vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
The fearless Ikta has finally hunted down the infamous Count Big Bridge! Count Bigbridge is now trapped in a rectangular room w meters wide and h meters deep, waiting for his end.

If you select a corner of the room and take the coordinate system so that the width direction is the x-axis and the depth direction is the y-axis, and the inside of the room is in the positive direction, Count Big Bridge is at the point (p, q). .. At point (x, y), there is a shock wave launcher, which is Ikta's ultimate weapon, from which a shock wave of v meters per second is emitted in all directions. This shock wave is valid for t seconds and is reflected off the walls of the room.

Ikta, who is outside the room, wants to know how much Count Big Bridge will suffer, so let's write a program that asks Count Big Bridge how many shock waves he will hit. At this time, if the shock wave hits the enemy from the n direction at the same time, it is considered to have hit the enemy n times, and it is also effective if the shock wave hits the enemy exactly t seconds later. The shock wave does not disappear due to obstacles such as the launcher itself and Count Big Bridge, and the shock waves do not interfere with each other.



Input

The input is given in the following format.

> w h v t x y p q
>

* Each is a positive integer as explained in the problem statement.



Constraints

* v × t ≤ 106
* 2 ≤ w, h ≤ 108
* 0 <x, p <w
* 0 <y, q <h
* (x, y) ≠ (p, q)

Output

Output the number of times the shock wave hits Count Big Bridge on one line.

Examples

Input

10 10 1 10 3 3 7 7


Output

1


Input

10 10 1 11 3 3 7 7


Output

5


Input

2 3 1000 1000 1 1 1 2


Output

523598775681

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The research center Q has developed a new multi-core processor. The processor consists of n cores and has k cells of cache memory. Consider the work of this processor.

At each cycle each core of the processor gets one instruction: either do nothing, or the number of the memory cell (the core will write an information to the cell). After receiving the command, the core executes it immediately. Sometimes it happens that at one cycle, multiple cores try to write the information into a single cell. Unfortunately, the developers did not foresee the possibility of resolving conflicts between cores, so in this case there is a deadlock: all these cores and the corresponding memory cell are locked forever. Each of the locked cores ignores all further commands, and no core in the future will be able to record an information into the locked cell. If any of the cores tries to write an information into some locked cell, it is immediately locked.

The development team wants to explore the deadlock situation. Therefore, they need a program that will simulate the processor for a given set of instructions for each core within m cycles . You're lucky, this interesting work is entrusted to you. According to the instructions, during the m cycles define for each core the number of the cycle, during which it will become locked. It is believed that initially all cores and all memory cells are not locked.


-----Input-----

The first line contains three integers n, m, k (1 ≤ n, m, k ≤ 100). Then follow n lines describing instructions. The i-th line contains m integers: x_{i}1, x_{i}2, ..., x_{im} (0 ≤ x_{ij} ≤ k), where x_{ij} is the instruction that must be executed by the i-th core at the j-th cycle. If x_{ij} equals 0, then the corresponding instruction is «do nothing». But if x_{ij} is a number from 1 to k, then the corresponding instruction is «write information to the memory cell number x_{ij}».

We assume that the cores are numbered from 1 to n, the work cycles are numbered from 1 to m and the memory cells are numbered from 1 to k.


-----Output-----

Print n lines. In the i-th line print integer t_{i}. This number should be equal to 0 if the i-th core won't be locked, or it should be equal to the number of the cycle when this core will be locked.


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

Output
1
1
3
0

Input
3 2 2
1 2
1 2
2 2

Output
1
1
0

Input
1 1 1
0

Output
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Arghs! Yet again, all the clocks in Petra’s home show the wrong time due to a power outage that occurred while she was sleeping. This means she has to spend her day resetting all the clocks to the correct time. Now, you might not consider this a big deal. After all, how many clocks does any single household really have? Well, Petra just so happens to be a collector of clocks. She literally has hundreds of clocks – and that is just in her bedroom! Thus, it is understandable that she does not look forward to all this resetting. 

You, as her friend, would prefer if she did not need to spend her entire day resetting all her clocks. Especially since this means she would not have any time to play with you! If only you could construct some automated way of entering the correct time into all the clocks, perhaps through some kind of computer code...

A-ha, of course! You can write a program to determine how to set the correct time as quickly as possible!

Each clock has a display of $4$ digits: two are used to display the hour (between 00 and 23), and two are used to display the minute (between 00 and 59). The time can be changed by selecting a digit and either decreasing or increasing by $1$. Decreasing a digit that is $0$, it is turned into $9$, and increasing a digit $9$ turns it into $0$. However, the clock can not display invalid times. This means that at any given time, the hour must be between 00 and 23 and the minute between 00 and 59.

