vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You are playing a racing game. Your character starts at the X-axis line ($y=0$) and proceeds up the racetrack, which has a boundary at the lines $x=0$ and $x=w$. The finish is at $y=h$, and the game ends when you reach that line. You proceed at a fixed vertical velocity $v$, but you can control your horizontal velocity to be any value between $-v/r$ and $v/r$, where $r$ is a fixed ratio. You may change your horizontal velocity at any time, but your vertical velocity must remain fixed.

There are gems at specific points on the race track. Your job is to collect as many gems as possible (they all have the same value).

How many gems can you collect? You may start at any horizontal position you want (but your vertical position must be $0$ at the start).

-----Input-----
Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. The first line will contain four integers: $n$ ($1 \le n \le 10^5$) is the number of gems, $r$ ($1 \le r \le 10$) is the ratio of vertical velocity to maximum horizontal speed, $w$ ($1 \le w \le 10^9$) is the width of the track, and $h$ ($1 \le h \le 10^9$) is the height of the finish line. Following this will be $n$ lines, each containing an integer $x$ and $y$ coordinate ($0 \le x \le w$, $1 \le y \le h$), containing the coordinate of a gem. All gems will lie on the race track. None will be on the start line.

-----Output-----
Output a single integer on a line by itself representing the maximum number of gems that you can collect.

-----Examples-----
Sample Input 1:
5 1 10 10
8 8
5 1
4 6
4 7
7 9
Sample Output 1:
3

Sample Input 2:
5 1 100 100
27 75
79 77
40 93
62 41
52 45
Sample Output 2:
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Divisible by Seven

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You have number *a*, whose decimal representation quite luckily contains digits 1, 6, 8, 9. Rearrange the digits in its decimal representation so that the resulting number will be divisible by 7.

Number *a* doesn't contain any leading zeroes and contains digits 1, 6, 8, 9 (it also can contain another digits). The resulting number also mustn't contain any leading zeroes.

Input Specification:
The first line contains positive integer *a* in the decimal record. It is guaranteed that the record of number *a* contains digits: 1, 6, 8, 9. Number *a* doesn't contain any leading zeroes. The decimal representation of number *a* contains at least 4 and at most 106 characters.

Output Specification:
Print a number in the decimal notation without leading zeroes — the result of the permutation.

If it is impossible to rearrange the digits of the number *a* in the required manner, print 0.

Demo Input:
['1689\n', '18906\n']

