vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
This is the hard version of the problem. The difference between the versions is in the number of possible operations that can be made. You can make hacks if and only if you solved both versions of the problem.

You are given a binary table of size n × m. This table consists of symbols 0 and 1.

You can make such operation: select 3 different cells that belong to one 2 × 2 square and change the symbols in these cells (change 0 to 1 and 1 to 0).

Your task is to make all symbols in the table equal to 0. You are allowed to make at most nm operations. You don't need to minimize the number of operations.

It can be proved, that it is always possible.

Input

The first line contains a single integer t (1 ≤ t ≤ 5000) — the number of test cases. The next lines contain descriptions of test cases.

The first line of the description of each test case contains two integers n, m (2 ≤ n, m ≤ 100).

Each of the next n lines contains a binary string of length m, describing the symbols of the next row of the table.

It is guaranteed, that the sum of nm for all test cases does not exceed 20000.

Output

For each test case print the integer k (0 ≤ k ≤ nm) — the number of operations.

In the each of the next k lines print 6 integers x_1, y_1, x_2, y_2, x_3, y_3 (1 ≤ x_1, x_2, x_3 ≤ n, 1 ≤ y_1, y_2, y_3 ≤ m) describing the next operation. This operation will be made with three cells (x_1, y_1), (x_2, y_2), (x_3, y_3). These three cells should be different. These three cells should belong to some 2 × 2 square.

Example

Input


5
2 2
10
11
3 3
011
101
110
4 4
1111
0110
0110
1111
5 5
01011
11001
00010
11011
10000
2 3
011
101


Output


1
1 1 2 1 2 2
2 
2 1 3 1 3 2
1 2 1 3 2 3
4
1 1 1 2 2 2 
1 3 1 4 2 3
3 2 4 1 4 2
3 3 4 3 4 4
4
1 2 2 1 2 2 
1 4 1 5 2 5 
4 1 4 2 5 1
4 4 4 5 3 4
2
1 3 2 2 2 3
1 2 2 1 2 2

Note

In the first test case, it is possible to make only one operation with cells (1, 1), (2, 1), (2, 2). After that, all symbols will be equal to 0.

In the second test case:

  * operation with cells (2, 1), (3, 1), (3, 2). After it the table will be: 
    
          
    011  
    001  
    000  
    

  * operation with cells (1, 2), (1, 3), (2, 3). After it the table will be: 
    
          
    000  
    000  
    000  
    




In the fifth test case:

  * operation with cells (1, 3), (2, 2), (2, 3). After it the table will be: 
    
          
    010  
    110  
    

  * operation with cells (1, 2), (2, 1), (2, 2). After it the table will be: 
    
          
    000  
    000  
    

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Game with Powers

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Vasya and Petya wrote down all integers from 1 to *n* to play the "powers" game (*n* can be quite large; however, Vasya and Petya are not confused by this fact).

Players choose numbers in turn (Vasya chooses first). If some number *x* is chosen at the current turn, it is forbidden to choose *x* or all of its other positive integer powers (that is, *x*2, *x*3, ...) at the next turns. For instance, if the number 9 is chosen at the first turn, one cannot choose 9 or 81 later, while it is still allowed to choose 3 or 27. The one who cannot make a move loses.

Who wins if both Vasya and Petya play optimally?

Input Specification:
Input contains single integer *n* (1<=≤<=*n*<=≤<=109).

Output Specification:
Print the name of the winner — "Vasya" or "Petya" (without quotes).

Demo Input:
['1\n', '2\n', '8\n']

Demo Output:
['Vasya\n', 'Petya\n', 'Petya\n']

Note:
In the first sample Vasya will choose 1 and win immediately.

In the second sample no matter which number Vasya chooses during his first turn, Petya can choose the remaining number and win.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Olympic Medal

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The World Programming Olympics Medal is a metal disk, consisting of two parts: the first part is a ring with outer radius of *r*1 cm, inner radius of *r*2 cm, (0<=&lt;<=*r*2<=&lt;<=*r*1) made of metal with density *p*1 g/cm3. The second part is an inner disk with radius *r*2 cm, it is made of metal with density *p*2 g/cm3. The disk is nested inside the ring.

The Olympic jury decided that *r*1 will take one of possible values of *x*1,<=*x*2,<=...,<=*x**n*. It is up to jury to decide which particular value *r*1 will take. Similarly, the Olympic jury decided that *p*1 will take one of possible value of *y*1,<=*y*2,<=...,<=*y**m*, and *p*2 will take a value from list *z*1,<=*z*2,<=...,<=*z**k*.

