meetforever/GRPO_CL huggingface dataset:
user: Lenny is playing a game on a 3 × 3 grid of lights. In the beginning of the game all lights are switched on. Pressing any of the lights will toggle it and all side-adjacent lights. The goal of the game is to switch all the lights off. We consider the toggling as follows: if the light was switched on then it will be switched off, if it was switched off then it will be switched on.

Lenny has spent some time playing with the grid and by now he has pressed each light a certain number of times. Given the number of times each light is pressed, you have to print the current state of each light.


-----Input-----

The input consists of three rows. Each row contains three integers each between 0 to 100 inclusive. The j-th number in the i-th row is the number of times the j-th light of the i-th row of the grid is pressed.


-----Output-----

Print three lines, each containing three characters. The j-th character of the i-th line is "1" if and only if the corresponding light is switched on, otherwise it's "0".


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

Output
001
010
100

Input
1 0 1
8 8 8
2 0 3

Output
010
011
100
user: Recently Ivan noticed an array a while debugging his code. Now Ivan can't remember this array, but the bug he was trying to fix didn't go away, so Ivan thinks that the data from this array might help him to reproduce the bug.

Ivan clearly remembers that there were n elements in the array, and each element was not less than 1 and not greater than n. Also he remembers q facts about the array. There are two types of facts that Ivan remembers:  1 l_{i} r_{i} v_{i} — for each x such that l_{i} ≤ x ≤ r_{i} a_{x} ≥ v_{i};  2 l_{i} r_{i} v_{i} — for each x such that l_{i} ≤ x ≤ r_{i} a_{x} ≤ v_{i}. 

Also Ivan thinks that this array was a permutation, but he is not so sure about it. He wants to restore some array that corresponds to the q facts that he remembers and is very similar to permutation. Formally, Ivan has denoted the cost of array as follows:

$\operatorname{cos} t = \sum_{i = 1}^{n}(\operatorname{cnt}(i))^{2}$, where cnt(i) is the number of occurences of i in the array.

Help Ivan to determine minimum possible cost of the array that corresponds to the facts!


-----Input-----

The first line contains two integer numbers n and q (1 ≤ n ≤ 50, 0 ≤ q ≤ 100).

Then q lines follow, each representing a fact about the array. i-th line contains the numbers t_{i}, l_{i}, r_{i} and v_{i} for i-th fact (1 ≤ t_{i} ≤ 2, 1 ≤ l_{i} ≤ r_{i} ≤ n, 1 ≤ v_{i} ≤ n, t_{i} denotes the type of the fact).


-----Output-----

If the facts are controversial and there is no array that corresponds to them, print -1. Otherwise, print minimum possible cost of the array.


-----Examples-----
Input
3 0

Output
3

Input
3 1
1 1 3 2

Output
5

Input
3 2
1 1 3 2
2 1 3 2

Output
9

Input
3 2
1 1 3 2
2 1 3 1

Output
-1
user: You are given three positive integers x, y, n. Your task is to find the nearest fraction to fraction [Image] whose denominator is no more than n. 

Formally, you should find such pair of integers a, b (1 ≤ b ≤ n; 0 ≤ a) that the value $|\frac{x}{y} - \frac{a}{b}|$ is as minimal as possible.

If there are multiple "nearest" fractions, choose the one with the minimum denominator. If there are multiple "nearest" fractions with the minimum denominator, choose the one with the minimum numerator.


-----Input-----

A single line contains three integers x, y, n (1 ≤ x, y, n ≤ 10^5).


-----Output-----

Print the required fraction in the format "a/b" (without quotes).


-----Examples-----
Input
3 7 6

Output
2/5

Input
7 2 4

Output
7/2
user: Zane the wizard is going to perform a magic show shuffling the cups.

There are n cups, numbered from 1 to n, placed along the x-axis on a table that has m holes on it. More precisely, cup i is on the table at the position x = i.

The problematic bone is initially at the position x = 1. Zane will confuse the audience by swapping the cups k times, the i-th time of which involves the cups at the positions x = u_{i} and x = v_{i}. If the bone happens to be at the position where there is a hole at any time, it will fall into the hole onto the ground and will not be affected by future swapping operations.

Do not forget that Zane is a wizard. When he swaps the cups, he does not move them ordinarily. Instead, he teleports the cups (along with the bone, if it is inside) to the intended positions. Therefore, for example, when he swaps the cup at x = 4 and the one at x = 6, they will not be at the position x = 5 at any moment during the operation. [Image] 