Demo Output:
['1869\n', '18690\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a matrix consisting of n rows and m columns. The matrix contains lowercase letters of the Latin alphabet.

You can perform the following operation any number of times you want to: choose two integers i (1 ≤ i ≤ m) and k (0 < k < n), and shift every column j such that i ≤ j ≤ m cyclically by k. The shift is performed upwards.

For example, if you have a matrix 

\left( \begin{array} \\\ a & b & c \\\ d & e & f \\\ g & h & i \end{array}\right)   and perform an operation with i = 2, k = 1, then it becomes:  \left( \begin{array} \\\ a & e & f \\\ d & h & i \\\ g & b & c \end{array}\right)  

You have to process q queries. Each of the queries is a string of length m consisting of lowercase letters of the Latin alphabet. For each query, you have to calculate the minimum number of operations described above you have to perform so that at least one row of the matrix is equal to the string from the query. Note that all queries are independent, that is, the operations you perform in a query don't affect the initial matrix in other queries.

Input

The first line contains three integers n, m, q (2 ≤ n, m, q ≤ 2.5 ⋅ 10^5; n ⋅ m ≤ 5 ⋅ 10^5; q ⋅ m ≤ 5 ⋅ 10^5) — the number of rows and columns in the matrix and the number of queries, respectively.

The next n lines contains m lowercase Latin letters each — elements of the matrix.

The following q lines contains a description of queries — strings of length m consisting of lowercase letters of the Latin alphabet.

Output

Print q integers. The i-th integer should be equal to the minimum number of operations you have to perform so that the matrix contains a string from the i-th query or -1 if the specified string cannot be obtained.

Examples

Input


3 5 4
abacc
ccbba
ccabc
abacc
acbbc
ababa
acbbc


Output


0
2
1
2


Input


6 4 4
daac
bcba
acad
cbdc
aaaa
bcbb
dcdd
acba
bbbb
dbcd


Output


3
1
2
-1


Input


5 10 5
ltjksdyfgg
cbhpsereqn
ijndtzbzcf
ghgcgeadep
bfzdgxqmqe
ibgcgzyfep
bbhdgxqmqg
ltgcgxrzep
ljnpseldgn
ghhpseyzcf


Output


5
3
5
-1
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
On the way to school, Karen became fixated on the puzzle game on her phone! [Image] 

The game is played as follows. In each level, you have a grid with n rows and m columns. Each cell originally contains the number 0.

One move consists of choosing one row or column, and adding 1 to all of the cells in that row or column.

To win the level, after all the moves, the number in the cell at the i-th row and j-th column should be equal to g_{i}, j.

Karen is stuck on one level, and wants to know a way to beat this level using the minimum number of moves. Please, help her with this task!


-----Input-----

The first line of input contains two integers, n and m (1 ≤ n, m ≤ 100), the number of rows and the number of columns in the grid, respectively.

The next n lines each contain m integers. In particular, the j-th integer in the i-th of these rows contains g_{i}, j (0 ≤ g_{i}, j ≤ 500).


-----Output-----

If there is an error and it is actually not possible to beat the level, output a single integer -1.

Otherwise, on the first line, output a single integer k, the minimum number of moves necessary to beat the level.

The next k lines should each contain one of the following, describing the moves in the order they must be done:  row x, (1 ≤ x ≤ n) describing a move of the form "choose the x-th row".  col x, (1 ≤ x ≤ m) describing a move of the form "choose the x-th column". 

If there are multiple optimal solutions, output any one of them.


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

Output
4
row 1
row 1
col 4
row 3

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

Output
-1

Input
3 3
1 1 1
1 1 1
1 1 1

Output
3
row 1
row 2
row 3



-----Note-----

In the first test case, Karen has a grid with 3 rows and 5 columns. She can perform the following 4 moves to beat the level: [Image] 

In the second test case, Karen has a grid with 3 rows and 3 columns. It is clear that it is impossible to beat the level; performing any move will create three 1s on the grid, but it is required to only have one 1 in the center.

In the third test case, Karen has a grid with 3 rows and 3 columns. She can perform the following 3 moves to beat the level: [Image] 

Note that this is not the only solution; another solution, among others, is col 1, col 2, col 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Link to Russian translation of problem

The statement of this problem is very simple: you are given a non-negative integer X. Whether it's divisible by 41?

Input
The first line contains one integer T - denoting the number of test cases.
The following T lines contain 4 integers a[0], a1, c, n each and describe each test case:

Let's consider decimal representation of the number X as an array  where a[0] is the leftmost (highest) digit. You are given a[0], a1 and each a[i] for 2 ≤ i ≤ n-1 can be found by formula:

a[i] = ( a[i - 1]*c + a[i - 2] ) modulo 10

Output
For each test case output YES if the corresponding integer is divisible by 41 and NO otherwise.

Constraints
T ≤ 2000
1 ≤N ≤ 50000
0 ≤ a[0], a1, c < 10

SAMPLE INPUT
5
1 4 6 2
4 1 4 2
8 2 1 2
2 8 8 2
1 2 1 3

SAMPLE OUTPUT
NO
YES
YES
NO
YES

Explanation

Numbers: 14, 41, 82, 28, 123.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Lysias loves his full-rigged ship and takes it out to his island castle as often as possible. On his way back to the castle one day, the engines capable of turning the sails failed. As it is a full-rigged ship, he and his crew are now unable to turn the sails in any direction.

But, as luck would have it, there is a south wind which is blowing them in the right direction…at least approximately. Since they may not get to the castle by wind only, Lysias believes he can use the ocean’s currents to move the ship either east or west temporarily by retracting and lowering the ship’s sails. In that way, the ship can move in two potential directions:
 - Move north by lowering the sails
 - Retract the sails and move in the direction of the current they’re on top of (east/west)

Lysias has dug up an old map of all the currents in this part of the ocean. As he is fond of mathematics, not only does Lysias wonder if it’s possible to get home without fixing the sails; he also wonders how many different routes they can take to get home. Can you help him?

-----Input-----
The first line has three integers: $Y$ and $X$ and $x_{init}$, representing the number of rows and columns of the map, and which column the ship is currently placed at. The ship always starts on the bottom row.

Then follow $Y$ rows, each with $X$ characters each. All characters $C_{x,y}$ is one of ‘~’, ‘#’, ‘@’, ‘>’ and ‘<’. ’~’ represents open sea without any currents, ‘#’ is impassable shallow waters, and ‘>’ and ‘<’ are currents moving the boat to the right and left respectively. ‘@’ represents Lysias’ castle.

-----Output-----
Output all the different distinct paths the ship could take to get back to the castle. Since there may be very many different ways to get back, output the answer modulo $1000003$.

If there are no ways to get to the castle, output “begin repairs”.

-----Limits-----
 - $0 < Y \leq 300$
 - $0 \leq x_{init} < X \leq 50000$
 - If $C_{x,y} = \text {‘>’}$, then $x+1 < X$ and $C_{x+1,y} \notin \{ \text {‘<’}, \verb|`#'|\} $
 - If $C_{x,y} = \text {‘<’}$, then $0 \leq x-1$ and $C_{x-1,y} \notin \{ \text {‘>’}, \verb|`#'|\} $
 - There is exactly one ‘@’ tile on the map
 - The boat will not start on a `#' tile

-----Examples-----
Sample Input 1:
2 2 0
>@
>~
Sample Output 1:
2

Sample Input 2:
3 5 1
>>@<<
>~#~<
>>>>~
Sample Output 2:
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We already know of the large corporation where Polycarpus works as a system administrator. The computer network there consists of n computers and m cables that connect some pairs of computers. In other words, the computer network can be represented as some non-directed graph with n nodes and m edges. Let's index the computers with integers from 1 to n, let's index the cables with integers from 1 to m.

Polycarpus was given an important task — check the reliability of his company's network. For that Polycarpus decided to carry out a series of k experiments on the computer network, where the i-th experiment goes as follows:

  1. Temporarily disconnect the cables with indexes from li to ri, inclusive (the other cables remain connected). 
  2. Count the number of connected components in the graph that is defining the computer network at that moment. 
  3. Re-connect the disconnected cables with indexes from li to ri (that is, restore the initial network). 



Help Polycarpus carry out all experiments and for each print the number of connected components in the graph that defines the computer network through the given experiment. Isolated vertex should be counted as single component.

Input

The first line contains two space-separated integers n, m (2 ≤ n ≤ 500; 1 ≤ m ≤ 104) — the number of computers and the number of cables, correspondingly.

The following m lines contain the cables' description. The i-th line contains space-separated pair of integers xi, yi (1 ≤ xi, yi ≤ n; xi ≠ yi) — the numbers of the computers that are connected by the i-th cable. Note that a pair of computers can be connected by multiple cables.

The next line contains integer k (1 ≤ k ≤ 2·104) — the number of experiments. Next k lines contain the experiments' descriptions. The i-th line contains space-separated integers li, ri (1 ≤ li ≤ ri ≤ m) — the numbers of the cables that Polycarpus disconnects during the i-th experiment. 

Output

Print k numbers, the i-th number represents the number of connected components of the graph that defines the computer network during the i-th experiment. 

Examples

Input

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


Output

4
5
6
3
4
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Takahashi has an N \times M grid, with N horizontal rows and M vertical columns. Determine if we can place A 1 \times 2 tiles (1 vertical, 2 horizontal) and B 2 \times 1 tiles (2 vertical, 1 horizontal) satisfying the following conditions, and construct one arrangement of the tiles if it is possible:

* All the tiles must be placed on the grid.
* Tiles must not stick out of the grid, and no two different tiles may intersect.
* Neither the grid nor the tiles may be rotated.
* Every tile completely covers exactly two squares.

Constraints

* 1 \leq N,M \leq 1000
* 0 \leq A,B \leq 500000
* N, M, A and B are integers.

Input

Input is given from Standard Input in the following format:


N M A B


Output

If it is impossible to place all the tiles, print `NO`. Otherwise, print the following:


YES
c_{11}...c_{1M}
:
c_{N1}...c_{NM}


Here, c_{ij} must be one of the following characters: `.`, `<`, `>`, `^` and `v`. Represent an arrangement by using each of these characters as follows:

* When c_{ij} is `.`, it indicates that the square at the i-th row and j-th column is empty;
* When c_{ij} is `<`, it indicates that the square at the i-th row and j-th column is covered by the left half of a 1 \times 2 tile;
* When c_{ij} is `>`, it indicates that the square at the i-th row and j-th column is covered by the right half of a 1 \times 2 tile;
* When c_{ij} is `^`, it indicates that the square at the i-th row and j-th column is covered by the top half of a 2 \times 1 tile;
* When c_{ij} is `v`, it indicates that the square at the i-th row and j-th column is covered by the bottom half of a 2 \times 1 tile.

Examples

Input

3 4 4 2


Output

YES
<><>
^<>^
v<>v


Input

4 5 5 3


Output

YES
<>..^
^.<>v
v<>.^
<><>v


Input

7 9 20 20


Output

NO

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Limak is a little polar bear. Polar bears hate long strings and thus they like to compress them. You should also know that Limak is so young that he knows only first six letters of the English alphabet: 'a', 'b', 'c', 'd', 'e' and 'f'.

You are given a set of q possible operations. Limak can perform them in any order, any operation may be applied any number of times. The i-th operation is described by a string a_{i} of length two and a string b_{i} of length one. No two of q possible operations have the same string a_{i}.

When Limak has a string s he can perform the i-th operation on s if the first two letters of s match a two-letter string a_{i}. Performing the i-th operation removes first two letters of s and inserts there a string b_{i}. See the notes section for further clarification.

You may note that performing an operation decreases the length of a string s exactly by 1. Also, for some sets of operations there may be a string that cannot be compressed any further, because the first two letters don't match any a_{i}.

Limak wants to start with a string of length n and perform n - 1 operations to finally get a one-letter string "a". In how many ways can he choose the starting string to be able to get "a"? Remember that Limak can use only letters he knows.


-----Input-----

The first line contains two integers n and q (2 ≤ n ≤ 6, 1 ≤ q ≤ 36) — the length of the initial string and the number of available operations.

The next q lines describe the possible operations. The i-th of them contains two strings a_{i} and b_{i} (|a_{i}| = 2, |b_{i}| = 1). It's guaranteed that a_{i} ≠ a_{j} for i ≠ j and that all a_{i} and b_{i} consist of only first six lowercase English letters.


-----Output-----

Print the number of strings of length n that Limak will be able to transform to string "a" by applying only operations given in the input.


-----Examples-----
Input
3 5
ab a
cc c
ca a
ee c
ff d

Output
4

Input
2 8
af e
dc d
cc f
bc b
da b
eb a
bb b
ff c

Output
1

Input
6 2
bb a
ba a

Output
0



-----Note-----

In the first sample, we count initial strings of length 3 from which Limak can get a required string "a". There are 4 such strings: "abb", "cab", "cca", "eea". The first one Limak can compress using operation 1 two times (changing "ab" to a single "a"). The first operation would change "abb" to "ab" and the second operation would change "ab" to "a".

Other three strings may be compressed as follows:   "cab" $\rightarrow$ "ab" $\rightarrow$ "a"  "cca" $\rightarrow$ "ca" $\rightarrow$ "a"  "eea" $\rightarrow$ "ca" $\rightarrow$ "a" 

In the second sample, the only correct initial string is "eb" because it can be immediately compressed to "a".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In a bizarre game of chess ,knight was so drunk, that instead of his usual move he started walking straight. In every move Knight jumps on 2n steps forward (n is number of block that he had travelled so far from starting) but after that he has to take either 1 step forward or backward.
Now the Knight needs to get to position X so King (i.e. You) needs to decide the order of his backward or forward step in such a way that he can reach its destination in minimum number of steps. Remember he always travels in a straight line and the length of the board is infinite.

-----Input-----
The first line of the input contains an integer T denoting the number of test cases, for each test case enter value X ( i.e. destination)
Note : initially knight is at n = 1.

-----Output-----
For each test case the output should be string of numbers 1 & 2 where 1 denotes backward step and 2 denote the forward step 
Note : for no solution print 0.

-----Constraints-----
- 1 ≤ T ≤ 100
- 1 ≤ X ≤ 10^10

-----Example-----
Input:
2
17
10
Output:
2111
0

-----Explanation-----
Case 1 : starting from  n = 1 , knight moves to n = 3 ('2') , 5 ('1') , 9 ('1') , 17 ('1') i.e. string printed is 2 1 1 1
Case 2 : no solution is possible

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Monty Hall problem is a probability puzzle base on the American TV show "Let's Make A Deal".

In this show, you would be presented with 3 doors: One with a prize behind it, and two without (represented with goats).

After choosing a door, the host would open one of the other two doors which didn't include a prize, and ask the participant if he or she wanted to switch to the third door. Most wouldn't. One would think you have a fifty-fifty chance of winning after having been shown a false door, however the math proves that you significantly increase your chances, from 1/3 to 2/3 by switching.

Further information about this puzzle can be found on https://en.wikipedia.org/wiki/Monty_Hall_problem.

In this program you are given an array of people who have all guessed on a door from 1-3, as well as given the door which includes the price. You need to make every person switch to the other door, and increase their chances of winning. Return the win percentage (as a rounded int) of all participants.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Students love to celebrate their holidays. Especially if the holiday is the day of the end of exams!

Despite the fact that Igor K., unlike his groupmates, failed to pass a programming test, he decided to invite them to go to a cafe so that each of them could drink a bottle of... fresh cow milk. Having entered the cafe, the m friends found n different kinds of milk on the menu, that's why they ordered n bottles — one bottle of each kind. We know that the volume of milk in each bottle equals w.

When the bottles were brought in, they decided to pour all the milk evenly among the m cups, so that each got a cup. As a punishment for not passing the test Igor was appointed the person to pour the milk. He protested that he was afraid to mix something up and suggested to distribute the drink so that the milk from each bottle was in no more than two different cups. His friends agreed but they suddenly faced the following problem — and what is actually the way to do it?

Help them and write the program that will help to distribute the milk among the cups and drink it as quickly as possible!

Note that due to Igor K.'s perfectly accurate eye and unswerving hands, he can pour any fractional amount of milk from any bottle to any cup.

Input

The only input data file contains three integers n, w and m (1 ≤ n ≤ 50, 100 ≤ w ≤ 1000, 2 ≤ m ≤ 50), where n stands for the number of ordered bottles, w stands for the volume of each of them and m stands for the number of friends in the company.

Output

Print on the first line "YES" if it is possible to pour the milk so that the milk from each bottle was in no more than two different cups. If there's no solution, print "NO".

If there is a solution, then print m more lines, where the i-th of them describes the content of the i-th student's cup. The line should consist of one or more pairs that would look like "b v". Each such pair means that v (v > 0) units of milk were poured into the i-th cup from bottle b (1 ≤ b ≤ n). All numbers b on each line should be different.

If there are several variants to solve the problem, print any of them. Print the real numbers with no less than 6 digits after the decimal point.

Examples

Input

2 500 3


Output

YES
1 333.333333
2 333.333333
2 166.666667 1 166.666667


Input

4 100 5


Output

YES
3 20.000000 4 60.000000
1 80.000000
4 40.000000 2 40.000000
3 80.000000
2 60.000000 1 20.000000


Input

4 100 7


Output

NO


Input

5 500 2


Output

YES
4 250.000000 5 500.000000 2 500.000000
3 500.000000 1 500.000000 4 250.000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
ACT I
Handi Bhaiya is a very notorious kid and always troubles his parents and friends. One day his naughtiness lead him to a demon Kali(THE COBRA COMMANDER) who trapped him into a triangular magic cell. Handi Bhaiya parents want their kid back and asks for your help.

ACT II
You knew that the entire humanity will hate you but then also you decided to rescue Handi Bhaiya (don't ask why). You went to Kali and asked to release Handi Bhiaya. Kali being good by heart decided to free him but you have to solve a puzzle first.

Puzzle
Kali asks to write you a program that will tell whether Handi Bhaiya can be inside the given cell or not, for T(1 ≤ T ≤ 10^6) test cases. For each test case you will be given a cell(not necessarily closed and bounded) that will have 3 integral sides- a, b and c representing the sides of cell. You have to tell whether Handi can be inside that cell or not. Remember that the cell was triangular in which he was trapped.
If the cell is triangular then also print the type of triangle - isosceles, equilateral or scalene. Refer given test case for sample output.
Constraints: 0<a,b,c<2^64

SAMPLE INPUT
4
15 15 15
13 13 14
3 4 5
10 12 23

SAMPLE OUTPUT
YES. It is a equilateral triangle.
YES. It is a isosceles triangle.
YES. It is a scalene triangle.
NO

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