R and W are playing a game.

They have a convex polygon with $n$ vertices, labeled $1, 2, 3, \dots, n$ in counter-clockwise order. Initially, the polygon has $n$ line segments, which are the edges of the polygon. We use an ordered pair $(u, v)$ (where $u < v$) to represent a line segment with endpoints $u$ and $v$.

Before the game starts, W performs some operations. In each operation, he selects two distinct vertices of the polygon and connects them with a line segment, provided that the new segment does not coincide with or intersect any existing segments (sharing only a common endpoint is not considered an intersection). He repeats this process until no more segments can be added, resulting in state $S_0$. $S_0$ contains the edges of the polygon and the segments added by W. It is easy to see that these segments divide the polygon into triangular regions. For any such triangle with vertices $i, j, k$ ($i < j < k$), we can assign it a label, such that each triangle is labeled with a unique value from $2, 3, \dots, n-1$.

W defines a "rotation" operation: for the current state, select 4 vertices $a, b, c, d$ such that $1 \le a < b < c < d \le n$ and there are 5 segments among them: $(a, b), (b, c), (c, d), (a, d), (a, c)$. Then, remove the segment $(a, c)$ and add the segment $(b, d)$. This "rotation" can be uniquely represented by the ordered pair $(a, c)$. It is clear that after each "rotation" operation, there are no intersecting segments in the polygon.

When W presents a state as the initial state to R, the game begins. During the game, R can perform a "rotation" on the current state. After a finite number of "rotations", R will reach a state where no further "rotations" can be performed, and the game ends. The sequence of ordered pairs corresponding to each "rotation" in the order they were performed is the operation plan for that round.

To increase the difficulty, W generates $m$ new states based on $S_0$. The $i$-th state $S_i$ is obtained by performing one "rotation" on $S_0$. You need to help R find the minimum number of "rotations" required to complete the game starting from each of $S_0, S_1, \dots, S_m$. Depending on W's mood, you may also need to find the number of different operation plans that achieve this minimum number of "rotations". Since the number of plans can be very large, output the result modulo $1,000,000,007$.

Input

The first line contains an integer $W$, representing W's mood. If $W=0$, only the minimum number of "rotations" is required. If $W=1$, the number of different operation plans with the minimum number of "rotations" is also required.

The second line contains a positive integer $n$, the number of vertices of the convex polygon.

The next $n-3$ lines each contain two positive integers $u, v$, representing a line segment added by W in $S_0$, with endpoints $u$ and $v$. It is guaranteed that this segment does not coincide with or intersect any existing segments.

The next line contains an integer $m$, the number of new states generated based on $S_0$.

The next $m$ lines each contain two integers. Assuming the $i$-th line contains $a, b$, it represents the state $S_i$ obtained by performing a $(a, b)$ "rotation" on $S_0$.

Output

Output $m+1$ lines.

If $W=0$, each line contains one integer. The $i$-th line ($i = 1, 2, \dots, m, m+1$) contains the minimum number of "rotations" starting from $S_{i-1}$.

If $W=1$, each line contains two integers. The $i$-th line ($i = 1, 2, \dots, m, m+1$) contains the minimum number of "rotations" and the number of different operation plans with that minimum number of "rotations" modulo $1,000,000,007$, starting from $S_{i-1}$.

Examples

Input 1

1
6
1 3
1 5
3 5
1
1 3

Output 1

3 2
3 1

Note 1

Starting from $S_0$, the minimum number of "rotations" is 3, with 2 possible plans. Starting from $S_1$, the minimum number of "rotations" is 3, with 1 possible plan. In the figures above, the yellow, blue, green, and red triangles correspond to labels 2, 3, 4, and 5 respectively.

Input 2

1
12
1 10
1 6
1 3
3 6
3 5
6 10
6 8
8 10
4
1 10
1 3
6 8
1 6

Output 2

8 210
7 210
8 70
8 105
8 140

Constraints

For all input data, it is guaranteed that: $3 \le n \le 100000, 0 \le m \le 100000$.

Figure 1. Example of a triangulated polygon with labeled triangles.