C. Black Widow

problem_index: C

time_limit: 2 seconds

memory_limit: 256 megabytes

note:
The equation in the first sample is:
![image](images/cf_704_C/4.png)
The equation in the second sample is:
![image](images/cf_704_C/5.png)
The equation in the third sample is:
![image](images/cf_704_C/6.png)

question:
Natalia Romanova is trying to test something on the new gun S.H.I.E.L.D gave her. In order to determine the result of the test, she needs to find the number of answers to a certain equation. The equation is of form:
![image](1.png)
Where ![image](2.png) represents logical OR and ![image](3.png) represents logical exclusive OR (XOR), and v_{i, j} are some boolean variables or their negations. Natalia calls the left side of the equation a XNF formula. Each statement in brackets is called a clause, and v_{i, j} are called literals.
In the equation Natalia has, the left side is actually a 2-XNF-2 containing variables x_{1}, x_{2}, ..., x_{m} and their negations. An XNF formula is 2-XNF-2 if:
 -  For each 1 ≤ i ≤ n, k_{i} ≤ 2, i.e. the size of each clause doesn't exceed two. -  Each variable occurs in the formula at most two times (with negation and without negation in total). Please note that it's possible that a variable occurs twice but its negation doesn't occur in any clause (or vice versa). Natalia is given a formula of m variables, consisting of n clauses. Please, make sure to check the samples in order to properly understand how the formula looks like.
Natalia is more into fight than theory, so she asked you to tell her the number of answers to this equation. More precisely, you need to find the number of ways to set x_{1}, ..., x_{m} with true and false (out of total of 2^{m} ways) so that the equation is satisfied. Since this number can be extremely large, you need to print the answer modulo 10^{9} + 7.
Please, note that some variable may appear twice in one clause, or not appear in the equation at all (but still, setting it to false or true gives different ways to set variables).

Input
The first line of input contains two integers n and m (1 ≤ n, m ≤ 100 000) — the number of clauses and the number of variables respectively.
The next n lines contain the formula. The i-th of them starts with an integer k_{i} — the number of literals in the i-th clause. It is followed by k_{i} non-zero integers a_{i, 1}, ..., a_{i, ki}. If a_{i, j} > 0 then v_{i, j} is x_{ai, j} otherwise it's negation of x_{ - ai, j} (1 ≤ k_{i} ≤ 2,  - m ≤ a_{i, j} ≤ m, a_{i, j} ≠ 0).

Output
Print the answer modulo 1 000 000 007 (10^{9} + 7) in one line.

Examples
Input
6 7
2 4 -2
2 6 3
2 -7 1
2 -5 1
2 3 6
2 -2 -5

Output
48

Input
8 10
1 -5
2 4 -6
2 -2 -6
2 -7 9
2 10 -1
2 3 -1
2 -8 9
2 5 8

Output
544

Input
2 3
2 1 1
2 -3 3

Output
4

Note
The equation in the first sample is:
![image](4.png)The equation in the second sample is:
![image](5.png)The equation in the third sample is:
![image](6.png)

source: codeforces

raw_problem:
C. Black Widow

time limit per test
2 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

Natalia Romanova is trying to test something on the new gun S.H.I.E.L.D gave her. In order to determine the result of the test, she needs to find the number of answers to a certain equation. The equation is of form:

Where  represents logical OR and  represents logical exclusive OR (XOR), and vi, j are some boolean variables or their negations. Natalia calls the left side of the equation a XNF formula. Each statement in brackets is called a clause, and vi, j are called literals.

In the equation Natalia has, the left side is actually a 2-XNF-2 containing variables x1, x2, ..., xm and their negations. An XNF formula is 2-XNF-2 if:

 For each 1 ≤ i ≤ n, ki ≤ 2, i.e. the size of each clause doesn't exceed two.

 Each variable occurs in the formula at most two times (with negation and without negation in total). Please note that it's possible that a variable occurs twice but its negation doesn't occur in any clause (or vice versa).

Natalia is given a formula of m variables, consisting of n clauses. Please, make sure to check the samples in order to properly understand how the formula looks like.

Natalia is more into fight than theory, so she asked you to tell her the number of answers to this equation. More precisely, you need to find the number of ways to set x1, ..., xm with true and false (out of total of 2m ways) so that the equation is satisfied. Since this number can be extremely large, you need to print the answer modulo 109 + 7.

Please, note that some variable may appear twice in one clause, or not appear in the equation at all (but still, setting it to false or true gives different ways to set variables).

Input

The first line of input contains two integers n and m (1 ≤ n, m ≤ 100 000) — the number of clauses and the number of variables respectively.

The next n lines contain the formula. The i-th of them starts with an integer ki — the number of literals in the i-th clause. It is followed by ki non-zero integers ai, 1, ..., ai, ki. If ai, j > 0 then vi, j is xai, j otherwise it's negation of x - ai, j (1 ≤ ki ≤ 2,  - m ≤ ai, j ≤ m, ai, j ≠ 0).

Output

Print the answer modulo 1 000 000 007 (109 + 7) in one line.

Examples

Input

6 7
2 4 -2
2 6 3
2 -7 1
2 -5 1
2 3 6
2 -2 -5

Output

48

Input

8 10
1 -5
2 4 -6
2 -2 -6
2 -7 9
2 10 -1
2 3 -1
2 -8 9
2 5 8

Output

544

Input

2 3
2 1 1
2 -3 3

Output

4

Note

The equation in the first sample is:

The equation in the second sample is:

The equation in the third sample is:

tags: ['Mathematics', 'Dynamic programming', 'Graph algorithms', 'Implementation']

skill_types: ['Dynamic programming']

raw_tags: ['math', 'graphs', 'implementation', 'dp']

image_tags: Math Math Math Math Math Math

data_split: test


D. Shaass and Painter Robot

problem_index: D

time_limit: 2 seconds

memory_limit: 256 megabytes

source: codeforces

raw_problem:
D. Shaass and Painter Robot

time limit per test
2 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

Shaass thinks a kitchen with all white floor tiles is so boring. His kitchen floor is made of n·m square tiles forming a n × m rectangle. Therefore he's decided to color some of the tiles in black so that the floor looks like a checkerboard, which is no two side-adjacent tiles should have the same color.

Shaass wants to use a painter robot to color the tiles. In the beginning the robot is standing in a border tile (xs, ys) facing a diagonal direction (i.e. upper-left, upper-right, down-left or down-right). As the robot walks in the kitchen he paints every tile he passes even if it's painted before. Painting each tile consumes one unit of black paint. If at any moment the robot hits a wall of the kitchen he changes his direction according the reflection rules. Note that a tile gets painted when the robot enters the tile from another tile, in other words changing direction in the same tile doesn't lead to any painting. The first tile the robot is standing on, is also painted.

The robot stops painting the first moment the floor is checkered. Given the dimensions of the kitchen and the position of the robot, find out the amount of paint the robot consumes before it stops painting the floor.

Let's consider an examples depicted below.

If the robot starts at tile number 1 (the tile (1, 1)) of the left grid heading to down-right it'll pass tiles 1354236 and consumes 7 units of black paint on his way until he stops at tile number 6. But if it starts at tile number 1 in the right grid heading to down-right it will get stuck in a loop painting tiles 1, 2, and 3.

Input

The first line of the input contains two integers n and m, (2 ≤ n, m ≤ 105). The second line contains two integers xs and ys (1 ≤ xs ≤ n, 1 ≤ ys ≤ m) and the direction robot is facing initially. Direction is one of the strings: "UL" (upper-left direction), "UR" (upper-right), "DL" (down-left) or "DR" (down-right).

Note, that record (xs, ys) denotes the tile that is located at the xs-th row from the top and at the ys-th column from the left of the kitchen.

It's guaranteed that the starting position will be a border tile (a tile with less than four side-adjacent tiles).

Output

Print the amount of paint the robot consumes to obtain a checkered kitchen floor. Or print -1 if it never happens.

Please do not use the %lld specificator to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specificator.

Examples

Input

3 4
1 1 DR

Output

7

Input

3 4
3 3 DR

Output

11

Input

3 3
1 1 DR

Output

-1

Input

3 3
1 2 DL

Output

4

question:
Shaass thinks a kitchen with all white floor tiles is so boring. His kitchen floor is made of n·m square tiles forming a n × m rectangle. Therefore he's decided to color some of the tiles in black so that the floor looks like a checkerboard, which is no two side-adjacent tiles should have the same color.
Shaass wants to use a painter robot to color the tiles. In the beginning the robot is standing in a border tile (x_{s}, y_{s}) facing a diagonal direction (i.e. upper-left, upper-right, down-left or down-right). As the robot walks in the kitchen he paints every tile he passes even if it's painted before. Painting each tile consumes one unit of black paint. If at any moment the robot hits a wall of the kitchen he changes his direction according the reflection rules. Note that a tile gets painted when the robot enters the tile from another tile, in other words changing direction in the same tile doesn't lead to any painting. The first tile the robot is standing on, is also painted.
The robot stops painting the first moment the floor is checkered. Given the dimensions of the kitchen and the position of the robot, find out the amount of paint the robot consumes before it stops painting the floor.
Let's consider an examples depicted below.
 ![image](1.png) If the robot starts at tile number 1 (the tile (1, 1)) of the left grid heading to down-right it'll pass tiles 1354236 and consumes 7 units of black paint on his way until he stops at tile number 6. But if it starts at tile number 1 in the right grid heading to down-right it will get stuck in a loop painting tiles 1, 2, and 3.

Input
The first line of the input contains two integers n and m, (2 ≤ n, m ≤ 10^{5}). The second line contains two integers x_{s} and y_{s} (1 ≤ x_{s} ≤ n, 1 ≤ y_{s} ≤ m) and the direction robot is facing initially. Direction is one of the strings: "UL" (upper-left direction), "UR" (upper-right), "DL" (down-left) or "DR" (down-right).
Note, that record (x_{s}, y_{s}) denotes the tile that is located at the x_{s}-th row from the top and at the y_{s}-th column from the left of the kitchen.
It's guaranteed that the starting position will be a border tile (a tile with less than four side-adjacent tiles).

Output
Print the amount of paint the robot consumes to obtain a checkered kitchen floor. Or print -1 if it never happens.
Please do not use the %lld specificator to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specificator.

Examples
Input
3 4
1 1 DR

Output
7

Input
3 4
3 3 DR

Output
11

Input
3 3
1 1 DR

Output
-1

Input
3 3
1 2 DL

Output
4

tags: ['Number theory', 'Implementation', 'Complete search']

skill_types: ['Complete search']

raw_tags: ['brute force', 'number theory', 'implementation']

data_split: test


Jez

difficulty: HARD

source: open kattis

raw_problem:
Luka found a very unusual game board in his attic.
    Surprisingly, it consists of $R
    \cdot C$ square cells. The rows are numbered
    $0$ to $R-1$ top to bottom and the columns
    $0$ to $C-1$ left to right.

What makes the board unusual is the way in which the cells
    are coloured. Each cell is either grey or white:

