Under construction

Still being built. Things may change

Unit Founding Event

Interview

Time limit1sMemory limit1024 MB

Summary
Order N stages so each soldier joins its first preferred stage in that order and every stage meets its minimum headcount, or report -1.
Level

Medium6 of 10

Topics
Greedy, Queue, Array
Solved
No attempts yet

Problem

The enrollment for the unit founding event just closed!

The event consists of NN stages numbered 11 through NN, and PP soldiers take part. Each soldier has picked one or more preferred stages.

For the event to succeed, every stage must reach its minimum headcount. Since there is no spare capacity to distribute soldiers carefully, first fix the order of the stages, then place on each stage the soldiers who preferred it. Every soldier joins only the preferred stage that comes first in the order.

Find an order in which the event can succeed, and print one such order.

Input

The first line contains the number of stages NN and the number of soldiers PP, separated by a space.

The second line contains the minimum headcount mim_i of each stage from stage 11 to stage NN, separated by spaces.

Each of the next PP lines contains xix_i, the number of stages that soldier prefers, followed by the xix_i preferred stage numbers in ascending order. All numbers on a line are separated by spaces.

Output

If an order exists that meets the minimum headcount of every stage, print one valid order on NN lines. Otherwise, print -1.

Constraints

  • 1≤N≤50 0001 \le N \le 50\,000
  • 1≤P≤100 0001 \le P \le 100\,000
  • 1≤mi≤P1 \le m_i \le P
  • 1≤xi≤N1 \le x_i \le N; the sum of all xix_i does not exceed 500 000500\,000.

Examples3

  1. Example 1

    Input
    3 5
1 1 1
3 1 2 3
3 1 2 3
3 1 2 3
3 1 2 3
3 1 2 3
    Expected output
    -1

  2. Example 2

    Input
    3 5
1 2 1
2 1 3
1 2
1 1
2 1 2
2 2 3
    Expected output
    2
3
1

  3. Example 3

    Input
    4 15
2 3 3 3
2 1 4
1 3
1 3
1 1
2 2 4
2 1 2
1 2
2 2 4
3 1 2 4
1 2
2 1 3
2 1 4
2 3 4
3 2 3 4
1 3
    Expected output
    2
4
1
3