According to most ancient traditions the ratio between the outer ring mass *m**out* and the inner disk mass *m**in* must equal , where *A*,<=*B* are constants taken from ancient books. Now, to start making medals, the jury needs to take values for *r*1, *p*1, *p*2 and calculate the suitable value of *r*2.

The jury wants to choose the value that would maximize radius *r*2. Help the jury find the sought value of *r*2. Value *r*2 doesn't have to be an integer.

Medal has a uniform thickness throughout the area, the thickness of the inner disk is the same as the thickness of the outer ring.

Input Specification:
The first input line contains an integer *n* and a sequence of integers *x*1,<=*x*2,<=...,<=*x**n*. The second input line contains an integer *m* and a sequence of integers *y*1,<=*y*2,<=...,<=*y**m*. The third input line contains an integer *k* and a sequence of integers *z*1,<=*z*2,<=...,<=*z**k*. The last line contains two integers *A* and *B*.

All numbers given in the input are positive and do not exceed 5000. Each of the three sequences contains distinct numbers. The numbers in the lines are separated by spaces.

Output Specification:
Print a single real number — the sought value *r*2 with absolute or relative error of at most 10<=-<=6. It is guaranteed that the solution that meets the problem requirements exists.

Demo Input:
['3 1 2 3\n1 2\n3 3 2 1\n1 2\n', '4 2 3 6 4\n2 1 2\n3 10 6 8\n2 1\n']

Demo Output:
['2.683281573000\n', '2.267786838055\n']

Note:
In the first sample the jury should choose the following values: *r*<sub class="lower-index">1</sub> = 3, *p*<sub class="lower-index">1</sub> = 2, *p*<sub class="lower-index">2</sub> = 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Volodya and Vlad play the following game. There are k pies at the cells of n × m board. Each turn Volodya moves one pie to the neighbouring (by side) cell. If the pie lies at the border of the board then Volodya can move it outside the board, get the pie and win. After Volodya's move, Vlad bans some edge at the border of the board of length 1 (between two knots of the board) so that Volodya is not able to move the pie outside the board through this edge anymore. The question is: will Volodya win this game? We suppose both players follow the optimal strategy.

<image>

Input

First line contains 3 integers, separated by space: 1 ≤ n, m ≤ 100 — dimensions of the board and 0 ≤ k ≤ 100 — the number of pies. Each of the next k lines contains 2 integers, separated by space: 1 ≤ x ≤ n, 1 ≤ y ≤ m — coordinates of the corresponding pie. There could be more than one pie at a cell. 

Output

Output only one word: "YES" — if Volodya wins, "NO" — otherwise.

Examples

Input

2 2 1
1 2


Output

YES

Input

3 4 0


Output

NO

Input

100 50 2
50 25
50 25


Output

NO

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Jigar got a sequence of n positive integers as his birthday present! He likes consecutive subsequences whose sum is divisible by k. He asks you to write a program to count them for him.

Input Format 

The first line contains T, the number of testcases. 

T testcases follow. Each testcase consists of 2 lines. 

The first line contains n and k separated by a single space. 

And the second line contains n space separated integers.

Output Format 

For each test case, output the number of consecutive subsequenences whose sum is divisible by k in a newline.

Constraints 

1 ≤ T ≤ 20 

1 ≤ n ≤ 10^{6} 

1 ≤ k ≤ 100 

1 ≤ a[i] ≤ 10^{4} 

Sample Input

2
5 3
1 2 3 4 1
6 2
1 2 1 2 1 2

Sample Output

4
9

Explanation

For 

1 2 3 4 1

there exists, 4 subsequences whose sum is divisible by 3, they are   

3
1 2
1 2 3
2 3 4

For 

1 2 1 2 1 2

there exists, 9 subsequences whose sum is divisible by 2, they are  

2
2
2
1 2 1
1 2 1
1 2 1 2
2 1 2 1
1 2 1 2
2 1 2 1 2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: PolandBall and Polygon

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
PolandBall has such a convex polygon with *n* veritces that no three of its diagonals intersect at the same point. PolandBall decided to improve it and draw some red segments. 

He chose a number *k* such that *gcd*(*n*,<=*k*)<==<=1. Vertices of the polygon are numbered from 1 to *n* in a clockwise way. PolandBall repeats the following process *n* times, starting from the vertex 1: 

