Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3651
Cipher Lock

Time Limit: 2 Seconds      Memory Limit: 65536 KB

CSBCLW (the Company Sells the Best Cipher Lock in the World) has just invented a new cipher lock. The internal structure of the cipher lock looks like a N-regular polygon, and its vertices, are key points, while two attributes can be set on them. The first attribute on the vertices is can be represented by an integer ranging from 1 to P, and the second attribute is can be represented by an integer ranging from 1 to Q. Only if all the vertices meet the condition that every pairs of adjacent vertices have at least one attribute in common, the cipher would be legal.

Due to security reasons, there are exact 8 special constraints on the lock. Each constraint are described as a tuple with three integers (X, U, V). It means on the X-th vertex of the lock, the two attributes must be U and V. Under this limitation, CSBCLW wants to know how many different locks can be produced.

Input

There are multiple test cases (no more than 100). For each test case:

The first line contains three integers N, P and Q (1 <= N, P, Q <= 10 ^ 10).

Then followed by 8 lines. Each line contains three integers X (1 <= X <= N), U (1 <= U <= P) and V (1 <= V <= Q).

Output

For each test case, output the number of different locks module 1234567890.

Sample Input

16 2 2
1 1 1
3 1 2
5 1 1
7 2 1
9 2 2
11 1 1
13 2 1
15 1 2

Sample Output

256

Author: WANG, Xiajun
Submit    Status