white, if the row and column numbers of the cell, when
        represented in binary, have at least one digit 1 in the
        same position. For example, the cell $(4, 5)$ would be white.

grey, otherwise. For example, the cell $(2, 5)$ would be grey.

The following image shows a board of size 10·10.

Luka’s hedgehog likes walking on this unusual board and does
    it in an unusual way. The hedgehog starts his walk in the cell
    $(0, 0)$ and continues in
    the zig-zag pattern as in the second image above. While the
    hedgehog is walking, Luka counts how many
    grey squares it visited.

After visiting $K$
    squares, the hedgehog gets tired and falls asleep. Luka then
    goes to bed too, happy that he was able count the grey
    squares.

Knowing the dimensions of the board and the number
    $K$ beforehand, however,
    it is possible to write a program that calculates the result
    faster. This is your task.

Input

The first line contains two integers $R$ ($1
    \le R \le 1\, 000\, 000$) and $C$ ($1
    \le C \le 1\, 000\, 000$), the dimensions of the
    board.

The second line contains the integer $K$ ($1
    \le K \le R \cdot C$), the total number of squares the
    hedgehog visits.

Note that this number may not fit in a 32-bit integer.

Output

Output the number of grey cells the hedgehog visits.

Sample Input 1
Sample Output 1

10 10
6

5

Sample Input 2
Sample Output 2

3 5
11

8

Sample Input 3
Sample Output 3

10 10
100

51

question:
Luka found a very unusual game board in his attic. Surprisingly, it consists of$R \cdot C$square cells. The rows are numbered$0$to$R-1$top to bottom and the columns$0$to$C-1$left to right.
What makes the board unusual is the way in which the cells are coloured. Each cell is either grey or white:
- white, if the row and column numbers of the cell, when represented in binary, have at least one digit 1 in the same position. For example, the cell $(4, 5)$ would be white.- grey, otherwise. For example, the cell $(2, 5)$ would be grey.
The following image shows a board of size 10·10.
![image](1.png)![image](2.png)Luka’s hedgehog likes walking on this unusual board and does it in an unusual way. The hedgehog starts his walk in the cell$(0, 0)$and continues in the zig-zag pattern as in the second image above. While the hedgehog is walking, Luka countshow many grey squaresit visited.
After visiting$K$squares, the hedgehog gets tired and falls asleep. Luka then goes to bed too, happy that he was able count the grey squares.
Knowing the dimensions of the board and the number$K$beforehand, however, it is possible to write a program that calculates the result faster. This is your task.

Input
The first line contains two integers$R$($1 \le R \le 1\, 000\, 000$) and$C$($1 \le C \le 1\, 000\, 000$), the dimensions of the board.
The second line contains the integer$K$($1 \le K \le R \cdot C$), the total number of squares the hedgehog visits.
Note that this number may not fit in a 32-bit integer.

Output
Output the number of grey cells the hedgehog visits.
Sample Input 1
10 10
6

Sample Output 1
5

Sample Input 2
3 5
11

Sample Output 2
8

Sample Input 3
10 10
100

Sample Output 3
51

image_tags: Chessboard Patterns

data_split: test


B. Restaurant Game

problem_index: B

time_limit: 1 second

memory_limit: 256 megabytes

