The ~X~ galaxy is facing its largest fight ever. The fight takes place across all regions with many of our and enemy warships, each identified by a code and strength. Determine the surviving ships in each region according to the following condition:

• The ships will be assigned to specific regions to fight, and a list of ship codes will represent the fight in each region.
• A stronger ship will defeat a weaker one. If two ships have equal strength, both will be destroyed.
• Enemy and our ships located close to each other in the list will fight each other first according to the order of the list.
  • For example: [1 2 -1] means that our ship number ~2~ will fight enemy ship number ~1~ first, and then based on the result of this fight, the next fight will be determined.

Input

• The first line is the number of warships ~N~ ~(2 ≤ N ≤ 3\times10^5)~, and the number of regions ~M~ ~(1 ≤ M ≤ 10^5)~.
• The next ~N~ lines each describe a warship: Ship code (positive for our ships, negative for enemy ships) (absolute value not exceeding ~10^9~) and ship strength (not exceeding ~10^9~).
• The following ~M~ lines each describe a region: Region code ~K~ (not exceeding ~10^9~), number of warships in region ~K~, and a list of ~K~ integers representing the fighting situation of ~K~ ships.
• The testcase ensures that each ship only participates in one region.

Output:

• For each region in the ascending order of identifier codes, an integer representing the winning side (~1~ is win, ~2~ is lose, ~0~ is a draw).

Sample Input

8 3
1 5
2 10
3 8
4 10
5 2
-1 5
-2 8
-3 5
1 3 1 2 -1
2 2 3 -2
3 3 4 5 -3

Sample Output

1 1
2 0
3 1