EIU Programming Practices and Exams

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*10⁵), and the number of regions M (1 ≤ M ≤ 10⁵).
• The next N lines each describe a warship: Ship code (positive for our ships, negative for enemy ships) (absolute value not exceeding 10⁹) and ship strength (not exceeding 10⁹).
• The following M lines each describe a region: Region code K (not exceeding 10⁹), 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