Write a program that, given the original time of a clock and the current time, determines how to set the clock correctly.

-----Input-----
The input consists:
 - one line with the time that the clock is currently set to.
 - one line with the current time.

Each time has the format hh:mm, where hh is a two-digit number between 00 and 23, and mm is a two-digit number between 00 and 59.

-----Output-----
The first line contains the number of different times seen on the clock when setting it correctly. Then for each time output it on the same format as above hh:mm on a separate line. Include both the original time and the final time.

-----Examples-----
Sample Input 1:
00:00
01:01
Sample Output 1:
3
00:00
01:00
01:01

Sample Input 2:
00:08
00:00
Sample Output 2:
3
00:08
00:09
00:00

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let $s$ be a string of lowercase Latin letters. Its price is the sum of the indices of letters (an integer between 1 and 26) that are included in it. For example, the price of the string abca is $1+2+3+1=7$.

The string $w$ and the integer $p$ are given. Remove the minimal number of letters from $w$ so that its price becomes less than or equal to $p$ and print the resulting string. Note that the resulting string may be empty. You can delete arbitrary letters, they do not have to go in a row. If the price of a given string $w$ is less than or equal to $p$, then nothing needs to be deleted and $w$ must be output.

Note that when you delete a letter from $w$, the order of the remaining letters is preserved. For example, if you delete the letter e from the string test, you get tst.


-----Input-----

The first line of input contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the test. The following are descriptions of $t$ test cases.

Each case consists of two lines.

The first of them is the string $w$, it is non-empty and consists of lowercase Latin letters. Its length does not exceed $2\cdot10^5$.

The second line contains an integer $p$ ($1 \le p \le 5\,200000$).

It is guaranteed that the sum of string lengths $w$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

Output exactly $t$ rows, the $i$-th of them should contain the answer to the $i$-th set of input data. Print the longest string that is obtained from $w$ by deleting letters such that its price is less or equal to $p$. If there are several answers, then output any of them.

Note that the empty string  — is one of the possible answers. In this case, just output an empty string.


-----Examples-----

Input
5
abca
2
abca
6
codeforces
1
codeforces
10
codeforces
100
Output
aa
abc

cdc
codeforces


-----Note-----