Zane’s puppy, Inzane, is in trouble. Zane is away on his vacation, and Inzane cannot find his beloved bone, as it would be too exhausting to try opening all the cups. Inzane knows that the Codeforces community has successfully helped Zane, so he wants to see if it could help him solve his problem too. Help Inzane determine the final position of the bone.


-----Input-----

The first line contains three integers n, m, and k (2 ≤ n ≤ 10^6, 1 ≤ m ≤ n, 1 ≤ k ≤ 3·10^5) — the number of cups, the number of holes on the table, and the number of swapping operations, respectively.

The second line contains m distinct integers h_1, h_2, ..., h_{m} (1 ≤ h_{i} ≤ n) — the positions along the x-axis where there is a hole on the table.

Each of the next k lines contains two integers u_{i} and v_{i} (1 ≤ u_{i}, v_{i} ≤ n, u_{i} ≠ v_{i}) — the positions of the cups to be swapped.


-----Output-----

Print one integer — the final position along the x-axis of the bone.


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

Output
1
Input
5 1 2
2
1 2
2 4

Output
2


-----Note-----

In the first sample, after the operations, the bone becomes at x = 2, x = 5, x = 7, and x = 1, respectively.

In the second sample, after the first operation, the bone becomes at x = 2, and falls into the hole onto the ground.
user: Due to the increase in the number of students of Berland State University it was decided to equip a new computer room. You were given the task of buying mouses, and you have to spend as little as possible. After all, the country is in crisis!

The computers bought for the room were different. Some of them had only USB ports, some — only PS/2 ports, and some had both options.

You have found a price list of a certain computer shop. In it, for m mouses it is specified the cost and the type of the port that is required to plug the mouse in (USB or PS/2). Each mouse from the list can be bought at most once.

You want to buy some set of mouses from the given price list in such a way so that you maximize the number of computers equipped with mouses (it is not guaranteed that you will be able to equip all of the computers), and in case of equality of this value you want to minimize the total cost of mouses you will buy.


-----Input-----

The first line contains three integers a, b and c (0 ≤ a, b, c ≤ 10^5)  — the number of computers that only have USB ports, the number of computers, that only have PS/2 ports, and the number of computers, that have both options, respectively.

The next line contains one integer m (0 ≤ m ≤ 3·10^5)  — the number of mouses in the price list.

The next m lines each describe another mouse. The i-th line contains first integer val_{i} (1 ≤ val_{i} ≤ 10^9)  — the cost of the i-th mouse, then the type of port (USB or PS/2) that is required to plug the mouse in.


-----Output-----

Output two integers separated by space — the number of equipped computers and the total cost of the mouses you will buy.


-----Example-----
Input
2 1 1
4
5 USB
6 PS/2
3 PS/2
7 PS/2

Output
3 14



-----Note-----

In the first example you can buy the first three mouses. This way you will equip one of the computers that has only a USB port with a USB mouse, and the two PS/2 mouses you will plug into the computer with PS/2 port and the computer with both ports.
user: Kyoya Ootori is selling photobooks of the Ouran High School Host Club. He has 26 photos, labeled "a" to "z", and he has compiled them into a photo booklet with some photos in some order (possibly with some photos being duplicated). A photo booklet can be described as a string of lowercase letters, consisting of the photos in the booklet in order. He now wants to sell some "special edition" photobooks, each with one extra photo inserted anywhere in the book. He wants to make as many distinct photobooks as possible, so he can make more money. He asks Haruhi, how many distinct photobooks can he make by inserting one extra photo into the photobook he already has?

Please help Haruhi solve this problem.


-----Input-----

The first line of input will be a single string s (1 ≤ |s| ≤ 20). String s consists only of lowercase English letters. 


-----Output-----

Output a single integer equal to the number of distinct photobooks Kyoya Ootori can make.


-----Examples-----
Input
a

Output
51

Input
hi

Output
76



-----Note-----

In the first case, we can make 'ab','ac',...,'az','ba','ca',...,'za', and 'aa', producing a total of 51 distinct photo booklets.
user: King of Berland Berl IV has recently died. Hail Berl V! As a sign of the highest achievements of the deceased king the new king decided to build a mausoleum with Berl IV's body on the main square of the capital.

The mausoleum will be constructed from 2n blocks, each of them has the shape of a cuboid. Each block has the bottom base of a 1 × 1 meter square. Among the blocks, exactly two of them have the height of one meter, exactly two have the height of two meters, ..., exactly two have the height of n meters.

