We are operating a fleet of NN servers and MM virtual machines, and some smart artificial intelligence has determined that the current mapping of VMs to servers is not optimal. The best mapping of virtual machines (VMs) was also found by the AI, but it fails to produce a good enough schedule of VM moves to achieve this ideal mapping. Can you help?

To change the mapping, you can move VM to any other server if there are enough resources. After one or several moves of the VM, it must be placed as planned:

Each server is characterized by two values: the ii-th server has scisci CPU cores and smismi GB RAM. Each VM is characterized by two values: the jj-th VM consumes vcjvcj cores and vmjvmj GB RAM.

You can move multiple VMs in the cloud at the same time. Parallel moves take the same time and are grouped into “steps”. Each move is characterized by three values: source server, target server, and VM to move.

Constraints:

  1. You do not control the order of moves inside a step. Before each step, the system checks if there are enough resources for each server for every VM it currently has and all arriving in the upcoming step. The release of previous resources (removed VMs) will happen between the steps.
  2. The network is a bottleneck, so no more than 22 parallel moves per server is possible (for example, if a server receives 3 new VMs and 1 old VM moves somewhere, this will take at least 2 steps). In particular, if there are NN servers in the cloud, you may have N×2÷2=NN×2÷2=N moves in a step, at most.

It is supposed that CPU cores and memory consumed by VM are allocated in the target server before the step started and deallocated in the source server only after the step is finished. It means that VMs consumes resources while transferring.

The goal is to find the schedule with minimal time to complete and avoid redundant migrations, if possible. The total score to be minimized is defined as follows:

Score=1000log10(Total_steps×Memory_moved_in_GB+1)Score=1000⋅log10⁡(Total_steps×Memory_moved_in_GB+1)

  • 2N10002≤N≤10001M1000001≤M≤100000;
  • Each server ii has scisci CPU cores and smismi GB RAM, 100sci500100≤sci≤500200smi1000200≤smi≤1000;
  • Each VM jj consumes vcjvcj cores and vmjvmj GB RAM, 1vcj2001≤vcj≤2001vmj5001≤vmj≤500;
  • Each server may host any number of VMs if its resource capacity is not violated.

The total score will be the sum of each test score. Each test score is rounded to 33 digits after the decimal points according to mathematical rules. Each test run without a solution (or failure during execution) will be penalized, penalty_score=10000penalty_score=10000 will be used for this case. The jury guarantees that the solution exists for each test.

The problem has two suites of tests: preliminary and main. The preliminary test suite consists of 3030 tests. This test suite is used to test your solutions during the contest (that is, immediately after submitting a solution). When the contest is over, then for each participant the last submission will be selected (which passed at least one test). This particular submission will be tested on the main test suite (other submissions will be ignored). The main suite consists of a preliminary suite plus another 2020 tests (so it contains a total of 30+20=5030+20=50 tests). After testing on the main test suite, the final standings table will be built, on the basis of which the final results of the contest will be announced.

Input

The first line of each test contains two integers — NN and MM (2N10002≤N≤10001M1000001≤M≤100000).

Next, NN lines contain server descriptions. The ii-th of them contains two integers — scisci and smismi (100sci500100≤sci≤500200smi1000200≤smi≤1000).

Next, MM lines contain VM descriptions. The jj-th of them contains two integers — vcjvcj and vmjvmj (1vcj2001≤vcj≤2001vmj5001≤vmj≤500).

Next, MM lines follow, each containing two integers oldjoldj and newjnewj (0oldj,newj<N0≤oldj,newj<N) — server index where jj-th VM located in the original mapping and server index where it should be located in the optimal mapping.

Output

In the first line print a single integer SS (0S31060≤S≤3⋅106) — total steps count.

Then print SS line groups with step descriptions. Each description should start with a line containing a single integer kiki (1kiM1≤ki≤M) — the number of parallel VM moves in the current step. Next print kiki lines with each VM move description — triplets of zero-indexed old server index, new server index, and VM index.

The jury guarantees that the solution exists for each test.

Examples

input

Copy
2 1
100 500
200 1000
50 200
0 1

output

Copy
1
1
0 1 0

input

Copy
3 3
100 350
200 480
150 720
80 300
20 50
150 480
0 1
2 0
1 2

output

Copy
3
1
2 0 1
1
1 2 2
1
0 1 0

input

Copy
5 6
500 1000
100 200
500 1000
500 500
500 1000
200 500
50 50
200 500
50 150
50 50
50 50
0 2
2 0
3 4
1 2
2 0
0 1

output

Copy
3
2
2 0 1
2 0 4
3
0 1 5
0 2 0
3 4 2
1
1 2 3

{“name”:”A. Fixing the Cloud”,”group”:”Codeforces – NERC Challenge 2020: Marathon”,”url”:”https://codeforces.com/contest/1460/problem/A”,”interactive”:false,”memoryLimit”:256,”timeLimit”:6000,”tests”:[{“input”:”2 1\n100 500\n200 1000\n50 200\n0 1\n”,”output”:”1\n1\n0 1 0\n”,”id”:1607763775156},{“input”:”3 3\n100 350\n200 480\n150 720\n80 300\n20 50\n150 480\n0 1\n2 0\n1 2\n”,”output”:”3\n1\n2 0 1\n1\n1 2 2\n1\n0 1 0\n”,”id”:1607763775182},{“id”:1607763775183,”input”:”5 6\n500 1000\n100 200\n500 1000\n500 500\n500 1000\n200 500\n50 50\n200 500\n50 150\n50 50\n50 50\n0 2\n2 0\n3 4\n1 2\n2 0\n0 1″,”output”:”3\n2\n2 0 1\n2 0 4\n3\n0 1 5\n0 2 0\n3 4 2\n1\n1 2 3″}],”testType”:”single”,”input”:{“type”:”stdin”},”output”:{“type”:”stdout”},”languages”:{“java”:{“mainClass”:”Main”,”taskClass”:”AFixingTheCloud”}},”srcPath”:”f:\\coding\\A_Fixing_the_Cloud.cpp”}