The random integer y is either zero or one, and the random integer x is between 1 and N. The value y is a secret. We are given an interval , and we need to hold at all times in order to guarantee the confidentiality of the secret. (I.e. we want that .)
The values and are known for all i between 1 and N. Unfortunately, the dependency between x and y means that someone who learns x might be able to compute good bounds on . Fortunately, the value of x is not yet known. Your goal is to censor the value of x such that nobody can learn too much about the value of y.
To censor x means to partition the set {1, 2, ..., N} into equivalence classes A1, ..., AM such that, as soon as x is determined, only the index i of the unique equivalence class Ai that contains x becomes known (instead of the precise value of x).
You therefore have to find a partition such that for all i between 1 and M, the confidentiality of the secret is maintained, i.e. .
(Hint: Recall that , where means that both A and B are true, and .)
In case there are multiple solutions, compute an arbitrary solution that maximizes the number of equivalence classes that contain only a single element.
The first line of the input contains two space-separated integers A and B such that a·106 = A and b·106 = B. The second line of the input contains the single integer N (1 ≤ N ≤ 106).
The i-th of the next N lines of the input contains integers Xi and Yi such that and .
If there is no solution, print the single integer - 1.
Otherwise, the first line of the output should contain the size M of the partition. The i-th of the following M lines should contain an integer Ki, the number of elements of the i-th equivalence class Ai, followed by Ki numbers, the elements of Ai.
You may print the equivalence classes and their elements in any order.
## Input
The first line of the input contains two space-separated integers A and B such that a·106 = A and b·106 = B. The second line of the input contains the single integer N (1 ≤ N ≤ 106).The i-th of the next N lines of the input contains integers Xi and Yi such that and .
## Output
If there is no solution, print the single integer - 1.Otherwise, the first line of the output should contain the size M of the partition. The i-th of the following M lines should contain an integer Ki, the number of elements of the i-th equivalence class Ai, followed by Ki numbers, the elements of Ai.You may print the equivalence classes and their elements in any order.
[samples]
**Definitions**
Let $ N \in \mathbb{Z}^+ $, $ A, B \in \mathbb{Z} $ with $ A = a \cdot 10^6 $, $ B = b \cdot 10^6 $.
For each $ i \in \{1, \dots, N\} $, let $ (x_i, y_i) \in \mathbb{Z}^2 $ be given, where $ x_i \in [1, N] $, $ y_i \in \{0, 1\} $.
Let $ Y = \{ y_i \mid i \in \{1, \dots, N\} \} $ be the set of secret values.
**Constraints**
1. $ 1 \leq N \leq 10^6 $
2. $ y_i \in \{0, 1\} $ for all $ i \in \{1, \dots, N\} $
3. For any equivalence class $ A_j $ in the partition, if $ \exists i, k \in A_j $ such that $ y_i \ne y_k $, then the partition is invalid.
That is: $ \forall j \in \{1, \dots, M\}, \; \forall i, k \in A_j, \; y_i = y_k $
**Objective**
Find a partition $ \{A_1, \dots, A_M\} $ of $ \{1, 2, \dots, N\} $ such that:
- For each $ A_j $, all elements $ i \in A_j $ have identical $ y_i $.
- Maximize the number of singleton classes (i.e., classes with $ |A_j| = 1 $).
If no such partition exists (i.e., if two indices $ i, k $ with $ x_i = x_k $ but $ y_i \ne y_k $ exist), output $-1$.
Otherwise, output:
- First line: $ M $
- Next $ M $ lines: for each class $ A_j $, output $ |A_j| $ followed by the elements of $ A_j $ (in any order).