The blocks are arranged in a row without spacing one after the other. Of course, not every arrangement of blocks has the form of a mausoleum. In order to make the given arrangement in the form of the mausoleum, it is necessary that when you pass along the mausoleum, from one end to the other, the heights of the blocks first were non-decreasing (i.e., increasing or remained the same), and then — non-increasing (decrease or remained unchanged). It is possible that any of these two areas will be omitted. For example, the following sequences of block height meet this requirement:

  [1, 2, 2, 3, 4, 4, 3, 1];  [1, 1];  [2, 2, 1, 1];  [1, 2, 3, 3, 2, 1]. 

Suddenly, k more requirements appeared. Each of the requirements has the form: "h[x_{i}] sign_{i} h[y_{i}]", where h[t] is the height of the t-th block, and a sign_{i} is one of the five possible signs: '=' (equals), '<' (less than), '>' (more than), '<=' (less than or equals), '>=' (more than or equals). Thus, each of the k additional requirements is given by a pair of indexes x_{i}, y_{i} (1 ≤ x_{i}, y_{i} ≤ 2n) and sign sign_{i}.

Find the number of possible ways to rearrange the blocks so that both the requirement about the shape of the mausoleum (see paragraph 3) and the k additional requirements were met.


-----Input-----

The first line of the input contains integers n and k (1 ≤ n ≤ 35, 0 ≤ k ≤ 100) — the number of pairs of blocks and the number of additional requirements.

Next k lines contain listed additional requirements, one per line in the format "x_{i} sign_{i} y_{i}" (1 ≤ x_{i}, y_{i} ≤ 2n), and the sign is on of the list of the five possible signs.


-----Output-----

Print the sought number of ways.


-----Examples-----
Input
3 0

Output
9

Input
3 1
2 > 3

Output
1

Input
4 1
3 = 6

Output
3
user: Fafa owns a company that works on huge projects. There are n employees in Fafa's company. Whenever the company has a new project to start working on, Fafa has to divide the tasks of this project among all the employees.

Fafa finds doing this every time is very tiring for him. So, he decided to choose the best l employees in his company as team leaders. Whenever there is a new project, Fafa will divide the tasks among only the team leaders and each team leader will be responsible of some positive number of employees to give them the tasks. To make this process fair for the team leaders, each one of them should be responsible for the same number of employees. Moreover, every employee, who is not a team leader, has to be under the responsibility of exactly one team leader, and no team leader is responsible for another team leader.

Given the number of employees n, find in how many ways Fafa could choose the number of team leaders l in such a way that it is possible to divide employees between them evenly.


-----Input-----

The input consists of a single line containing a positive integer n (2 ≤ n ≤ 10^5) — the number of employees in Fafa's company.


-----Output-----

Print a single integer representing the answer to the problem.


-----Examples-----
Input
2

Output
1

Input
10

Output
3



-----Note-----

In the second sample Fafa has 3 ways:  choose only 1 employee as a team leader with 9 employees under his responsibility.  choose 2 employees as team leaders with 4 employees under the responsibility of each of them.  choose 5 employees as team leaders with 1 employee under the responsibility of each of them.
user: Suppose you have a special $x$-$y$-counter. This counter can store some value as a decimal number; at first, the counter has value $0$. 

The counter performs the following algorithm: it prints its lowest digit and, after that, adds either $x$ or $y$ to its value. So all sequences this counter generates are starting from $0$. For example, a $4$-$2$-counter can act as follows:  it prints $0$, and adds $4$ to its value, so the current value is $4$, and the output is $0$;  it prints $4$, and adds $4$ to its value, so the current value is $8$, and the output is $04$;  it prints $8$, and adds $4$ to its value, so the current value is $12$, and the output is $048$;  it prints $2$, and adds $2$ to its value, so the current value is $14$, and the output is $0482$;  it prints $4$, and adds $4$ to its value, so the current value is $18$, and the output is $04824$. 

This is only one of the possible outputs; for example, the same counter could generate $0246802468024$ as the output, if we chose to add $2$ during each step.

You wrote down a printed sequence from one of such $x$-$y$-counters. But the sequence was corrupted and several elements from the sequence could be erased.

Now you'd like to recover data you've lost, but you don't even know the type of the counter you used. You have a decimal string $s$ — the remaining data of the sequence. 

For all $0 \le x, y < 10$, calculate the minimum number of digits you have to insert in the string $s$ to make it a possible output of the $x$-$y$-counter. Note that you can't change the order of digits in string $s$ or erase any of them; only insertions are allowed.