Assume you've ended last operation in vertex *x* (consider *x*<==<=1 if it is the first operation). Draw a new segment from vertex *x* to *k*-th next vertex in clockwise direction. This is a vertex *x*<=+<=*k* or *x*<=+<=*k*<=-<=*n* depending on which of these is a valid index of polygon's vertex.

Your task is to calculate number of polygon's sections after each drawing. A section is a clear area inside the polygon bounded with drawn diagonals or the polygon's sides.

Input Specification:
There are only two numbers in the input: *n* and *k* (5<=≤<=*n*<=≤<=106, 2<=≤<=*k*<=≤<=*n*<=-<=2, *gcd*(*n*,<=*k*)<==<=1).

Output Specification:
You should print *n* values separated by spaces. The *i*-th value should represent number of polygon's sections after drawing first *i* lines.

Demo Input:
['5 2\n', '10 3\n']

Demo Output:
['2 3 5 8 11 ', '2 3 4 6 9 12 16 21 26 31 ']

Note:
The greatest common divisor (gcd) of two integers *a* and *b* is the largest positive integer that divides both *a* and *b* without a remainder.

For the first sample testcase, you should output "2 3 5 8 11". Pictures below correspond to situations after drawing lines.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A frog lives on the axis Ox and needs to reach home which is in the point n. She starts from the point 1. The frog can jump to the right at a distance not more than d. So, after she jumped from the point x she can reach the point x + a, where a is an integer from 1 to d.

For each point from 1 to n is known if there is a lily flower in it. The frog can jump only in points with a lilies. Guaranteed that there are lilies in the points 1 and n.

Determine the minimal number of jumps that the frog needs to reach home which is in the point n from the point 1. Consider that initially the frog is in the point 1. If the frog can not reach home, print -1.


-----Input-----

The first line contains two integers n and d (2 ≤ n ≤ 100, 1 ≤ d ≤ n - 1) — the point, which the frog wants to reach, and the maximal length of the frog jump.

The second line contains a string s of length n, consisting of zeros and ones. If a character of the string s equals to zero, then in the corresponding point there is no lily flower. In the other case, in the corresponding point there is a lily flower. Guaranteed that the first and the last characters of the string s equal to one.


-----Output-----

If the frog can not reach the home, print -1.

In the other case, print the minimal number of jumps that the frog needs to reach the home which is in the point n from the point 1.


-----Examples-----
Input
8 4
10010101

Output
2

Input
4 2
1001

Output
-1

Input
8 4
11100101

Output
3

Input
12 3
101111100101

Output
4



-----Note-----

In the first example the from can reach home in two jumps: the first jump from the point 1 to the point 4 (the length of the jump is three), and the second jump from the point 4 to the point 8 (the length of the jump is four).

In the second example the frog can not reach home, because to make it she need to jump on a distance three, but the maximum length of her jump equals to two.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef's daily routine is very simple. He starts his day with cooking food, then he eats the food and finally proceeds for sleeping thus ending his day. Chef carries a robot as his personal assistant whose job is to log the activities of Chef at various instants during the day. Today it recorded activities that Chef was doing at N different instants. These instances are recorded in chronological order (in increasing order of time). This log is provided to you in form of a string s of length N, consisting of characters 'C', 'E' and 'S'. If s[i] = 'C', then it means that at the i-th instant Chef was cooking, 'E' denoting he was eating and 'S' means he was sleeping.
You have to tell whether the record log made by the robot could possibly be correct or not. 

-----Input-----
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The only line of each test case contains string s.

-----Output-----
For each test case, output a single line containing "yes" or "no" (without quotes) accordingly.

-----Constraints-----
- 1 ≤ T ≤ 20
- 1 ≤ N ≤ 105

-----Subtasks-----
- Subtask #1 (40 points) : 1 ≤ N ≤ 100
- Subtask #2 (60 points) : original constraints

-----Example-----
Input:
5
CES
CS
CCC
SC
ECCC

Output:
yes
yes
yes
no
no

-----Explanation-----
Example case 1. "CES" can correspond to a possible record of activities of Chef. He starts the day with cooking, then eating and then sleeping.
Example case 2. "CS" can also correspond to a possible record of activities of Chef. He starts the day with cooking, then eating and then sleeping. Robot recorded his cooking and sleeping in order. He might not have recorded his eating activity.
Example case 4. "SC" can not correspond to Chef's activities. Here it means that Chef slept first, then he cooked the food, which is impossible for Chef to do on some particular day.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In this problem, your task is to use ASCII graphics to paint a cardiogram. 

