B. Building the Schedule
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Almost everything at a contest site is done by volunteers: printing, balloons, the help desk, the door of the contest hall. Before the contest starts, the organizers have to build the volunteer schedule.

There are $$$M$$$ shifts and $$$N$$$ volunteers. A shift with too few people cannot cover the hall, and a shift with too many people only creates noise, so shift $$$j$$$ needs at least $$$L_j$$$ and at most $$$U_j$$$ assigned volunteers. The volunteers have their own talks and meetings too: volunteer $$$i$$$ is available for some of the shifts and may be assigned to at most $$$c_i$$$ shifts. Writing the same person twice in the same shift helps nobody, so a volunteer can be assigned to the same shift at most once.

Find any assignment that satisfies every requirement, or determine that no such assignment exists.

Input

The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \le N,M \le 500$$$) — the number of volunteers and shifts.

Each of the next $$$M$$$ lines contains two integers $$$L_j$$$ and $$$U_j$$$ ($$$0 \le L_j \le U_j \le N$$$) — the minimum and maximum number of volunteers for shift $$$j$$$.

Each of the next $$$N$$$ lines describes one volunteer. The line for volunteer $$$i$$$ begins with two integers $$$c_i$$$ and $$$q_i$$$ ($$$0 \le c_i,q_i \le M$$$) — the maximum number of shifts volunteer $$$i$$$ may be assigned to, and the number of shifts volunteer $$$i$$$ is available for.

The same line then contains $$$q_i$$$ integers $$$s_{i,1},s_{i,2},\ldots,s_{i,q_i}$$$ ($$$1 \le s_{i,k} \le M$$$) — the shifts for which volunteer $$$i$$$ is available. These shift numbers are distinct.

Output

If no valid assignment exists, print -1.

Otherwise, print an integer $$$Q$$$ — the number of assignments. Then print $$$Q$$$ lines, each containing two integers $$$i$$$ and $$$j$$$, meaning that volunteer $$$i$$$ is assigned to shift $$$j$$$.

The printed volunteer-shift pairs must be distinct. Every pair must be available, no volunteer may appear more than $$$c_i$$$ times, and every shift $$$j$$$ must appear between $$$L_j$$$ and $$$U_j$$$ times, inclusive.

If several valid assignments exist, print any of them. It is allowed that $$$Q=0$$$.

Examples
Input
3 2
1 2
1 2
2 2 1 2
1 1 1
2 1 2
Output
2
1 1
1 2
Input
2 2
2 2
1 2
1 1 1
1 1 2
Output
-1
Input
2 3
0 0
0 2
0 1
0 0
2 0
Output
0
Note

In the first example, volunteer $$$1$$$ takes both shifts and volunteer $$$3$$$ takes the second shift. The two shifts receive one and two volunteers.

In the second example, shift $$$1$$$ needs two volunteers, but only volunteer $$$1$$$ is available for it.