Guess the Money

Dshawn is a tuhao. He has a lot of money. One day, he gave A dollars to kuangbin and cxlove. kuangbin got B dollars and cxlove got C dollars. Obviously, A = B + C.

wuyiqi is very curious, he want to know the A,B and C. But they didn’t tell him. Just tell him some information about the three numbers.

Dshawn said that the number A has N₁ digits in its decimal representation (without extra leading zero). Assume the digits of its decimal expansion from the left to the right are a₀, a₁, ..., a_{N1 - 1}. Dshawn didn’t tell wuyiqi all the digits but tell him M₁ digits.

kuangbin said that the number B has N₂ digits in its decimal representation (without extra leading zero). Assume the digits of its decimal expansion from the left to the right are b₀, b₁, ..., b_{N2 - 1}. kuangbin didn’t tell wuyiqi all the digits but tell him M₂ digits.

cxlove said that the number C has N₃ digits in its decimal representation (without extra leading zero). Assume the digits of its decimal expansion from the left to the right are c₀, c₁, ..., c_{N3 - 1}. cxlove didn’t tell wuyiqi all the digits but tell him M₃ digits.

You should find the number of possible {A, B, C}. It is possible that someone tells lies, so if the information given is inconsistent with any possible {A, B, C}, you should also detect this.

The first line of the input is T (1 ≤ T ≤ 50), which stands for the number of test cases you need to solve.

The first line of each case contains two integers N₁,M₁ (1 ≤ N₁ ≤ 10⁷, 0 ≤ M₁ ≤ min(N₁, 10⁴)).

For the next M₁ lines, each line contains two integers id and x (0 ≤ id < N₁, 0 ≤ x ≤ 9) means a_id = x.

The next line contains two integers N₂,M₂ (1 ≤ N₂ ≤ 10⁷, 0 ≤ M₂ ≤ min(N₂, 10⁴)).

For the next M₂ lines, each line contains two integers id and x (0 ≤ id < N₂, 0 ≤ x ≤ 9) means b_id = x.

The next line contains two integers N₃,M₃ (1 ≤ N₃ ≤ 10⁷, 0 ≤ M₃ ≤ min(N₃, 10⁴)).

For the next M₃ lines, each line contains two integers id and x (0 ≤ id < N₃, 0 ≤ x ≤ 9) means c_id = x.

For each test case, print a line “Case #t: ”(without quotes, t means the index of the test case) at the beginning.

If it is impossible, please output “IMPOSSIBLE” else output the answer modulo 20140927.

3	
2 0
1 1
0 9
1 0
1 1
0 5
1 0
1 0
2 0
3 0
2 0

Case #1: 9
Case #2: 6
Case #3: IMPOSSIBLE

2014 ACM/ICPC Asia Regional Shanghai Online