-----Input-----

The first line contains a single string $s$ ($1 \le |s| \le 2 \cdot 10^6$, $s_i \in \{\text{0} - \text{9}\}$) — the remaining data you have. It's guaranteed that $s_1 = 0$.


-----Output-----

Print a $10 \times 10$ matrix, where the $j$-th integer ($0$-indexed) on the $i$-th line ($0$-indexed too) is equal to the minimum number of digits you have to insert in the string $s$ to make it a possible output of the $i$-$j$-counter, or $-1$ if there is no way to do so.


-----Example-----
Input
0840

Output
-1 17 7 7 7 -1 2 17 2 7 
17 17 7 5 5 5 2 7 2 7 
7 7 7 4 3 7 1 7 2 5 
7 5 4 7 3 3 2 5 2 3 
7 5 3 3 7 7 1 7 2 7 
-1 5 7 3 7 -1 2 9 2 7 
2 2 1 2 1 2 2 2 0 1 
17 7 7 5 7 9 2 17 2 3 
2 2 2 2 2 2 0 2 2 2 
7 7 5 3 7 7 1 3 2 7 



-----Note-----

Let's take, for example, $4$-$3$-counter. One of the possible outcomes the counter could print is $0(4)8(1)4(7)0$ (lost elements are in the brackets).

One of the possible outcomes a $2$-$3$-counter could print is $0(35)8(1)4(7)0$.

The $6$-$8$-counter could print exactly the string $0840$.
user: The Little Elephant loves chess very much. 

One day the Little Elephant and his friend decided to play chess. They've got the chess pieces but the board is a problem. They've got an 8 × 8 checkered board, each square is painted either black or white. The Little Elephant and his friend know that a proper chessboard doesn't have any side-adjacent cells with the same color and the upper left cell is white. To play chess, they want to make the board they have a proper chessboard. For that the friends can choose any row of the board and cyclically shift the cells of the chosen row, that is, put the last (rightmost) square on the first place in the row and shift the others one position to the right. You can run the described operation multiple times (or not run it at all).

For example, if the first line of the board looks like that "BBBBBBWW" (the white cells of the line are marked with character "W", the black cells are marked with character "B"), then after one cyclic shift it will look like that "WBBBBBBW".

Help the Little Elephant and his friend to find out whether they can use any number of the described operations to turn the board they have into a proper chessboard.


-----Input-----

The input consists of exactly eight lines. Each line contains exactly eight characters "W" or "B" without any spaces: the j-th character in the i-th line stands for the color of the j-th cell of the i-th row of the elephants' board. Character "W" stands for the white color, character "B" stands for the black color.

Consider the rows of the board numbered from 1 to 8 from top to bottom, and the columns — from 1 to 8 from left to right. The given board can initially be a proper chessboard.


-----Output-----

In a single line print "YES" (without the quotes), if we can make the board a proper chessboard and "NO" (without the quotes) otherwise.


-----Examples-----
Input
WBWBWBWB
BWBWBWBW
BWBWBWBW
BWBWBWBW
WBWBWBWB
WBWBWBWB
BWBWBWBW
WBWBWBWB

Output
YES

Input
WBWBWBWB
WBWBWBWB
BBWBWWWB
BWBWBWBW
BWBWBWBW
BWBWBWWW
BWBWBWBW
BWBWBWBW

Output
NO



-----Note-----

In the first sample you should shift the following lines one position to the right: the 3-rd, the 6-th, the 7-th and the 8-th.

In the second sample there is no way you can achieve the goal.
user: In a dream Marco met an elderly man with a pair of black glasses. The man told him the key to immortality and then disappeared with the wind of time.

When he woke up, he only remembered that the key was a sequence of positive integers of some length n, but forgot the exact sequence. Let the elements of the sequence be a_1, a_2, ..., a_{n}. He remembered that he calculated gcd(a_{i}, a_{i} + 1, ..., a_{j}) for every 1 ≤ i ≤ j ≤ n and put it into a set S. gcd here means the greatest common divisor.

Note that even if a number is put into the set S twice or more, it only appears once in the set.

Now Marco gives you the set S and asks you to help him figure out the initial sequence. If there are many solutions, print any of them. It is also possible that there are no sequences that produce the set S, in this case print -1.


-----Input-----

The first line contains a single integer m (1 ≤ m ≤ 1000) — the size of the set S.