A cardiogram is a polyline with the following corners:$(0 ; 0),(a_{1} ; a_{1}),(a_{1} + a_{2} ; a_{1} - a_{2}),(a_{1} + a_{2} + a_{3} ; a_{1} - a_{2} + a_{3}), \ldots,(\sum_{i = 1}^{n} a_{i} ; \sum_{i = 1}^{n}(- 1)^{i + 1} a_{i})$

That is, a cardiogram is fully defined by a sequence of positive integers a_1, a_2, ..., a_{n}.

Your task is to paint a cardiogram by given sequence a_{i}.


-----Input-----

The first line contains integer n (2 ≤ n ≤ 1000). The next line contains the sequence of integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 1000). It is guaranteed that the sum of all a_{i} doesn't exceed 1000.


-----Output-----

Print max |y_{i} - y_{j}| lines (where y_{k} is the y coordinate of the k-th point of the polyline), in each line print $\sum_{i = 1}^{n} a_{i}$ characters. Each character must equal either « / » (slash), « \ » (backslash), « » (space). The printed image must be the image of the given polyline. Please study the test samples for better understanding of how to print a cardiogram.

Note that in this problem the checker checks your answer taking spaces into consideration. Do not print any extra characters. Remember that the wrong answer to the first pretest doesn't give you a penalty.


-----Examples-----
Input
5
3 1 2 5 1

Output
      / \     
   / \ /   \    
  /       \   
 /         \  
          \ / 

Input
3
1 5 1

Output
 / \     
  \    
   \   
    \  
     \ /

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
How can you tell an extrovert from an
introvert at NSA? Va gur ryringbef,
gur rkgebireg ybbxf ng gur BGURE thl'f fubrf.