input_output: {"inputs": ["10\n429\n41 20\nleft left\n977\n606 92\nleft left\n874\n742 866\nright right\n774\n61 573\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n606 92\nleft left\n874\n27 866\nright right\n774\n61 573\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n606 92\nleft left\n874\n742 866\nright right\n774\n61 115\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n606 92\nleft left\n874\n742 866\nright right\n774\n61 115\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n1 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n46 20\nleft left\n977\n606 92\nleft left\n874\n742 866\nright right\n774\n61 573\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n46 20\nleft left\n977\n606 92\nleft left\n874\n742 866\nright right\n774\n61 573\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 384\nright left\n", "10\n429\n41 20\nleft left\n977\n606 92\nleft left\n874\n27 866\nright right\n774\n61 573\nright right\n315\n160 287\nright left\n985\n47 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n691 92\nleft left\n874\n742 866\nright right\n774\n61 115\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n606 92\nleft left\n874\n742 866\nright right\n774\n61 573\nright right\n315\n160 287\nright left\n1873\n871 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n46 20\nleft left\n977\n583 92\nleft left\n874\n742 866\nright right\n774\n61 573\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n691 92\nleft left\n1707\n742 866\nright right\n774\n61 115\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n372 92\nleft left\n874\n27 866\nright right\n774\n61 573\nright right\n414\n160 287\nright left\n1551\n871 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n606 92\nleft left\n874\n742 866\nright right\n774\n61 573\nright right\n315\n160 287\nright left\n1873\n871 277\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n606 92\nleft left\n874\n742 866\nright right\n861\n61 115\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n706\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n691 97\nleft left\n874\n742 206\nright right\n774\n61 184\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n379\n41 20\nleft left\n977\n606 14\nleft left\n874\n742 866\nright right\n774\n61 115\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n1 70\nright left\n880\n336 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n823 92\nleft left\n874\n27 866\nright right\n774\n61 573\nright right\n315\n160 287\nright left\n985\n47 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n691 92\nleft left\n1707\n742 866\nright right\n774\n61 162\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n372 92\nleft left\n874\n27 866\nright right\n774\n61 573\nright right\n414\n160 287\nright left\n1551\n871 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n232 542\nright left\n", "10\n429\n41 20\nleft left\n977\n197 92\nleft left\n874\n742 866\nright right\n774\n61 573\nright right\n315\n160 287\nright left\n1873\n871 277\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n46 20\nleft left\n977\n583 137\nleft left\n874\n742 866\nright right\n774\n61 573\nright right\n315\n160 238\nright left\n985\n871 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n26 20\nleft left\n977\n372 92\nleft left\n874\n27 866\nright right\n774\n61 573\nright right\n414\n160 287\nright left\n1551\n871 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n565 592\nright left\n599\n509 542\nright left\n", "10\n379\n41 20\nleft left\n977\n606 14\nleft left\n874\n742 866\nright right\n774\n61 115\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n1 70\nright left\n880\n612 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n46 20\nleft left\n977\n583 92\nleft left\n874\n742 866\nright right\n774\n61 573\nright right\n431\n160 287\nright left\n985\n871 814\nleft right\n73\n-1 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n78 20\nleft left\n977\n372 92\nleft left\n874\n27 866\nright right\n774\n61 573\nright right\n414\n160 287\nright left\n1551\n871 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n232 542\nright left\n", "10\n429\n41 20\nleft left\n977\n197 92\nleft left\n874\n742 866\nright right\n934\n61 573\nright right\n315\n160 287\nright left\n1873\n871 277\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n930\n823 92\nleft left\n874\n46 866\nright right\n774\n61 573\nright right\n315\n160 287\nright left\n985\n47 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n606 92\nleft left\n874\n742 866\nright right\n774\n61 573\nright right\n315\n177 287\nright left\n1873\n871 338\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n800\n509 542\nright left\n", "10\n429\n46 20\nleft left\n977\n583 92\nleft left\n874\n742 866\nright right\n551\n61 573\nright right\n431\n160 287\nright left\n985\n871 814\nleft right\n73\n-1 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n1253\n197 92\nleft left\n874\n742 866\nright right\n934\n61 573\nright right\n315\n160 287\nright left\n1873\n871 277\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n379\n41 20\nleft left\n977\n606 14\nleft left\n1371\n742 866\nright right\n774\n61 115\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n1 70\nright left\n880\n475 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n379\n41 20\nleft left\n977\n606 14\nleft left\n418\n742 866\nright right\n774\n61 115\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n1 70\nright left\n880\n475 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n606 92\nleft left\n874\n742 866\nright right\n774\n61 72\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n1 70\nright left\n880\n336 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n46 20\nleft left\n977\n583 92\nleft left\n874\n742 866\nright right\n774\n61 573\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n530 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n823 92\nleft left\n874\n27 866\nright right\n774\n61 573\nright right\n315\n160 287\nright left\n985\n47 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n12 542\nright left\n", "10\n429\n41 20\nleft left\n977\n606 92\nleft left\n874\n742 866\nright right\n774\n61 956\nright right\n315\n160 287\nright left\n1873\n871 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n800\n509 542\nright left\n", "10\n429\n46 20\nleft left\n1833\n583 92\nleft left\n874\n742 866\nright right\n774\n61 573\nright right\n431\n160 287\nright left\n985\n871 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n197 92\nleft left\n874\n742 866\nright right\n774\n61 573\nright right\n315\n160 287\nright left\n1873\n1476 277\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n684\n41 20\nleft left\n977\n606 92\nleft left\n874\n742 866\nright right\n774\n61 573\nright right\n315\n160 287\nright left\n1873\n871 338\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n800\n509 542\nright left\n", "10\n429\n46 20\nleft left\n977\n583 92\nleft left\n874\n742 866\nright right\n551\n82 573\nright right\n431\n160 287\nright left\n985\n871 814\nleft right\n73\n-1 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n78 20\nleft left\n977\n372 92\nleft left\n874\n27 866\nright right\n1257\n61 573\nright right\n414\n222 287\nright left\n1551\n871 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n232 542\nright left\n", "10\n429\n41 20\nleft left\n1253\n197 92\nleft left\n874\n742 866\nright right\n934\n61 573\nright right\n315\n160 287\nright left\n1873\n871 158\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n379\n41 20\nleft left\n977\n606 14\nleft left\n246\n742 866\nright right\n774\n61 115\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n1 70\nright left\n880\n475 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n606 92\nleft left\n874\n742 866\nright right\n774\n43 573\nright right\n315\n177 287\nright left\n3332\n871 338\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n800\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n606 92\nleft left\n874\n742 866\nright right\n774\n43 573\nright right\n315\n177 287\nright left\n1873\n871 338\nleft right\n73\n0 51\nright left\n880\n358 535\nright left\n842\n457 527\nright left\n800\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n606 92\nleft left\n874\n742 866\nright right\n1233\n61 115\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n-1 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n46 20\nleft left\n1085\n583 92\nleft left\n874\n742 866\nright right\n774\n61 573\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n530 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n606 92\nleft left\n874\n742 866\nright right\n861\n61 115\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n706\n457 567\nright left\n1135\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n197 92\nleft left\n874\n742 866\nright right\n1372\n61 573\nright right\n315\n160 287\nright left\n1873\n1476 277\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n684\n64 20\nleft left\n977\n606 92\nleft left\n874\n742 866\nright right\n774\n61 573\nright right\n315\n160 287\nright left\n1873\n871 338\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n800\n509 542\nright left\n", "10\n429\n83 20\nleft left\n977\n583 92\nleft left\n874\n742 866\nright right\n774\n61 573\nright right\n431\n160 287\nright left\n985\n871 814\nleft right\n73\n-1 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n634\n509 542\nright left\n", "10\n429\n41 20\nleft left\n930\n823 92\nleft left\n874\n46 938\nright right\n774\n61 573\nright right\n315\n160 287\nright left\n985\n47 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 264\nright left\n599\n509 542\nright left\n", "10\n429\n78 20\nleft left\n977\n372 92\nleft left\n874\n27 866\nright right\n1257\n61 573\nright right\n414\n222 287\nright left\n1551\n871 814\nleft right\n73\n0 70\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n232 542\nright left\n", "10\n300\n41 20\nleft left\n1253\n197 92\nleft left\n874\n742 866\nright right\n934\n61 573\nright right\n315\n160 287\nright left\n1873\n871 158\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n14 92\nleft left\n874\n742 866\nright right\n774\n43 573\nright right\n315\n177 287\nright left\n3332\n871 338\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n800\n509 542\nright left\n", "10\n429\n46 28\nleft left\n977\n583 92\nleft left\n874\n742 866\nright right\n551\n61 573\nright right\n431\n160 287\nright left\n985\n871 814\nleft right\n73\n-1 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n286 542\nright left\n", "10\n429\n41 20\nleft left\n977\n606 92\nleft left\n874\n742 866\nright right\n774\n43 573\nright right\n315\n177 287\nright left\n1873\n871 338\nleft right\n73\n0 51\nright left\n880\n358 535\nright left\n684\n457 527\nright left\n800\n509 542\nright left\n", "10\n429\n41 0\nleft left\n977\n606 92\nleft left\n874\n742 866\nright right\n774\n61 115\nright right\n315\n160 287\nright left\n1898\n871 814\nleft right\n73\n1 45\nright left\n880\n358 535\nright left\n842\n457 1132\nright left\n599\n509 542\nright left\n", "10\n429\n46 20\nleft left\n1568\n606 92\nleft left\n1631\n742 866\nright right\n774\n61 1035\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n438\n606 92\nleft left\n874\n742 866\nright right\n774\n61 72\nright right\n315\n161 287\nright left\n985\n871 814\nleft right\n73\n1 70\nright left\n880\n336 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n83 20\nleft left\n1928\n583 92\nleft left\n874\n742 866\nright right\n774\n61 573\nright right\n431\n160 287\nright left\n985\n871 814\nleft right\n73\n-1 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n634\n509 542\nright left\n", "10\n429\n41 0\nleft left\n977\n606 92\nleft left\n874\n742 866\nright right\n774\n61 115\nright right\n315\n160 287\nright left\n1898\n871 814\nleft right\n73\n1 45\nright left\n880\n358 548\nright left\n842\n457 1132\nright left\n1098\n509 542\nright left\n", "10\n300\n41 20\nleft left\n1253\n197 92\nleft left\n874\n742 637\nright right\n934\n61 573\nright right\n315\n160 287\nright left\n1684\n871 158\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n3 592\nright left\n599\n509 542\nright left\n", "10\n300\n41 20\nleft left\n1253\n197 92\nleft left\n874\n742 637\nright right\n934\n92 573\nright right\n315\n160 287\nright left\n1684\n871 158\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n3 592\nright left\n599\n509 542\nright left\n", "10\n300\n41 20\nleft left\n941\n197 92\nleft left\n874\n742 637\nright right\n934\n92 573\nright right\n315\n160 287\nright left\n1684\n871 158\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n3 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n606 92\nleft left\n874\n742 866\nright right\n1398\n61 115\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n1 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n372 92\nleft left\n874\n27 866\nright right\n774\n61 573\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n0 45\nright left\n880\n358 341\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n606 92\nleft left\n874\n742 866\nright right\n774\n61 573\nright right\n315\n160 287\nright left\n3418\n871 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n46 20\nleft left\n721\n583 92\nleft left\n874\n742 866\nright right\n774\n61 573\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n372 92\nleft left\n874\n27 866\nright right\n774\n61 573\nright right\n414\n115 287\nright left\n1551\n871 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n361 92\nleft left\n874\n742 866\nright right\n861\n61 115\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n706\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n46 20\nleft left\n977\n583 137\nleft left\n874\n742 866\nright right\n774\n61 573\nright right\n315\n160 287\nright left\n985\n862 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n692\n41 20\nleft left\n977\n372 92\nleft left\n874\n27 866\nright right\n774\n61 573\nright right\n414\n160 287\nright left\n1551\n871 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n565 592\nright left\n599\n509 542\nright left\n", "10\n429\n44 20\nleft left\n977\n691 97\nleft left\n874\n742 206\nright right\n774\n61 184\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n606 92\nleft left\n874\n742 866\nright right\n203\n61 115\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n1 70\nright left\n880\n290 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n691 92\nleft left\n1707\n742 866\nright right\n774\n61 162\nright right\n315\n160 287\nright left\n1466\n871 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n823 92\nleft left\n874\n46 866\nright right\n774\n61 573\nright right\n315\n160 287\nright left\n985\n47 814\nleft right\n73\n0 45\nright left\n880\n666 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n46 20\nleft left\n977\n583 175\nleft left\n874\n742 866\nright right\n774\n61 573\nright right\n431\n160 287\nright left\n985\n871 814\nleft right\n73\n-1 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n164\n41 20\nleft left\n977\n691 92\nleft left\n1707\n742 1432\nright right\n774\n61 162\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n46 20\nleft left\n1407\n583 92\nleft left\n874\n742 866\nright right\n551\n61 573\nright right\n431\n160 287\nright left\n985\n871 814\nleft right\n73\n-1 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n78 20\nleft left\n977\n372 92\nleft left\n874\n27 866\nright right\n774\n61 573\nright right\n414\n222 287\nright left\n1551\n871 814\nleft right\n73\n-1 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n232 542\nright left\n", "10\n429\n41 20\nleft left\n1253\n197 92\nleft left\n874\n742 866\nright right\n934\n61 573\nright right\n315\n160 287\nright left\n1873\n871 277\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 294\nright left\n", "10\n429\n41 20\nleft left\n977\n606 92\nleft left\n874\n742 866\nright right\n774\n43 573\nright right\n315\n177 287\nright left\n1873\n1342 338\nleft right\n73\n0 51\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n800\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n857 92\nleft left\n874\n742 866\nright right\n774\n61 573\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n0 45\nright left\n880\n283 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n606 92\nleft left\n874\n651 866\nright right\n774\n61 115\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n1 65\nright left\n880\n290 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n46 20\nleft left\n977\n583 137\nleft left\n874\n742 866\nright right\n774\n61 573\nright right\n315\n160 238\nright left\n985\n871 814\nleft right\n73\n0 45\nright left\n880\n143 535\nright left\n811\n457 592\nright left\n599\n509 542\nright left\n", "10\n684\n41 20\nleft left\n977\n606 92\nleft left\n874\n742 866\nright right\n774\n61 560\nright right\n315\n160 287\nright left\n1873\n871 338\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n800\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n197 92\nleft left\n874\n742 866\nright right\n934\n61 573\nright right\n404\n160 287\nright left\n1873\n688 277\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n930\n823 92\nleft left\n874\n46 938\nright right\n774\n61 573\nright right\n315\n160 287\nright left\n985\n47 814\nleft right\n73\n0 45\nright left\n880\n358 281\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n46 20\nleft left\n977\n583 92\nleft left\n490\n742 866\nright right\n551\n82 573\nright right\n431\n160 287\nright left\n985\n871 814\nleft right\n73\n-1 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n672\n41 20\nleft left\n977\n606 92\nleft left\n874\n742 866\nright right\n1233\n61 115\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n-1 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 0\nleft left\n977\n606 92\nleft left\n874\n742 866\nright right\n774\n61 115\nright right\n315\n61 287\nright left\n985\n871 814\nleft right\n73\n1 45\nright left\n880\n358 535\nright left\n842\n457 1132\nright left\n599\n509 542\nright left\n", "10\n623\n41 20\nleft left\n977\n372 92\nleft left\n874\n27 866\nright right\n774\n61 573\nright right\n811\n160 287\nright left\n985\n871 814\nleft right\n73\n0 45\nright left\n880\n358 146\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n46 20\nleft left\n1085\n583 92\nleft left\n874\n742 866\nright right\n774\n61 573\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n-1 45\nright left\n880\n358 535\nright left\n842\n530 592\nright left\n599\n509 542\nright left\n", "10\n429\n44 20\nleft left\n930\n823 92\nleft left\n874\n46 938\nright right\n774\n61 573\nright right\n315\n160 287\nright left\n985\n47 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 264\nright left\n599\n509 542\nright left\n", "10\n429\n78 20\nleft left\n977\n372 92\nleft left\n874\n27 866\nright right\n1257\n61 573\nright right\n414\n222 287\nright left\n1551\n871 1316\nleft right\n73\n0 70\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n232 542\nright left\n", "10\n429\n46 28\nleft left\n977\n583 92\nleft left\n874\n742 866\nright right\n551\n61 573\nright right\n431\n160 287\nright left\n985\n871 814\nleft right\n73\n-1 45\nright left\n880\n358 940\nright left\n842\n457 592\nright left\n599\n286 542\nright left\n", "10\n684\n57 20\nleft left\n977\n606 92\nleft left\n874\n742 866\nright right\n377\n61 573\nright right\n315\n160 287\nright left\n1873\n871 338\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n800\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n14 92\nleft left\n874\n55 866\nright right\n774\n43 573\nright right\n315\n177 287\nright left\n3332\n871 338\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n800\n509 542\nright left\n", "10\n429\n41 0\nleft left\n977\n606 92\nleft left\n874\n742 866\nright right\n774\n76 115\nright right\n315\n160 287\nright left\n1898\n871 814\nleft right\n73\n1 45\nright left\n880\n358 535\nright left\n842\n457 1132\nright left\n1098\n509 542\nright left\n", "10\n300\n41 20\nleft left\n1253\n197 92\nleft left\n360\n742 637\nright right\n934\n61 573\nright right\n315\n160 287\nright left\n1873\n871 158\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n3 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n14 92\nleft left\n874\n96 866\nright right\n774\n43 573\nright right\n315\n177 287\nright left\n3332\n871 338\nleft right\n73\n1 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n800\n509 542\nright left\n", "10\n429\n41 0\nleft left\n977\n606 92\nleft left\n874\n742 866\nright right\n774\n61 115\nright right\n315\n160 287\nright left\n2049\n871 814\nleft right\n73\n1 45\nright left\n880\n358 548\nright left\n842\n457 1132\nright left\n1098\n509 542\nright left\n", "10\n300\n41 20\nleft left\n1253\n197 92\nleft left\n874\n742 637\nright right\n934\n61 573\nright right\n315\n5 287\nright left\n1684\n871 158\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n3 592\nright left\n599\n509 542\nright left\n", "10\n300\n41 20\nleft left\n941\n311 92\nleft left\n874\n742 637\nright right\n934\n92 573\nright right\n315\n160 396\nright left\n1684\n871 158\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n3 592\nright left\n599\n509 542\nright left\n", "10\n710\n41 20\nleft left\n977\n372 92\nleft left\n874\n27 866\nright right\n774\n61 573\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n0 45\nright left\n880\n358 341\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n361 92\nleft left\n874\n742 438\nright right\n861\n61 115\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n706\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n823 92\nleft left\n874\n46 866\nright right\n774\n98 573\nright right\n315\n160 287\nright left\n985\n47 814\nleft right\n73\n0 45\nright left\n880\n666 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n46 13\nleft left\n1407\n583 92\nleft left\n874\n742 866\nright right\n551\n61 573\nright right\n431\n160 287\nright left\n985\n871 814\nleft right\n73\n-1 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n379\n30 20\nleft left\n977\n606 14\nleft left\n418\n742 866\nright right\n774\n61 115\nright right\n315\n309 287\nright left\n985\n871 814\nleft right\n73\n1 70\nright left\n880\n475 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n857 92\nleft left\n874\n742 334\nright right\n774\n61 573\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n0 45\nright left\n880\n283 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n15 20\nleft left\n977\n583 92\nleft left\n874\n742 866\nright right\n649\n61 573\nright right\n431\n160 287\nright left\n985\n871 814\nleft right\n73\n-1 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n634\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n197 92\nleft left\n1561\n742 866\nright right\n934\n61 573\nright right\n404\n160 287\nright left\n1873\n688 277\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n78 20\nleft left\n977\n629 92\nleft left\n874\n27 866\nright right\n1257\n61 573\nright right\n414\n222 287\nright left\n1551\n871 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n232 376\nright left\n", "10\n68\n41 20\nleft left\n977\n606 14\nleft left\n246\n742 866\nright right\n774\n61 115\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n1 70\nright left\n880\n475 535\nright left\n842\n457 592\nright left\n599\n271 542\nright left\n", "10\n429\n46 20\nleft left\n1085\n583 92\nleft left\n634\n742 866\nright right\n774\n61 573\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n-1 45\nright left\n880\n358 535\nright left\n842\n530 592\nright left\n599\n509 542\nright left\n", "10\n684\n64 20\nleft left\n977\n606 92\nleft left\n874\n224 866\nright right\n774\n61 573\nright right\n315\n160 287\nright left\n1873\n871 338\nleft right\n73\n0 45\nright left\n880\n358 380\nright left\n842\n457 592\nright left\n800\n509 542\nright left\n", "10\n684\n57 20\nleft left\n977\n606 92\nleft left\n874\n742 866\nright right\n377\n61 573\nright right\n315\n160 287\nright left\n1873\n871 338\nleft right\n73\n0 44\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n800\n509 542\nright left\n", "10\n429\n41 0\nleft left\n977\n606 92\nleft left\n874\n742 866\nright right\n774\n76 115\nright right\n315\n160 287\nright left\n1898\n871 814\nleft right\n73\n1 45\nright left\n880\n143 535\nright left\n842\n457 1132\nright left\n1098\n509 542\nright left\n", "10\n379\n41 20\nleft left\n977\n606 14\nleft left\n874\n13 866\nright right\n774\n61 115\nright right\n277\n160 287\nright left\n985\n871 814\nleft right\n73\n1 70\nright left\n880\n475 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n857 92\nleft left\n874\n742 334\nright right\n774\n61 573\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n0 45\nright left\n880\n200 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n78 0\nleft left\n977\n606 92\nleft left\n874\n742 866\nright right\n774\n76 115\nright right\n315\n160 287\nright left\n1898\n871 814\nleft right\n73\n1 45\nright left\n880\n143 535\nright left\n842\n457 1132\nright left\n1098\n509 542\nright left\n", "10\n429\n8 20\nleft left\n977\n14 92\nleft left\n874\n96 1179\nright right\n774\n43 573\nright right\n315\n177 287\nright left\n3332\n871 338\nleft right\n73\n1 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n800\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n685 92\nleft left\n874\n742 942\nright right\n861\n61 115\nright right\n315\n160 287\nright left\n1068\n871 814\nleft right\n73\n0 59\nright left\n880\n358 535\nright left\n706\n457 592\nright left\n1135\n509 542\nright left\n", "10\n429\n78 31\nleft left\n977\n629 92\nleft left\n874\n27 866\nright right\n1257\n61 573\nright right\n414\n222 287\nright left\n1551\n871 814\nleft right\n114\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n232 376\nright left\n", "10\n429\n62 0\nleft left\n977\n606 92\nleft left\n874\n742 796\nright right\n774\n61 115\nright right\n315\n160 287\nright left\n2049\n871 814\nleft right\n73\n1 45\nright left\n880\n358 548\nright left\n842\n457 1132\nright left\n1098\n732 542\nright left\n", "10\n429\n46 12\nleft left\n977\n606 92\nleft left\n874\n742 822\nright right\n774\n61 187\nright right\n315\n160 33\nright left\n985\n871 709\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n685 92\nleft left\n874\n742 942\nright right\n861\n61 115\nright right\n315\n160 287\nright left\n1068\n871 814\nleft right\n73\n0 59\nright left\n880\n358 535\nright left\n706\n457 592\nright left\n1135\n641 542\nright left\n", "10\n429\n78 31\nleft left\n977\n629 92\nleft left\n874\n27 866\nright right\n1257\n61 573\nright right\n414\n222 350\nright left\n1551\n871 814\nleft right\n114\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n232 376\nright left\n", "10\n429\n41 30\nleft left\n977\n606 92\nleft left\n874\n742 866\nright right\n2410\n29 115\nright right\n315\n160 287\nright left\n985\n937 814\nleft right\n73\n-1 47\nright left\n880\n358 535\nright left\n955\n457 592\nright left\n599\n509 542\nright left\n", "10\n68\n41 20\nleft left\n977\n606 14\nleft left\n246\n742 866\nright right\n774\n61 56\nright right\n315\n160 287\nright left\n985\n354 814\nleft right\n122\n1 70\nright left\n880\n475 315\nright left\n842\n457 592\nright left\n599\n271 542\nright left\n", "10\n429\n41 20\nleft left\n977\n685 92\nleft left\n874\n742 942\nright right\n861\n19 115\nright right\n315\n160 287\nright left\n1068\n871 814\nleft right\n73\n0 59\nright left\n880\n358 535\nright left\n706\n108 592\nright left\n1135\n641 542\nright left\n", "10\n429\n41 20\nleft left\n977\n691 92\nleft left\n874\n742 866\nright right\n774\n54 115\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n46 20\nleft left\n719\n583 92\nleft left\n874\n742 866\nright right\n774\n61 573\nright right\n431\n160 287\nright left\n985\n871 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n372 92\nleft left\n874\n27 866\nright right\n774\n61 573\nright right\n414\n160 287\nright left\n2156\n871 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n232 542\nright left\n", "10\n429\n41 20\nleft left\n977\n691 92\nleft left\n1707\n742 1432\nright right\n774\n61 162\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n0 42\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n606 92\nleft left\n874\n742 866\nright right\n774\n61 573\nright right\n315\n177 287\nright left\n1873\n871 338\nleft right\n73\n0 45\nright left\n880\n423 535\nright left\n842\n457 592\nright left\n800\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n606 92\nleft left\n874\n742 866\nright right\n774\n43 573\nright right\n315\n177 287\nright left\n1873\n871 338\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n800\n509 1027\nright left\n", "10\n429\n46 28\nleft left\n977\n583 92\nleft left\n874\n742 866\nright right\n551\n61 573\nright right\n431\n157 287\nright left\n985\n871 814\nleft right\n73\n-1 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n180\n41 20\nleft left\n977\n857 92\nleft left\n874\n742 866\nright right\n774\n61 573\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n606 92\nleft left\n874\n742 866\nright right\n774\n43 573\nright right\n315\n177 287\nright left\n2573\n871 338\nleft right\n73\n0 51\nright left\n880\n358 535\nright left\n842\n457 527\nright left\n800\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n606 92\nleft left\n874\n742 866\nright right\n861\n61 115\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n0 50\nright left\n880\n358 535\nright left\n706\n457 567\nright left\n1135\n509 542\nright left\n", "10\n300\n44 20\nleft left\n1253\n197 92\nleft left\n874\n742 866\nright right\n934\n61 573\nright right\n315\n160 287\nright left\n1873\n871 158\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 0\nleft left\n977\n606 92\nleft left\n874\n742 866\nright right\n774\n61 115\nright right\n315\n160 287\nright left\n1898\n1542 814\nleft right\n73\n1 45\nright left\n880\n358 535\nright left\n842\n457 1132\nright left\n599\n509 542\nright left\n", "10\n684\n57 20\nleft left\n977\n606 92\nleft left\n874\n742 866\nright right\n774\n61 573\nright right\n315\n135 287\nright left\n1873\n871 338\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n800\n509 542\nright left\n", "10\n429\n78 20\nleft left\n977\n413 92\nleft left\n874\n27 866\nright right\n1257\n61 573\nright right\n414\n284 287\nright left\n1551\n871 814\nleft right\n73\n0 70\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n232 542\nright left\n", "10\n429\n41 20\nleft left\n977\n14 92\nleft left\n1174\n50 866\nright right\n774\n43 573\nright right\n315\n177 287\nright left\n3332\n871 338\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n800\n509 542\nright left\n", "10\n300\n41 20\nleft left\n426\n197 92\nleft left\n874\n742 637\nright right\n934\n61 573\nright right\n315\n160 287\nright left\n1873\n871 158\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n3 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n14 92\nleft left\n874\n96 866\nright right\n774\n43 573\nright right\n315\n177 287\nright left\n3332\n871 338\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 569\nright left\n800\n509 542\nright left\n", "10\n429\n41 20\nleft left\n930\n823 92\nleft left\n874\n60 938\nright right\n774\n121 573\nright right\n315\n46 287\nright left\n985\n47 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 264\nright left\n599\n532 542\nright left\n", "10\n300\n41 20\nleft left\n1253\n197 92\nleft left\n874\n742 637\nright right\n934\n92 573\nright right\n315\n160 287\nright left\n1684\n871 23\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n3 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n606 92\nleft left\n874\n3 866\nright right\n774\n61 573\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n118 542\nright left\n", "10\n429\n41 20\nleft left\n977\n606 92\nleft left\n874\n742 866\nright right\n1398\n61 115\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n2 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n74 20\nleft left\n977\n606 92\nleft left\n874\n742 866\nright right\n774\n61 573\nright right\n315\n160 287\nright left\n3418\n871 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n691 92\nleft left\n1707\n742 866\nright right\n774\n61 162\nright right\n315\n160 287\nright left\n2598\n871 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n164\n41 20\nleft left\n977\n691 92\nleft left\n1707\n742 1432\nright right\n774\n61 162\nright right\n315\n160 287\nright left\n1422\n871 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n46 20\nleft left\n977\n583 92\nleft left\n490\n742 866\nright right\n551\n82 573\nright right\n431\n160 287\nright left\n985\n871 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n623\n41 20\nleft left\n977\n372 103\nleft left\n874\n27 866\nright right\n774\n61 573\nright right\n811\n160 287\nright left\n985\n871 814\nleft right\n73\n0 45\nright left\n880\n358 146\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n684\n64 20\nleft left\n977\n606 92\nleft left\n874\n179 866\nright right\n774\n61 573\nright right\n315\n160 287\nright left\n1873\n871 338\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n800\n509 542\nright left\n", "10\n429\n46 28\nleft left\n977\n583 92\nleft left\n874\n742 791\nright right\n551\n61 573\nright right\n431\n160 287\nright left\n985\n871 814\nleft right\n73\n-1 45\nright left\n880\n358 940\nright left\n842\n457 592\nright left\n599\n286 542\nright left\n", "10\n684\n57 20\nleft left\n977\n606 92\nleft left\n874\n742 866\nright right\n377\n61 573\nright right\n315\n160 287\nright left\n1873\n871 338\nleft right\n73\n0 45\nright left\n880\n358 802\nright left\n842\n457 592\nright left\n800\n509 542\nright left\n", "10\n300\n41 20\nleft left\n1253\n197 92\nleft left\n141\n742 637\nright right\n934\n61 573\nright right\n315\n160 287\nright left\n1873\n871 158\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n3 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 13\nleft left\n977\n14 92\nleft left\n874\n96 866\nright right\n774\n43 573\nright right\n315\n177 287\nright left\n3332\n871 338\nleft right\n73\n1 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n800\n509 542\nright left\n", "10\n429\n41 20\nleft left\n930\n823 35\nleft left\n874\n60 938\nright right\n774\n121 573\nright right\n315\n46 287\nright left\n985\n47 814\nleft right\n111\n0 45\nright left\n880\n358 535\nright left\n842\n457 264\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n823 92\nleft left\n874\n46 866\nright right\n774\n98 573\nright right\n315\n160 287\nright left\n985\n47 814\nleft right\n73\n0 45\nright left\n1711\n666 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n379\n41 20\nleft left\n977\n606 14\nleft left\n874\n48 866\nright right\n1172\n61 115\nright right\n277\n160 287\nright left\n985\n871 814\nleft right\n73\n1 70\nright left\n880\n475 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n606 92\nleft left\n874\n742 866\nright right\n774\n43 573\nright right\n315\n177 287\nright left\n1873\n1342 338\nleft right\n73\n0 51\nright left\n880\n358 535\nright left\n842\n463 592\nright left\n800\n509 799\nright left\n", "10\n429\n41 20\nleft left\n977\n372 88\nleft left\n874\n27 925\nright right\n774\n61 573\nright right\n414\n160 287\nright left\n985\n871 814\nleft right\n73\n0 45\nright left\n880\n358 167\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n685 92\nleft left\n874\n742 866\nright right\n861\n61 115\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n0 59\nright left\n880\n358 474\nright left\n706\n457 592\nright left\n1135\n509 542\nright left\n", "10\n429\n78 19\nleft left\n977\n372 92\nleft left\n874\n27 866\nright right\n1257\n61 573\nright right\n414\n82 287\nright left\n1551\n871 1316\nleft right\n73\n0 70\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n232 542\nright left\n", "10\n429\n41 1\nleft left\n977\n606 92\nleft left\n874\n742 866\nright right\n1233\n61 115\nright right\n315\n160 287\nright left\n985\n937 814\nleft right\n73\n-1 47\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n684\n57 20\nleft left\n977\n606 92\nleft left\n874\n742 866\nright right\n377\n61 573\nright right\n315\n160 287\nright left\n1873\n871 338\nleft right\n73\n0 44\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n800\n509 36\nright left\n", "10\n300\n41 20\nleft left\n1253\n197 92\nleft left\n874\n742 637\nright right\n934\n162 573\nright right\n315\n160 287\nright left\n1684\n871 158\nleft right\n73\n0 45\nright left\n880\n358 640\nright left\n842\n3 592\nright left\n1014\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n361 92\nleft left\n874\n742 438\nright right\n350\n61 115\nright right\n315\n10 287\nright left\n985\n871 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n706\n457 592\nright left\n599\n509 542\nright left\n", "10\n379\n41 20\nleft left\n977\n606 14\nleft left\n874\n13 866\nright right\n774\n61 115\nright right\n277\n160 287\nright left\n985\n871 814\nleft right\n73\n1 70\nright left\n880\n475 535\nright left\n842\n457 592\nright left\n599\n509 384\nright left\n", "10\n429\n41 20\nleft left\n977\n685 92\nleft left\n874\n742 942\nright right\n861\n61 115\nright right\n315\n160 287\nright left\n872\n871 814\nleft right\n73\n0 59\nright left\n880\n358 535\nright left\n706\n457 592\nright left\n1135\n509 542\nright left\n", "10\n429\n46 12\nleft left\n977\n606 92\nleft left\n874\n742 822\nright right\n774\n61 187\nright right\n315\n160 33\nright left\n985\n871 814\nleft right\n73\n0 68\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n685 92\nleft left\n874\n742 942\nright right\n861\n30 115\nright right\n315\n160 287\nright left\n1068\n871 814\nleft right\n73\n0 59\nright left\n880\n358 535\nright left\n706\n457 592\nright left\n1135\n509 542\nright left\n", "10\n429\n78 31\nleft left\n977\n629 92\nleft left\n874\n27 866\nright right\n1935\n61 573\nright right\n414\n222 287\nright left\n1551\n871 814\nleft right\n114\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n232 376\nright left\n", "10\n68\n41 20\nleft left\n977\n606 5\nleft left\n246\n742 866\nright right\n774\n61 56\nright right\n315\n160 287\nright left\n985\n354 814\nleft right\n73\n1 70\nright left\n880\n475 535\nright left\n842\n457 592\nright left\n599\n271 542\nright left\n", "10\n684\n64 20\nleft left\n1403\n1204 92\nleft left\n874\n224 866\nright right\n774\n61 573\nright right\n315\n160 287\nright left\n1873\n871 338\nleft right\n73\n-1 45\nright left\n880\n358 380\nright left\n842\n457 592\nright left\n800\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n685 92\nleft left\n874\n742 942\nright right\n861\n19 115\nright right\n315\n241 287\nright left\n1068\n871 814\nleft right\n73\n0 59\nright left\n880\n358 535\nright left\n706\n457 592\nright left\n1135\n641 542\nright left\n", "10\n68\n41 20\nleft left\n977\n606 14\nleft left\n246\n742 866\nright right\n774\n61 56\nright right\n315\n129 287\nright left\n985\n354 814\nleft right\n122\n1 70\nright left\n880\n475 315\nright left\n842\n457 592\nright left\n599\n271 542\nright left\n", "10\n429\n55 20\nleft left\n977\n606 92\nleft left\n1591\n742 866\nright right\n774\n61 115\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n1 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n34 20\nleft left\n977\n372 92\nleft left\n874\n27 866\nright right\n774\n61 573\nright right\n414\n43 287\nright left\n1551\n871 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n565 592\nright left\n599\n509 542\nright left\n", "10\n429\n46 20\nleft left\n642\n583 92\nleft left\n874\n742 866\nright right\n551\n61 573\nright right\n644\n160 287\nright left\n985\n871 814\nleft right\n73\n-1 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n379\n41 20\nleft left\n977\n606 14\nleft left\n814\n742 866\nright right\n774\n61 115\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n1 70\nright left\n880\n475 535\nright left\n926\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n606 92\nleft left\n1303\n742 806\nright right\n774\n61 115\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n-1 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n606 17\nleft left\n874\n742 866\nright right\n774\n61 956\nright right\n382\n160 287\nright left\n1873\n871 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n800\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n197 92\nleft left\n874\n742 866\nright right\n774\n61 573\nright right\n315\n160 287\nright left\n1873\n1476 277\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n1670\n248 592\nright left\n599\n509 542\nright left\n", "10\n429\n7 20\nleft left\n977\n14 92\nleft left\n874\n96 866\nright right\n774\n43 573\nright right\n315\n177 287\nright left\n3332\n871 338\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 569\nright left\n800\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n606 92\nleft left\n874\n742 866\nright right\n1398\n61 115\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n2 45\nright left\n880\n358 535\nright left\n842\n46 592\nright left\n599\n509 542\nright left\n", "10\n429\n41 20\nleft left\n977\n361 92\nleft left\n874\n742 521\nright right\n861\n61 115\nright right\n315\n160 287\nright left\n1496\n871 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n706\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n46 14\nleft left\n1407\n583 92\nleft left\n874\n742 866\nright right\n551\n61 573\nright right\n431\n160 287\nright left\n985\n799 814\nleft right\n73\n-1 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n46 20\nleft left\n1043\n583 92\nleft left\n490\n742 866\nright right\n551\n82 573\nright right\n431\n160 287\nright left\n985\n871 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n46 20\nleft left\n1085\n583 7\nleft left\n874\n742 866\nright right\n774\n61 573\nright right\n315\n160 287\nright left\n985\n871 814\nleft right\n73\n-1 45\nright left\n1273\n358 535\nright left\n842\n530 592\nright left\n599\n509 542\nright left\n", "10\n429\n24 20\nleft left\n930\n823 92\nleft left\n874\n46 938\nright right\n774\n61 573\nright right\n315\n160 287\nright left\n985\n47 814\nleft right\n73\n0 45\nright left\n880\n358 535\nright left\n842\n457 264\nright left\n599\n456 542\nright left\n", "10\n684\n57 5\nleft left\n977\n606 92\nleft left\n874\n742 866\nright right\n377\n61 573\nright right\n315\n160 287\nright left\n1873\n871 338\nleft right\n73\n0 45\nright left\n880\n358 802\nright left\n842\n457 592\nright left\n800\n509 542\nright left\n", "10\n429\n41 13\nleft left\n977\n14 92\nleft left\n874\n96 866\nright right\n774\n60 573\nright right\n315\n177 287\nright left\n3332\n871 338\nleft right\n73\n1 45\nright left\n880\n358 535\nright left\n842\n457 592\nright left\n800\n509 542\nright left\n", "10\n429\n41 27\nleft left\n977\n606 114\nleft left\n874\n742 866\nright right\n203\n61 115\nright right\n462\n160 287\nright left\n985\n871 814\nleft right\n73\n1 70\nright left\n880\n290 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "10\n429\n58 20\nleft left\n977\n823 92\nleft left\n874\n46 866\nright right\n774\n98 573\nright right\n315\n160 287\nright left\n985\n47 814\nleft right\n73\n0 45\nright left\n1711\n666 535\nright left\n842\n457 592\nright left\n599\n509 542\nright left\n", "1\n4\n0 1\nleft right\n"], "outputs": ["428\n0\n873\n773\n0\n984\n0\n0\n0\n0\n", "428\n0\n0\n773\n0\n984\n0\n0\n0\n0\n", "428\n0\n873\n773\n0\n984\n0\n0\n0\n0\n", "428\n0\n873\n773\n0\n984\n72\n0\n0\n0\n", "0\n0\n873\n773\n0\n984\n0\n0\n0\n0\n", "0\n0\n873\n773\n0\n984\n0\n0\n0\n598\n", "428\n0\n0\n773\n0\n0\n0\n0\n0\n0\n", "428\n976\n873\n773\n0\n984\n0\n0\n0\n0\n", "428\n0\n873\n773\n0\n1872\n0\n0\n0\n0\n", "0\n976\n873\n773\n0\n984\n0\n0\n0\n0\n", "428\n976\n1706\n773\n0\n984\n0\n0\n0\n0\n", "428\n0\n0\n773\n0\n1550\n0\n0\n0\n0\n", "428\n0\n873\n773\n0\n0\n0\n0\n0\n0\n", "428\n0\n873\n860\n0\n984\n0\n0\n0\n0\n", "428\n0\n0\n0\n0\n984\n0\n0\n0\n0\n", "378\n0\n873\n773\n0\n984\n0\n0\n0\n0\n", "428\n976\n0\n773\n0\n0\n0\n0\n0\n0\n", "428\n976\n1706\n0\n0\n984\n0\n0\n0\n0\n", "428\n0\n0\n773\n0\n1550\n0\n0\n0\n598\n", "428\n976\n873\n773\n0\n0\n0\n0\n0\n0\n", "0\n0\n873\n773\n314\n984\n0\n0\n0\n0\n", "0\n0\n0\n773\n0\n1550\n0\n0\n0\n0\n", "378\n0\n873\n773\n0\n984\n0\n879\n0\n0\n", "0\n976\n873\n773\n0\n984\n72\n0\n0\n0\n", "0\n0\n0\n773\n0\n1550\n0\n0\n0\n598\n", "428\n976\n873\n933\n0\n0\n0\n0\n0\n0\n", "428\n929\n873\n773\n0\n0\n0\n0\n0\n0\n", "428\n0\n873\n773\n314\n1872\n0\n0\n0\n0\n", "0\n976\n873\n550\n0\n984\n72\n0\n0\n0\n", "428\n1252\n873\n933\n0\n0\n0\n0\n0\n0\n", "378\n0\n1370\n773\n0\n984\n0\n879\n0\n0\n", "378\n0\n417\n773\n0\n984\n0\n879\n0\n0\n", "428\n0\n873\n0\n0\n984\n0\n0\n0\n0\n", "0\n976\n873\n773\n0\n984\n0\n0\n841\n0\n", "428\n976\n0\n773\n0\n0\n0\n0\n0\n598\n", "428\n0\n873\n0\n0\n1872\n0\n0\n0\n0\n", "0\n1832\n873\n773\n0\n984\n0\n0\n0\n0\n", "428\n976\n873\n773\n0\n1872\n0\n0\n0\n0\n", "683\n0\n873\n773\n0\n1872\n0\n0\n0\n0\n", "0\n976\n873\n0\n0\n984\n72\n0\n0\n0\n", "0\n0\n0\n1256\n0\n1550\n0\n0\n0\n598\n", "428\n1252\n873\n933\n0\n1872\n0\n0\n0\n0\n", "378\n0\n245\n773\n0\n984\n0\n879\n0\n0\n", "428\n0\n873\n773\n314\n3331\n0\n0\n0\n0\n", "428\n0\n873\n773\n314\n1872\n0\n0\n841\n0\n", "428\n0\n873\n1232\n0\n984\n72\n0\n0\n0\n", "0\n1084\n873\n773\n0\n984\n0\n0\n841\n0\n", "428\n0\n873\n860\n0\n984\n0\n0\n705\n0\n", "428\n976\n873\n1371\n0\n1872\n0\n0\n0\n0\n", "0\n0\n873\n773\n0\n1872\n0\n0\n0\n0\n", "428\n976\n873\n773\n0\n984\n72\n0\n0\n0\n", "428\n929\n873\n773\n0\n0\n0\n0\n841\n0\n", "0\n0\n0\n1256\n0\n1550\n72\n0\n0\n598\n", "299\n1252\n873\n933\n0\n1872\n0\n0\n0\n0\n", "428\n976\n873\n773\n314\n3331\n0\n0\n0\n0\n", "0\n976\n873\n550\n0\n984\n72\n0\n0\n598\n", "428\n0\n873\n773\n314\n1872\n0\n0\n683\n0\n", "428\n0\n873\n773\n0\n1897\n72\n0\n0\n0\n", "0\n0\n1630\n773\n0\n984\n0\n0\n0\n0\n", "428\n0\n873\n0\n314\n984\n0\n0\n0\n0\n", "428\n1927\n873\n773\n0\n984\n72\n0\n0\n0\n", "428\n0\n873\n773\n0\n1897\n72\n879\n0\n0\n", "299\n1252\n873\n933\n0\n1683\n0\n0\n0\n0\n", "299\n1252\n873\n0\n0\n1683\n0\n0\n0\n0\n", "299\n940\n873\n0\n0\n1683\n0\n0\n0\n0\n", "428\n0\n873\n1397\n0\n984\n72\n0\n0\n0\n", "428\n0\n0\n773\n0\n984\n0\n879\n0\n0\n", "428\n0\n873\n773\n0\n3417\n0\n0\n0\n0\n", "0\n720\n873\n773\n0\n984\n0\n0\n0\n0\n", "428\n0\n0\n773\n413\n1550\n0\n0\n0\n0\n", "428\n976\n873\n860\n0\n984\n0\n0\n0\n0\n", "0\n0\n873\n773\n0\n0\n0\n0\n0\n0\n", "691\n0\n0\n773\n0\n1550\n0\n0\n0\n0\n", "0\n0\n0\n0\n0\n984\n0\n0\n0\n0\n", "428\n0\n873\n202\n0\n984\n0\n0\n0\n0\n", "428\n976\n1706\n0\n0\n1465\n0\n0\n0\n0\n", "428\n976\n873\n773\n0\n0\n0\n879\n0\n0\n", "0\n0\n873\n773\n0\n984\n72\n0\n0\n0\n", "163\n976\n1706\n0\n0\n984\n0\n0\n0\n0\n", "0\n1406\n873\n550\n0\n984\n72\n0\n0\n0\n", "0\n0\n0\n773\n0\n1550\n72\n0\n0\n598\n", "428\n1252\n873\n933\n0\n0\n0\n0\n0\n598\n", "428\n0\n873\n773\n314\n0\n0\n0\n0\n0\n", "428\n976\n873\n773\n0\n984\n0\n879\n0\n0\n", "428\n0\n0\n773\n0\n984\n72\n0\n0\n0\n", "0\n0\n873\n773\n314\n984\n0\n879\n0\n0\n", "683\n0\n873\n0\n0\n1872\n0\n0\n0\n0\n", "428\n976\n873\n933\n0\n1872\n0\n0\n0\n0\n", "428\n929\n873\n773\n0\n0\n0\n879\n0\n0\n", "0\n976\n489\n0\n0\n984\n72\n0\n0\n0\n", "671\n0\n873\n1232\n0\n984\n72\n0\n0\n0\n", "428\n0\n873\n773\n314\n984\n72\n0\n0\n0\n", "622\n0\n0\n773\n0\n984\n0\n0\n0\n0\n", "0\n1084\n873\n773\n0\n984\n72\n0\n841\n0\n", "0\n929\n873\n773\n0\n0\n0\n0\n841\n0\n", "0\n0\n0\n1256\n0\n0\n72\n0\n0\n598\n", "0\n976\n873\n550\n0\n984\n72\n879\n0\n598\n", "683\n0\n873\n376\n0\n1872\n0\n0\n0\n0\n", "428\n976\n0\n773\n314\n3331\n0\n0\n0\n0\n", "428\n0\n873\n0\n0\n1897\n72\n0\n0\n0\n", "299\n1252\n359\n933\n0\n1872\n0\n0\n0\n0\n", "428\n976\n873\n773\n314\n3331\n72\n0\n0\n0\n", "428\n0\n873\n773\n0\n2048\n72\n879\n0\n0\n", "299\n1252\n873\n933\n314\n1683\n0\n0\n0\n0\n", "299\n940\n873\n0\n314\n1683\n0\n0\n0\n0\n", "709\n0\n0\n773\n0\n984\n0\n879\n0\n0\n", "428\n976\n0\n860\n0\n984\n0\n0\n0\n0\n", "428\n976\n873\n0\n0\n0\n0\n879\n0\n0\n", "428\n1406\n873\n550\n0\n984\n72\n0\n0\n0\n", "0\n0\n417\n773\n0\n984\n0\n879\n0\n0\n", "428\n976\n0\n773\n0\n984\n0\n879\n0\n0\n", "0\n976\n873\n648\n0\n984\n72\n0\n0\n0\n", "428\n976\n1560\n933\n0\n1872\n0\n0\n0\n0\n", "0\n976\n0\n1256\n0\n1550\n0\n0\n0\n598\n", "67\n0\n245\n773\n0\n984\n0\n879\n0\n0\n", "0\n1084\n633\n773\n0\n984\n72\n0\n841\n0\n", "0\n0\n873\n773\n0\n1872\n0\n879\n0\n0\n", "683\n0\n873\n376\n0\n1872\n72\n0\n0\n0\n", "428\n0\n873\n0\n0\n1897\n72\n879\n0\n0\n", "378\n0\n0\n773\n0\n984\n0\n879\n0\n0\n", "428\n976\n0\n773\n0\n984\n0\n0\n0\n0\n", "0\n0\n873\n0\n0\n1897\n72\n879\n0\n0\n", "428\n976\n0\n773\n314\n3331\n72\n0\n0\n0\n", "428\n976\n873\n860\n0\n1067\n0\n0\n0\n0\n", "428\n976\n0\n1256\n0\n1550\n0\n0\n0\n598\n", "0\n0\n873\n773\n0\n2048\n72\n879\n0\n0\n", "0\n0\n873\n773\n314\n0\n0\n0\n0\n0\n", "428\n976\n873\n860\n0\n1067\n0\n0\n0\n1134\n", "428\n976\n0\n1256\n413\n1550\n0\n0\n0\n598\n", "428\n0\n873\n2409\n0\n984\n72\n0\n0\n0\n", "67\n0\n245\n773\n0\n984\n0\n0\n0\n0\n", "428\n976\n873\n860\n0\n1067\n0\n0\n705\n1134\n", "428\n976\n873\n0\n0\n984\n0\n0\n0\n0\n", "0\n718\n873\n773\n0\n984\n0\n0\n0\n0\n", "428\n0\n0\n773\n0\n2155\n0\n0\n0\n598\n", "428\n976\n1706\n0\n0\n984\n72\n0\n0\n0\n", "428\n0\n873\n773\n314\n1872\n0\n879\n0\n0\n", "428\n0\n873\n773\n314\n1872\n0\n0\n0\n799\n", "0\n976\n873\n550\n430\n984\n72\n0\n0\n0\n", "179\n976\n873\n773\n0\n984\n0\n0\n0\n0\n", "428\n0\n873\n773\n314\n2572\n0\n0\n841\n0\n", "428\n0\n873\n860\n0\n984\n72\n0\n705\n0\n", "0\n1252\n873\n933\n0\n1872\n0\n0\n0\n0\n", "428\n0\n873\n773\n0\n0\n72\n0\n0\n0\n", "683\n0\n873\n773\n314\n1872\n0\n0\n0\n0\n", "0\n976\n0\n1256\n0\n1550\n72\n0\n0\n598\n", "428\n976\n1173\n773\n314\n3331\n0\n0\n0\n0\n", "299\n425\n873\n933\n0\n1872\n0\n0\n0\n0\n", "428\n976\n873\n773\n314\n3331\n0\n0\n841\n0\n", "428\n929\n873\n773\n0\n0\n0\n0\n841\n598\n", "299\n1252\n873\n0\n0\n0\n0\n0\n0\n0\n", "428\n0\n0\n773\n0\n984\n0\n0\n0\n598\n", "428\n0\n873\n1397\n0\n984\n0\n0\n0\n0\n", "0\n0\n873\n773\n0\n3417\n0\n0\n0\n0\n", "428\n976\n1706\n0\n0\n2597\n0\n0\n0\n0\n", "163\n976\n1706\n0\n0\n1421\n0\n0\n0\n0\n", "0\n976\n489\n0\n0\n984\n0\n0\n0\n0\n", "622\n976\n0\n773\n0\n984\n0\n0\n0\n0\n", "0\n0\n0\n773\n0\n1872\n0\n0\n0\n0\n", "0\n976\n0\n550\n0\n984\n72\n879\n0\n598\n", "683\n0\n873\n376\n0\n1872\n0\n879\n0\n0\n", "299\n1252\n140\n933\n0\n1872\n0\n0\n0\n0\n", "0\n976\n873\n773\n314\n3331\n72\n0\n0\n0\n", "428\n0\n873\n773\n0\n0\n0\n0\n841\n0\n", "428\n976\n873\n0\n0\n0\n0\n1710\n0\n0\n", "378\n0\n873\n1171\n0\n984\n0\n879\n0\n0\n", "428\n0\n873\n773\n314\n0\n0\n0\n0\n799\n", "428\n0\n873\n773\n0\n984\n0\n879\n0\n0\n", "428\n976\n873\n860\n0\n984\n0\n879\n0\n0\n", "428\n0\n0\n1256\n0\n0\n72\n0\n0\n598\n", "0\n0\n873\n1232\n0\n984\n72\n0\n0\n0\n", "683\n0\n873\n376\n0\n1872\n72\n0\n0\n799\n", "299\n1252\n873\n0\n0\n1683\n0\n879\n0\n0\n", "428\n976\n0\n349\n0\n984\n0\n0\n0\n0\n", "378\n0\n0\n773\n0\n984\n0\n879\n0\n598\n", "428\n976\n873\n860\n0\n871\n0\n0\n0\n0\n", "0\n0\n873\n773\n314\n984\n72\n0\n0\n0\n", "428\n976\n873\n0\n0\n1067\n0\n0\n0\n0\n", "428\n976\n0\n1934\n0\n1550\n0\n0\n0\n598\n", "67\n976\n245\n773\n0\n984\n0\n879\n0\n0\n", "0\n0\n873\n773\n0\n1872\n72\n879\n0\n0\n", "428\n976\n873\n860\n314\n1067\n0\n0\n0\n1134\n", "67\n0\n245\n773\n314\n984\n0\n0\n0\n0\n", "428\n0\n1590\n773\n0\n984\n72\n0\n0\n0\n", "0\n0\n0\n773\n413\n1550\n0\n0\n0\n0\n", "0\n641\n873\n550\n0\n984\n72\n0\n0\n0\n", "378\n0\n813\n773\n0\n984\n0\n879\n0\n0\n", "428\n0\n1302\n773\n0\n984\n72\n0\n0\n0\n", "428\n976\n873\n0\n0\n1872\n0\n0\n0\n0\n", "428\n976\n873\n773\n0\n1872\n0\n0\n1669\n0\n", "0\n976\n873\n773\n314\n3331\n0\n0\n841\n0\n", "428\n0\n873\n1397\n0\n984\n0\n0\n841\n0\n", "428\n976\n873\n860\n0\n1495\n0\n0\n0\n0\n", "0\n1406\n873\n550\n0\n0\n72\n0\n0\n0\n", "0\n1042\n489\n0\n0\n984\n0\n0\n0\n0\n", "0\n0\n873\n773\n0\n984\n72\n0\n841\n0\n", "0\n929\n873\n773\n0\n0\n0\n0\n841\n598\n", "0\n0\n873\n376\n0\n1872\n0\n879\n0\n0\n", "0\n976\n873\n0\n314\n3331\n72\n0\n0\n0\n", "0\n0\n873\n202\n0\n984\n0\n0\n0\n0\n", "0\n976\n873\n0\n0\n0\n0\n1710\n0\n0\n", "0\n"]}

source: codeforces

sample_tests: {"inputs": ["1\n4\n0 1\nleft right"], "outputs": ["0"]}

raw_problem:
B. Restaurant Game

time limit per test
1 second

memory limit per test
256 megabytes

input
standard input

output
standard output

Alice and Bob always had hard time choosing restaurant for the dinner. Previously they performed Eenie Meenie Miney Mo game, but eventually as their restaurant list grew, they had to create a new game. This new game starts as they write restaurant names on $$$N$$$ cards and align the cards in one line. Before the game begins, they both choose starting card and starting direction they are going to. They take turns in order one after another. After each turn, they move one card in their current direction. If they reach the end or beginning of the line of cards they change direction. Once they meet in a card, the card is marked for removal and is removed the first moment they both leave the card.
  Example of how card is removed
They repeat this process until there is only one restaurant card left. Since there are a lot of restaurant cards, they are bored to simulate this process over and over and need your help to determine the last card that remains. Can you help them?

Input

The first line of the input is one integer $$$T$$$ ($$$1$$$ $$$\leq$$$ $$$T$$$ $$$\leq$$$ $$$10^{4}$$$) representing number of test cases. Each test case contains 3 lines: The first line contains an integer $$$N$$$ representing initial number of cards. Next line contains two integer values $$$A,B$$$ ($$$0$$$ $$$\leq$$$ $$$A, B$$$ < $$$N$$$, $$$2$$$ $$$\leq$$$ $$$N$$$ $$$\leq$$$ $$$10^{18}$$$) representing starting 0-based index of the card in the array. Last line contains two strings $$$D_A, D_B$$$ $$$\in$$$ {"left", "right"} representing starting direction of their movement.

Output

The output contains $$$T$$$ integer number – the 0-based index of the last card that remains for every test case in order.

Example

Input

1
4
0 1
left right

Output

0

Note

Note that since Alice is starting at the beginning of the line even though her initial direction is left, on her next move she will go right.

question:
Alice and Bob always had hard time choosing restaurant for the dinner. Previously they performed Eenie Meenie Miney Mo game, but eventually as their restaurant list grew, they had to create a new game. This new game starts as they write restaurant names on $$$N$$$ cards and align the cards in one line. Before the game begins, they both choose starting card and starting direction they are going to. They take turns in order one after another. After each turn, they move one card in their current direction. If they reach the end or beginning of the line of cards they change direction. Once they meet in a card, the card is marked for removal and is removed the first moment they both leave the card.
 ![image](1.png) Example of how card is removed They repeat this process until there is only one restaurant card left. Since there are a lot of restaurant cards, they are bored to simulate this process over and over and need your help to determine the last card that remains. Can you help them?

Input
The first line of the input is one integer $$$T$$$ ($$$1$$$ $$$\leq$$$ $$$T$$$ $$$\leq$$$ $$$10^{4}$$$) representing number of test cases. Each test case contains 3 lines: The first line contains an integer $$$N$$$ representing initial number of cards. Next line contains two integer values $$$A,B$$$ ($$$0$$$ $$$\leq$$$ $$$A, B$$$ < $$$N$$$, $$$2$$$ $$$\leq$$$ $$$N$$$ $$$\leq$$$ $$$10^{18}$$$) representing starting 0-based index of the card in the array. Last line contains two strings $$$D_A, D_B$$$ $$$\in$$$ {"left", "right"} representing starting direction of their movement.

Output
The output contains $$$T$$$ integer number – the 0-based index of the last card that remains for every test case in order.

Example
Input
1
4
0 1
left right

Output
0

Note
Note that since Alice is starting at the beginning of the line even though her initial direction is left, on her next move she will go right.

data_split: test


D. DevOps Best Practices

problem_index: D

time_limit: 3 seconds

memory_limit: 512 megabytes

note:
CD/CT system for the first sample test is shown below.
![image](images/cf_1267_D/1.png)

solutions: ["import sys\nfrom functools import reduce\n\ndef impossible():\n\tprint('Impossible')\n\ndef main_proc():\n\tres = []\n\tcnt2resolve = 0\n\tn = int(input())\n\ttarget = [[[], []] for _ in range(8)]\n\ttest = [0 for _ in range(8)]\n\ttest[7] = 1\n\tsrc = [[] for _ in range(0, n + 1)]\n\tct = ['1' for _ in range(0, n + 1)]\n\tinput()\n\tfor i in range(2, n + 1):\n\t\tind = reduce(lambda a, b: (a << 1) + int(b), [int(_) for _ in input().split()])\n\t\tsrc[i].append(ind)\n\t\ttarget[ind][1].append(i)\n\ttarget[0][1] = []\n\tfor x in target:\n\t\tif len(x[1]):\n\t\t\tcnt2resolve += 1\n\tinput()\n\tfor i in range(2, n + 1):\n\t\tind = reduce(lambda a, b: (a << 1) + int(b), [int(_) for _ in input().split()])\n\t\tind &= src[i][0]\n\t\tsrc[i].append(ind)\n\tfor i in (7, 6, 5, 3, 4, 2, 1):\n\t\tif not target[i][0] and target[i][1]:\n\t\t\tfor j in target[i][1]:\n\t\t\t\tif test[src[j][0]]:\n\t\t\t\t\tif not target[i][0]:\n\t\t\t\t\t\ttarget[i][0].append(test[src[j][0]])\n\t\t\t\t\t\tcnt2resolve -= 1\n\t\t\t\t\ttest[src[j][1]] = j\n\tif cnt2resolve:\n\t\tfor i in (6, 5, 3):\n\t\t\tif not target[i][0] and target[i][1]:\n\t\t\t\ttmp = 2\n\t\t\t\tfor j in (4, 2, 1):\n\t\t\t\t\tif j & i:\n\t\t\t\t\t\tif test[j]:\n\t\t\t\t\t\t\tif src[test[j]][0] in (4, 2, 1):\n\t\t\t\t\t\t\t\ttarget[i][0].append(target[src[test[j]][0]][0][0])\n\t\t\t\t\t\t\telse:\n\t\t\t\t\t\t\t\ttarget[i][0].append(test[j])\n\t\t\t\t\t\t\ttmp -= 1\n\t\t\t\tif not tmp:\n\t\t\t\t\tcnt2resolve -= 1\n\tif not cnt2resolve:\n\t\tfor i in range(7, 0, -1):\n\t\t\tfor k in target[i][0]:\n\t\t\t\tif len(target[i][0]) == 2:\n\t\t\t\t\ttt = target[i][1][:1]\n\t\t\t\telse:\n\t\t\t\t\ttt = target[i][1]\n\t\t\t\tfor j in tt:\n\t\t\t\t\tres.append(' '.join((str(k), str(j))))\n\t\t\tif len(target[i][0]) == 2 and len(target[i][1]) > 1:\n\t\t\t\thp = target[i][1][0]\n\t\t\t\tct[hp] = '0'\n\t\t\t\tfor j in target[i][1][1:]:\n\t\t\t\t\tres.append(' '.join((str(hp), str(j))))\n\t\tprint('Possible')\n\t\tprint(' '.join(ct[1:]))\n\t\tprint(len(res))\n\t\tprint('\\n'.join(res))\n\telse:\n\t\tprint('Impossible')\n\treturn\nmain_proc()\n"]

source: codeforces

raw_problem:
D. DevOps Best Practices

time limit per test
3 seconds

memory limit per test
512 megabytes

input
standard input

output
standard output

Daisy is a senior software engineer at RainyDay, LLC. She has just implemented three new features in their product: the first feature makes their product work, the second one makes their product fast, and the third one makes their product correct. The company encourages at least some testing of new features, so Daisy appointed her intern Demid to write some tests for the new features.

Interestingly enough, these three features pass all the tests on Demid's development server, which has index 1, but might fail the tests on some other servers.

After Demid has completed this task, Daisy appointed you to deploy these three features to all $$$n$$$ servers of your company. For every feature $$$f$$$ and every server $$$s$$$, Daisy told you whether she wants the feature $$$f$$$ to be deployed on the server $$$s$$$. If she wants it to be deployed, it must be done even if the feature $$$f$$$ fails the tests on the server $$$s$$$. If she does not want it to be deployed, you may not deploy it there.

Your company has two important instruments for the deployment of new features to servers: Continuous Deployment (CD) and Continuous Testing (CT). CD can be established between several pairs of servers, forming a directed graph. CT can be set up on some set of servers.

If CD is configured from the server $$$s_1$$$ to the server $$$s_2$$$ then every time $$$s_1$$$ receives a new feature $$$f$$$ the system starts the following deployment process of $$$f$$$ to $$$s_2$$$:

 If the feature $$$f$$$ is already deployed on the server $$$s_2$$$, then nothing is done.

 Otherwise, if CT is not set up on the server $$$s_1$$$, then the server $$$s_1$$$ just deploys the feature $$$f$$$ to the server $$$s_2$$$ without any testing.

 Otherwise, the server $$$s_1$$$ runs tests for the feature $$$f$$$. If the tests fail on the server $$$s_1$$$, nothing is done. If the tests pass, then the server $$$s_1$$$ deploys the feature $$$f$$$ to the server $$$s_2$$$.

You are to configure the CD/CT system, and after that Demid will deploy all three features on his development server. Your CD/CT system must deploy each feature exactly to the set of servers that Daisy wants.

Your company does not have a lot of computing resources, so you can establish CD from one server to another at most $$$264$$$ times.

Input

The first line contains integer $$$n$$$ ($$$2 \le n \le 256$$$) — the number of servers in your company.

Next $$$n$$$ lines contain three integers each. The $$$j$$$-th integer in the $$$i$$$-th line is $$$1$$$ if Daisy wants the $$$j$$$-th feature to be deployed to the $$$i$$$-th server, or $$$0$$$ otherwise.

Next $$$n$$$ lines contain three integers each. The $$$j$$$-th integer in the $$$i$$$-th line is $$$1$$$ if tests pass for the $$$j$$$-th feature on the $$$i$$$-th server, or $$$0$$$ otherwise.

Demid's development server has index $$$1$$$. It is guaranteed that Daisy wants all three features to be deployed to the server number 1, and all three features pass their tests on the server number 1.

Output

If it is impossible to configure CD/CT system with CD being set up between at most $$$264$$$ pairs of servers, then output the single line "Impossible".

Otherwise, the first line of the output must contain the line "Possible".

Next line must contain $$$n$$$ space-separated integers — the configuration of CT. The $$$i$$$-th integer should be $$$1$$$ if you set up CT on the $$$i$$$-th server, or $$$0$$$ otherwise.

Next line must contain the integer $$$m$$$ ($$$0 \le m \le 264$$$) — the number of CD pairs you want to set up.

Each of the next $$$m$$$ lines must describe CD configuration, each line with two integers $$$s_i$$$ and $$$t_i$$$ ($$$1 \le s_i, t_i \le n$$$; $$$s_i \ne t_i$$$), establishing automated deployment of new features from the server $$$s_i$$$ to the server $$$t_i$$$.

Examples

Input

3
1 1 1
1 0 1
1 1 1
1 1 1
0 0 0
1 0 1

Output

Possible
1 1 1
2
3 2
1 3

Input

2
1 1 1
0 0 1
1 1 1
1 1 0

Output

Impossible

Note

CD/CT system for the first sample test is shown below.

question:
Daisy is a senior software engineer at RainyDay, LLC. She has just implemented three new features in their product: the first feature makes their product work, the second one makes their product fast, and the third one makes their product correct. The company encourages at least some testing of new features, so Daisy appointed her intern Demid to write some tests for the new features.
Interestingly enough, these three features pass all the tests on Demid's development server, which has index 1, but might fail the tests on some other servers.
After Demid has completed this task, Daisy appointed you to deploy these three features to all $$$n$$$ servers of your company. For every feature $$$f$$$ and every server $$$s$$$, Daisy told you whether she wants the feature $$$f$$$ to be deployed on the server $$$s$$$. If she wants it to be deployed, it must be done even if the feature $$$f$$$ fails the tests on the server $$$s$$$. If she does not want it to be deployed, you may not deploy it there.
Your company has two important instruments for the deployment of new features to servers: Continuous Deployment (CD) and Continuous Testing (CT). CD can be established between several pairs of servers, forming a directed graph. CT can be set up on some set of servers.
If CD is configured from the server $$$s_1$$$ to the server $$$s_2$$$ then every time $$$s_1$$$ receives a new feature $$$f$$$ the system starts the following deployment process of $$$f$$$ to $$$s_2$$$:
 -  If the feature $$$f$$$ is already deployed on the server $$$s_2$$$, then nothing is done. -  Otherwise, if CT is not set up on the server $$$s_1$$$, then the server $$$s_1$$$ just deploys the feature $$$f$$$ to the server $$$s_2$$$ without any testing. -  Otherwise, the server $$$s_1$$$ runs tests for the feature $$$f$$$. If the tests fail on the server $$$s_1$$$, nothing is done. If the tests pass, then the server $$$s_1$$$ deploys the feature $$$f$$$ to the server $$$s_2$$$. You are to configure the CD/CT system, and after that Demid will deploy all three features on his development server. Your CD/CT system must deploy each feature exactly to the set of servers that Daisy wants.
Your company does not have a lot of computing resources, so you can establish CD from one server to another at most $$$264$$$ times.

Input
The first line contains integer $$$n$$$ ($$$2 \le n \le 256$$$) — the number of servers in your company.
Next $$$n$$$ lines contain three integers each. The $$$j$$$-th integer in the $$$i$$$-th line is $$$1$$$ if Daisy wants the $$$j$$$-th feature to be deployed to the $$$i$$$-th server, or $$$0$$$ otherwise.
Next $$$n$$$ lines contain three integers each. The $$$j$$$-th integer in the $$$i$$$-th line is $$$1$$$ if tests pass for the $$$j$$$-th feature on the $$$i$$$-th server, or $$$0$$$ otherwise.
Demid's development server has index $$$1$$$. It is guaranteed that Daisy wants all three features to be deployed to the server number 1, and all three features pass their tests on the server number 1.

Output
If it is impossible to configure CD/CT system with CD being set up between at most $$$264$$$ pairs of servers, then output the single line "Impossible".
Otherwise, the first line of the output must contain the line "Possible".
Next line must contain $$$n$$$ space-separated integers — the configuration of CT. The $$$i$$$-th integer should be $$$1$$$ if you set up CT on the $$$i$$$-th server, or $$$0$$$ otherwise.
Next line must contain the integer $$$m$$$ ($$$0 \le m \le 264$$$) — the number of CD pairs you want to set up.
Each of the next $$$m$$$ lines must describe CD configuration, each line with two integers $$$s_i$$$ and $$$t_i$$$ ($$$1 \le s_i, t_i \le n$$$; $$$s_i \ne t_i$$$), establishing automated deployment of new features from the server $$$s_i$$$ to the server $$$t_i$$$.

Examples
Input
3
1 1 1
1 0 1
1 1 1
1 1 1
0 0 0
1 0 1

Output
Possible
1 1 1
2
3 2
1 3

Input
2
1 1 1
0 0 1
1 1 1
1 1 0

Output
Impossible

Note
CD/CT system for the first sample test is shown below.
 ![image](1.png)

data_split: test


Arranging Wine

difficulty: HARD

source: open kattis

raw_problem:
The host university is organizing a party for this year’s
    ACM/ICPC contestants with a buffet dinner and $R$ boxes of red wine and $W$ boxes of white wine. Wine boxes
    are to be arranged into non-empty piles, each pile contains
    only one type of wine, either white or red. After that, those
    piles are put into a line so that no two piles belonging to the
    same kind sit next to each other. In addition, for security
    reasons, each red wine pile should not have more than
    $d$ boxes of red wine,
    although piles of white wine can be arbitrarily large.

Your task is to identify $K$ - the number of different ways to
    arrange the given wine boxes satisfying all of the above
    conditions.

Input

The input contains $3$
    space separated integers in one line: $R$, $W$, $d$ $(1
    \leq R,W \leq 10^6, 1 \leq d \leq R)$

Output

Write in one line the remainder of $K$ divided by $10^9+7$.

Sample Clarification

In the first sample below, there are $3$ valid arrangements:

In the second sample below, there are $6$ valid arrangements:

Sample Input 1
Sample Output 1

2 2 1

3

Sample Input 2
Sample Output 2

2 2 2

6

question:
The host university is organizing a party for this year’s ACM/ICPC contestants with a buffet dinner and$R$boxes of red wine and$W$boxes of white wine. Wine boxes are to be arranged into non-empty piles, each pile contains only one type of wine, either white or red. After that, those piles are put into a line so that no two piles belonging to the same kind sit next to each other. In addition, for security reasons, each red wine pile should not have more than$d$boxes of red wine, although piles of white wine can be arbitrarily large.
Your task is to identify$K$- the number of different ways to arrange the given wine boxes satisfying all of the above conditions.

Input
The input contains$3$space separated integers in one line:$R$,$W$,$d$$(1 \leq R,W \leq 10^6, 1 \leq d \leq R)$

Output
Write in one line the remainder of$K$divided by$10^9+7$.

Sample Clarification
In the first sample below, there are$3$valid arrangements:
![image](1.png)In the second sample below, there are$6$valid arrangements:
![image](2.png)Sample Input 1
2 2 1

Sample Output 1
3

Sample Input 2
2 2 2

Sample Output 2
6

image_tags: Others Others

data_split: test