The second line contains m integers s_1, s_2, ..., s_{m} (1 ≤ s_{i} ≤ 10^6) — the elements of the set S. It's guaranteed that the elements of the set are given in strictly increasing order, that means s_1 < s_2 < ... < s_{m}.


-----Output-----

If there is no solution, print a single line containing -1.

Otherwise, in the first line print a single integer n denoting the length of the sequence, n should not exceed 4000.

In the second line print n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^6) — the sequence.

We can show that if a solution exists, then there is a solution with n not exceeding 4000 and a_{i} not exceeding 10^6.

If there are multiple solutions, print any of them.


-----Examples-----
Input
4
2 4 6 12

Output
3
4 6 12
Input
2
2 3

Output
-1



-----Note-----

In the first example 2 = gcd(4, 6), the other elements from the set appear in the sequence, and we can show that there are no values different from 2, 4, 6 and 12 among gcd(a_{i}, a_{i} + 1, ..., a_{j}) for every 1 ≤ i ≤ j ≤ n.
user: The capital of Berland has n multifloor buildings. The architect who built up the capital was very creative, so all the houses were built in one row.

Let's enumerate all the houses from left to right, starting with one. A house is considered to be luxurious if the number of floors in it is strictly greater than in all the houses with larger numbers. In other words, a house is luxurious if the number of floors in it is strictly greater than in all the houses, which are located to the right from it. In this task it is assumed that the heights of floors in the houses are the same.

The new architect is interested in n questions, i-th of them is about the following: "how many floors should be added to the i-th house to make it luxurious?" (for all i from 1 to n, inclusive). You need to help him cope with this task.

Note that all these questions are independent from each other — the answer to the question for house i does not affect other answers (i.e., the floors to the houses are not actually added).


-----Input-----

The first line of the input contains a single number n (1 ≤ n ≤ 10^5) — the number of houses in the capital of Berland.

The second line contains n space-separated positive integers h_{i} (1 ≤ h_{i} ≤ 10^9), where h_{i} equals the number of floors in the i-th house. 


-----Output-----

Print n integers a_1, a_2, ..., a_{n}, where number a_{i} is the number of floors that need to be added to the house number i to make it luxurious. If the house is already luxurious and nothing needs to be added to it, then a_{i} should be equal to zero.

All houses are numbered from left to right, starting from one.


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

Output
3 2 0 2 0 
Input
4
3 2 1 4

Output
2 3 4 0
user: Vasily has a number a, which he wants to turn into a number b. For this purpose, he can do two types of operations:  multiply the current number by 2 (that is, replace the number x by 2·x);  append the digit 1 to the right of current number (that is, replace the number x by 10·x + 1). 

You need to help Vasily to transform the number a into the number b using only the operations described above, or find that it is impossible.

Note that in this task you are not required to minimize the number of operations. It suffices to find any way to transform a into b.


-----Input-----

The first line contains two positive integers a and b (1 ≤ a < b ≤ 10^9) — the number which Vasily has and the number he wants to have.


-----Output-----

If there is no way to get b from a, print "NO" (without quotes).

Otherwise print three lines. On the first line print "YES" (without quotes). The second line should contain single integer k — the length of the transformation sequence. On the third line print the sequence of transformations x_1, x_2, ..., x_{k}, where:  x_1 should be equal to a,  x_{k} should be equal to b,  x_{i} should be obtained from x_{i} - 1 using any of two described operations (1 < i ≤ k). 

If there are multiple answers, print any of them.


-----Examples-----
Input
2 162

Output
YES
5
2 4 8 81 162 

Input
4 42

Output
NO

Input
100 40021

Output
YES
5
100 200 2001 4002 40021
user: The start of the new academic year brought about the problem of accommodation students into dormitories. One of such dormitories has a a × b square meter wonder room. The caretaker wants to accommodate exactly n students there. But the law says that there must be at least 6 square meters per student in a room (that is, the room for n students must have the area of at least 6n square meters). The caretaker can enlarge any (possibly both) side of the room by an arbitrary positive integer of meters. Help him change the room so as all n students could live in it and the total area of the room was as small as possible.


-----Input-----

The first line contains three space-separated integers n, a and b (1 ≤ n, a, b ≤ 10^9) — the number of students and the sizes of the room.


-----Output-----

Print three integers s, a_1 and b_1 (a ≤ a_1; b ≤ b_1) — the final area of the room and its sizes. If there are multiple optimal solutions, print any of them.


-----Examples-----
Input
3 3 5

Output
18
3 6

Input
2 4 4

Output
16
4 4