I found this joke on USENET, but the punchline is scrambled. Maybe you can decipher it?
According to Wikipedia, ROT13 (http://en.wikipedia.org/wiki/ROT13) is frequently used to obfuscate jokes on USENET.

Hint: For this task you're only supposed to substitue characters. Not spaces, punctuation, numbers etc.
Test examples:
```
rot13("EBG13 rknzcyr.") == "ROT13 example.";
rot13("This is my first ROT13 excercise!" == "Guvf vf zl svefg EBG13 rkprepvfr!"
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Pocket Book

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
One day little Vasya found mom's pocket book. The book had *n* names of her friends and unusually enough, each name was exactly *m* letters long. Let's number the names from 1 to *n* in the order in which they are written.

As mom wasn't home, Vasya decided to play with names: he chose three integers *i*, *j*, *k* (1<=≤<=*i*<=&lt;<=*j*<=≤<=*n*, 1<=≤<=*k*<=≤<=*m*), then he took names number *i* and *j* and swapped their prefixes of length *k*. For example, if we take names "CBDAD" and "AABRD" and swap their prefixes with the length of 3, the result will be names "AABAD" and "CBDRD".

You wonder how many different names Vasya can write instead of name number 1, if Vasya is allowed to perform any number of the described actions. As Vasya performs each action, he chooses numbers *i*, *j*, *k* independently from the previous moves and his choice is based entirely on his will. The sought number can be very large, so you should only find it modulo 1000000007 (109<=+<=7).

Input Specification:
The first input line contains two integers *n* and *m* (1<=≤<=*n*,<=*m*<=≤<=100) — the number of names and the length of each name, correspondingly. Then *n* lines contain names, each name consists of exactly *m* uppercase Latin letters.

Output Specification:
Print the single number — the number of different names that could end up in position number 1 in the pocket book after the applying the procedures described above. Print the number modulo 1000000007 (109<=+<=7).

Demo Input:
['2 3\nAAB\nBAA\n', '4 5\nABABA\nBCGDG\nAAAAA\nYABSA\n']

Demo Output:
['4\n', '216\n']

Note:
In the first sample Vasya can get the following names in the position number 1: "AAB", "AAA", "BAA" and "BAB".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A new airplane SuperPuperJet has an infinite number of rows, numbered with positive integers starting with 1 from cockpit to tail. There are six seats in each row, denoted with letters from 'a' to 'f'. Seats 'a', 'b' and 'c' are located to the left of an aisle (if one looks in the direction of the cockpit), while seats 'd', 'e' and 'f' are located to the right. Seats 'a' and 'f' are located near the windows, while seats 'c' and 'd' are located near the aisle. 

<image>

It's lunch time and two flight attendants have just started to serve food. They move from the first rows to the tail, always maintaining a distance of two rows from each other because of the food trolley. Thus, at the beginning the first attendant serves row 1 while the second attendant serves row 3. When both rows are done they move one row forward: the first attendant serves row 2 while the second attendant serves row 4. Then they move three rows forward and the first attendant serves row 5 while the second attendant serves row 7. Then they move one row forward again and so on.

Flight attendants work with the same speed: it takes exactly 1 second to serve one passenger and 1 second to move one row forward. Each attendant first serves the passengers on the seats to the right of the aisle and then serves passengers on the seats to the left of the aisle (if one looks in the direction of the cockpit). Moreover, they always serve passengers in order from the window to the aisle. Thus, the first passenger to receive food in each row is located in seat 'f', and the last one — in seat 'c'. Assume that all seats are occupied.

Vasya has seat s in row n and wants to know how many seconds will pass before he gets his lunch.

Input

The only line of input contains a description of Vasya's seat in the format ns, where n (1 ≤ n ≤ 1018) is the index of the row and s is the seat in this row, denoted as letter from 'a' to 'f'. The index of the row and the seat are not separated by a space.

Output

Print one integer — the number of seconds Vasya has to wait until he gets his lunch.

Examples

Input

1f


Output

1


Input

2d


Output

10


Input

4a


Output

11


Input

5e


Output

18

Note

In the first sample, the first flight attendant serves Vasya first, so Vasya gets his lunch after 1 second.

In the second sample, the flight attendants will spend 6 seconds to serve everyone in the rows 1 and 3, then they will move one row forward in 1 second. As they first serve seats located to the right of the aisle in order from window to aisle, Vasya has to wait 3 more seconds. The total is 6 + 1 + 3 = 10.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let's define logical OR as an operation on two logical values (i. e. values that belong to the set {0, 1}) that is equal to 1 if either or both of the logical values is set to 1, otherwise it is 0. We can define logical OR of three or more logical values in the same manner:

$a_{1} OR a_{2} OR \ldots OR a_{k}$ where $a_{i} \in \{0,1 \}$ is equal to 1 if some a_{i} = 1, otherwise it is equal to 0.

Nam has a matrix A consisting of m rows and n columns. The rows are numbered from 1 to m, columns are numbered from 1 to n. Element at row i (1 ≤ i ≤ m) and column j (1 ≤ j ≤ n) is denoted as A_{ij}. All elements of A are either 0 or 1. From matrix A, Nam creates another matrix B of the same size using formula:

[Image].

(B_{ij} is OR of all elements in row i and column j of matrix A)

Nam gives you matrix B and challenges you to guess matrix A. Although Nam is smart, he could probably make a mistake while calculating matrix B, since size of A can be large.


-----Input-----

The first line contains two integer m and n (1 ≤ m, n ≤ 100), number of rows and number of columns of matrices respectively.

The next m lines each contain n integers separated by spaces describing rows of matrix B (each element of B is either 0 or 1).


-----Output-----

In the first line, print "NO" if Nam has made a mistake when calculating B, otherwise print "YES". If the first line is "YES", then also print m rows consisting of n integers representing matrix A that can produce given matrix B. If there are several solutions print any one.


-----Examples-----
Input
2 2
1 0
0 0

Output
NO

Input
2 3
1 1 1
1 1 1

Output
YES
1 1 1
1 1 1

Input
2 3
0 1 0
1 1 1

Output
YES
0 0 0
0 1 0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
# Task
We know that some numbers can be split into two primes. ie. `5 = 2 + 3, 10 = 3 + 7`. But some numbers are not. ie. `17, 27, 35`, etc.. 

Given a positive integer `n`. Determine whether it can be split into two primes. If yes, return the maximum product of two primes. If not, return `0` instead.

# Input/Output

`[input]` integer `n`

A positive integer. 

`0 ≤ n ≤ 100000`

`[output]` an integer

The possible maximum product of two primes. or return `0` if it's impossible split into two primes.

# Example

For `n = 1`, the output should be `0`.

`1` can not split into two primes

For `n = 4`, the output should be `4`.

`4` can split into two primes `2 and 2`. `2 x 2 = 4`

For `n = 20`, the output should be `91`.

`20` can split into two primes `7 and 13` or `3 and 17`. The maximum product is `7 x 13 = 91`

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.