None

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 gi, 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 gi, j (0 ≤ gi, 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.
Title: Hongcow Learns the Cyclic Shift

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Hongcow is learning to spell! One day, his teacher gives him a word that he needs to learn to spell. Being a dutiful student, he immediately learns how to spell the word.

Hongcow has decided to try to make new words from this one. He starts by taking the word he just learned how to spell, and moves the last character of the word to the beginning of the word. He calls this a cyclic shift. He can apply cyclic shift many times. For example, consecutively applying cyclic shift operation to the word "abracadabra" Hongcow will get words "aabracadabr", "raabracadab" and so on.

Hongcow is now wondering how many distinct words he can generate by doing the cyclic shift arbitrarily many times. The initial string is also counted.

Input Specification:
The first line of input will be a single string *s* (1<=≤<=|*s*|<=≤<=50), the word Hongcow initially learns how to spell. The string *s* consists only of lowercase English letters ('a'–'z').

Output Specification:
Output a single integer equal to the number of distinct strings that Hongcow can obtain by applying the cyclic shift arbitrarily many times to the given string.

Demo Input:
['abcd\n', 'bbb\n', 'yzyz\n']

Demo Output:
['4\n', '1\n', '2\n']

Note:
For the first sample, the strings Hongcow can generate are "abcd", "dabc", "cdab", and "bcda".

For the second sample, no matter how many times Hongcow does the cyclic shift, Hongcow can only generate "bbb".

For the third sample, the two strings Hongcow can generate are "yzyz" and "zyzy".

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
A revolution took place on the Buka Island. New government replaced the old one. The new government includes *n* parties and each of them is entitled to some part of the island according to their contribution to the revolution. However, they can't divide the island.

The island can be conventionally represented as two rectangles *a*<=×<=*b* and *c*<=×<=*d* unit squares in size correspondingly. The rectangles are located close to each other. At that, one of the sides with the length of *a* and one of the sides with the length of *c* lie on one line. You can see this in more details on the picture.

The *i*-th party is entitled to a part of the island equal to *x**i* unit squares. Every such part should fully cover several squares of the island (it is not allowed to cover the squares partially) and be a connected figure. A "connected figure" presupposes that from any square of this party one can move to any other square of the same party moving through edge-adjacent squares also belonging to that party.

Your task is to divide the island between parties.

Input Specification:
The first line contains 5 space-separated integers — *a*, *b*, *c*, *d* and *n* (1<=≤<=*a*,<=*b*,<=*c*,<=*d*<=≤<=50, *b*<=≠<=*d*, 1<=≤<=*n*<=≤<=26). The second line contains *n* space-separated numbers. The *i*-th of them is equal to number *x**i* (1<=≤<=*x**i*<=≤<=*a*<=×<=*b*<=+<=*c*<=×<=*d*). It is guaranteed that .

Output Specification:
If dividing the island between parties in the required manner is impossible, print "NO" (without the quotes). Otherwise, print "YES" (also without the quotes) and, starting from the next line, print *max*(*b*,<=*d*) lines each containing *a*<=+<=*c* characters. To mark what square should belong to what party, use lowercase Latin letters. For the party that is first in order in the input data, use "a", for the second one use "b" and so on. Use "." for the squares that belong to the sea. The first symbol of the second line of the output data should correspond to the square that belongs to the rectangle *a*<=×<=*b*. The last symbol of the second line should correspond to the square that belongs to the rectangle *c*<=×<=*d*.

If there are several solutions output any.

Demo Input:
['3 4 2 2 3\n5 8 3\n', '3 2 1 4 4\n1 2 3 4\n']

Demo Output:
['YES\naaabb\naabbb\ncbb..\nccb..\n', 'YES\nabbd\ncccd\n...d\n...d\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ashley likes playing with strings.

She gives Mojo a fun problem to solve. In her imaginary string world, a string of even length is called as "Doublindrome" if both halves of the string are palindromes (both halves have length equal to half of original string).

She gives Mojo a string and asks him if he can form a "Doublindrome" by rearranging the characters of the given string or keeping the string as it is.

As Mojo is busy playing with cats, solve the problem for him.

Print "YES" (without quotes) if given string can be rearranged to form a "Doublindrome" else print "NO" (without quotes).

-----Input:-----
- First line will contain a single integer $T$, the number of testcases. 
- Each testcase consists of two lines, first line consists of an integer $N$ (length of the string) and second line consists of  the string $S$. 

-----Output:-----
For each testcase, print "YES"(without quotes) or "NO"(without quotes) on a new line.

-----Constraints-----
- $1 \leq T \leq 10^5$
- $1 \leq N \leq 100$
- $N$ is always even.
- String $S$ consists only of lowercase English alphabets.

-----Sample Input:-----
1
8
abbacddc

-----Sample Output:-----
YES

-----EXPLANATION:-----
The given string is a Doublindrome as its 2 halves "abba" and "cddc" are palindromes.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Two pirates Polycarpus and Vasily play a very interesting game. They have *n* chests with coins, the chests are numbered with integers from 1 to *n*. Chest number *i* has *a**i* coins. 

Polycarpus and Vasily move in turns. Polycarpus moves first. During a move a player is allowed to choose a positive integer *x* (2·*x*<=+<=1<=≤<=*n*) and take a coin from each chest with numbers *x*, 2·*x*, 2·*x*<=+<=1. It may turn out that some chest has no coins, in this case the player doesn't take a coin from this chest. The game finishes when all chests get emptied.

Polycarpus isn't a greedy scrooge. Polycarpys is a lazy slob. So he wonders in what minimum number of moves the game can finish. Help Polycarpus, determine the minimum number of moves in which the game can finish. Note that Polycarpus counts not only his moves, he also counts Vasily's moves.

Input Specification:
The first line contains a single integer *n* (1<=≤<=*n*<=≤<=100) — the number of chests with coins. The second line contains a sequence of space-separated integers: *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=1000), where *a**i* is the number of coins in the chest number *i* at the beginning of the game.

Output Specification:
Print a single integer — the minimum number of moves needed to finish the game. If no sequence of turns leads to finishing the game, print -1.

Demo Input:
['1\n1\n', '3\n1 2 3\n']

Demo Output:
['-1\n', '3\n']

Note:
In the first test case there isn't a single move that can be made. That's why the players won't be able to empty the chests.

In the second sample there is only one possible move *x* = 1. This move should be repeated at least 3 times to empty the third chest.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Matryoshkas are sets of traditional Russian wooden dolls of decreasing size placed one inside the other. A matryoshka doll can be opened to reveal a smaller figure of the same sort inside, which has, in turn, another figure inside, and so on.The Russian Matryoshka Museum recently exhibited a collection of similarly designed matryoshka sets, differing only in the number of nested dolls in each set. Unfortunately, some over-zealous (and obviously unsupervised) children separated these sets, placing all the individual dolls in a row. There are $n$ dolls in the row, each with an integer size. You need to reassemble the matryoshka sets, knowing neither the number of sets nor the number of dolls in each set. You know only that every complete set consists of dolls with consecutive sizes from $1$ to some number $m$, which may vary between the different sets. 

When reassembling the sets, you must follow these rules:
 - You can put a doll or a nested group of dolls only inside a larger doll.
 - You can combine two groups of dolls only if they are adjacent in the row.
 - Once a doll becomes a member of a group, it cannot be transferred to another group or permanently separated from the group. It can be temporarily separated only when combining two groups.

Your time is valuable, and you want to do this reassembly process as quickly as possible. The only time-consuming part of this task is opening and subsequently closing a doll, so you want to minimize how often you do this. For example, the minimum number of openings (and subsequent closings) when combining group [1, 2, 6] with the group [4] is two, since you have to open the dolls with sizes 6 and 4. When combining group [1, 2, 5] with the group [3, 4], you need to perform three openings.

Write a program to calculate the minimum number of openings required to combine all disassembled matryoshka sets.

-----Input-----
The input consists of a single test case. A test case consists of two lines. The first line contains one integer $n$ ($1 \le n \le 500$) representing the number of individual dolls in the row. The second line contains $n$ positive integers specifying the sizes of the dolls in the order they appear in the row. Each size is between $1$ and $500$ inclusive.

-----Output-----
Display the minimum number of openings required when reassembling the matryoshka sets. If reassembling cannot be done (some of the kids might have been excessively zealous and taken some dolls), display the word impossible.

-----Examples-----
Sample Input:
7
1 2 3 2 4 1 3
Sample Output:
7

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have some bags of coins. Each bag contains exactly $k$ coins. Exactly one bag contains only counterfeit coins (we’ll call this the fake bag), while all other bags contain only real coins. All real coins weigh exactly the same number of grams. All counterfeit coins weigh exactly the same number of grams. You don’t know the exact weights of a real or counterfeit coin. You do know a counterfeit coin is strictly heavier than a real coin, but you do not know exactly how much heavier it is. The weights of the coins are positive real numbers.

You have a scale which you can use at most $m$ times. The scale has a left and right side. To use the scale, you can place any number of coins, taken from any of the bags, on each side of the scale, as long as the total number of coins on the left and right sides are exactly equal. The scale will return a single real number $s$. If $s$ is zero, both sides of the scale weigh exactly the same. If $s$ is negative, the left side is $|s|$ grams heavier than the right side. If $s$ is positive, the right side is $s$ grams heavier than the left side. Coins can be reused multiple times for different weighings, and you are able to keep track of which bag each coin came from. You must specify beforehand all weighings you want to perform (so you cannot adjust what gets weighed in future trials based on the results of previous trials). After using the scale $m$ times, you would like to be able to determine which bag is the fake bag.

You are now wondering: given $m$ and $k$, what is the maximum number of bags for which you can always determine the fake bag? This number can get large, so output it modulo the large prime $998244353$.

-----Input-----
The single line of input contains two space-separated integers $m$ and $k$ ($1 \leq m, k \leq 10^6$), where $m$ is the number of weighings available to you and $k$ is the number of coins in each bag.

-----Output-----
Output a single integer, which is the maximum number of bags for which you can determine the fake bag in $m$ weighings, modulo the large prime $998244353$.




-----Sample Explanation-----
One way we can use $2$ weighings to determine the fake bag among $9$ bags, each containing $1$ coin, is as follows:
 - On the first weighing, put the coins from bags $1,2,3$ on the left, and the coins from bags $7,8,9$ on the right.
 - On the second weighing, put the coins from bags $1,4,7$ on the left, and the coins from bags $3,6,9$ on the right.

We can determine the fake bag as follows:
 - The first weighing tells us which group of bags $(1,2,3)$, $(4,5,6)$, $(7,8,9)$ contains the fake bag (e.g. if the left side is heavier, then group $(1,2,3)$ contains the fake bag, if both sides are equal, then group $(4,5,6)$ contains the fake bag, otherwise group $(7,8,9)$ contains the fake bag).
 - The second weighing will tell us which group of bags $(1,4,7)$, $(2,5,8)$, $(3,6,9)$ contains the fake bag. The resulting fake bag can be uniquely determined as a result.

-----Examples-----
Sample Input:
2 1
Sample Output:
9

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