meetforever/GRPO_CL huggingface dataset:
user: Polycarp has n dice d_1, d_2, ..., d_{n}. The i-th dice shows numbers from 1 to d_{i}. Polycarp rolled all the dice and the sum of numbers they showed is A. Agrippina didn't see which dice showed what number, she knows only the sum A and the values d_1, d_2, ..., d_{n}. However, she finds it enough to make a series of statements of the following type: dice i couldn't show number r. For example, if Polycarp had two six-faced dice and the total sum is A = 11, then Agrippina can state that each of the two dice couldn't show a value less than five (otherwise, the remaining dice must have a value of at least seven, which is impossible).

For each dice find the number of values for which it can be guaranteed that the dice couldn't show these values if the sum of the shown values is A.


-----Input-----

The first line contains two integers n, A (1 ≤ n ≤ 2·10^5, n ≤ A ≤ s) — the number of dice and the sum of shown values where s = d_1 + d_2 + ... + d_{n}.

The second line contains n integers d_1, d_2, ..., d_{n} (1 ≤ d_{i} ≤ 10^6), where d_{i} is the maximum value that the i-th dice can show.


-----Output-----

Print n integers b_1, b_2, ..., b_{n}, where b_{i} is the number of values for which it is guaranteed that the i-th dice couldn't show them.


-----Examples-----
Input
2 8
4 4

Output
3 3 
Input
1 3
5

Output
4 
Input
2 3
2 3

Output
0 1 


-----Note-----

In the first sample from the statement A equal to 8 could be obtained in the only case when both the first and the second dice show 4. Correspondingly, both dice couldn't show values 1, 2 or 3.

In the second sample from the statement A equal to 3 could be obtained when the single dice shows 3. Correspondingly, it couldn't show 1, 2, 4 or 5.

In the third sample from the statement A equal to 3 could be obtained when one dice shows 1 and the other dice shows 2. That's why the first dice doesn't have any values it couldn't show and the second dice couldn't show 3.
user: Andrewid the Android is a galaxy-famous detective. He is now investigating a case of frauds who make fake copies of the famous Stolp's gears, puzzles that are as famous as the Rubik's cube once was.

Its most important components are a button and a line of n similar gears. Each gear has n teeth containing all numbers from 0 to n - 1 in the counter-clockwise order. When you push a button, the first gear rotates clockwise, then the second gear rotates counter-clockwise, the the third gear rotates clockwise an so on.

Besides, each gear has exactly one active tooth. When a gear turns, a new active tooth is the one following after the current active tooth according to the direction of the rotation. For example, if n = 5, and the active tooth is the one containing number 0, then clockwise rotation makes the tooth with number 1 active, or the counter-clockwise rotating makes the tooth number 4 active.

Andrewid remembers that the real puzzle has the following property: you can push the button multiple times in such a way that in the end the numbers on the active teeth of the gears from first to last form sequence 0, 1, 2, ..., n - 1. Write a program that determines whether the given puzzle is real or fake.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 1000) — the number of gears.

The second line contains n digits a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ n - 1) — the sequence of active teeth: the active tooth of the i-th gear contains number a_{i}.


-----Output-----

In a single line print "Yes" (without the quotes), if the given Stolp's gears puzzle is real, and "No" (without the quotes) otherwise.


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

Output
Yes

Input
5
4 2 1 4 3

Output
Yes

Input
4
0 2 3 1

Output
No



-----Note-----

In the first sample test when you push the button for the first time, the sequence of active teeth will be 2 2 1, when you push it for the second time, you get 0 1 2.
user: Bob and Alice are often participating in various programming competitions. Like many competitive programmers, Alice and Bob have good and bad days. They noticed, that their lucky and unlucky days are repeating with some period. For example, for Alice days $[l_a; r_a]$ are lucky, then there are some unlucky days: $[r_a + 1; l_a + t_a - 1]$, and then there are lucky days again: $[l_a + t_a; r_a + t_a]$ and so on. In other words, the day is lucky for Alice if it lies in the segment $[l_a + k t_a; r_a + k t_a]$ for some non-negative integer $k$.

The Bob's lucky day have similar structure, however the parameters of his sequence are different: $l_b$, $r_b$, $t_b$. So a day is a lucky for Bob if it lies in a segment $[l_b + k t_b; r_b + k t_b]$, for some non-negative integer $k$.

Alice and Bob want to participate in team competitions together and so they want to find out what is the largest possible number of consecutive days, which are lucky for both Alice and Bob.


-----Input-----

The first line contains three integers $l_a$, $r_a$, $t_a$ ($0 \le l_a \le r_a \le t_a - 1, 2 \le t_a \le 10^9$) and describes Alice's lucky days.

The second line contains three integers $l_b$, $r_b$, $t_b$ ($0 \le l_b \le r_b \le t_b - 1, 2 \le t_b \le 10^9$) and describes Bob's lucky days.

It is guaranteed that both Alice and Bob have some unlucky days.


-----Output-----

Print one integer: the maximum number of days in the row that are lucky for both Alice and Bob.


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

Output
2

Input
0 1 3
2 3 6

Output
1



-----Note-----

The graphs below correspond to the two sample tests and show the lucky and unlucky days of Alice and Bob as well as the possible solutions for these tests.

[Image]

[Image]
user: Malek lives in an apartment block with 100 floors numbered from 0 to 99. The apartment has an elevator with a digital counter showing the floor that the elevator is currently on. The elevator shows each digit of a number with 7 light sticks by turning them on or off. The picture below shows how the elevator shows each digit.[Image]

One day when Malek wanted to go from floor 88 to floor 0 using the elevator he noticed that the counter shows number 89 instead of 88. Then when the elevator started moving the number on the counter changed to 87. After a little thinking Malek came to the conclusion that there is only one explanation for this: One of the sticks of the counter was broken. Later that day Malek was thinking about the broken stick and suddenly he came up with the following problem.

Suppose the digital counter is showing number n. Malek calls an integer x (0 ≤ x ≤ 99) good if it's possible that the digital counter was supposed to show x but because of some(possibly none) broken sticks it's showing n instead. Malek wants to know number of good integers for a specific n. So you must write a program that calculates this number. Please note that the counter always shows two digits.


-----Input-----

The only line of input contains exactly two digits representing number n (0 ≤ n ≤ 99). Note that n may have a leading zero.


-----Output-----

In the only line of the output print the number of good integers.


-----Examples-----
Input
89

Output
2

Input
00

Output
4

Input
73

Output
15



-----Note-----

In the first sample the counter may be supposed to show 88 or 89.

In the second sample the good integers are 00, 08, 80 and 88.

In the third sample the good integers are 03, 08, 09, 33, 38, 39, 73, 78, 79, 83, 88, 89, 93, 98, 99.
user: Kostya is a genial sculptor, he has an idea: to carve a marble sculpture in the shape of a sphere. Kostya has a friend Zahar who works at a career. Zahar knows about Kostya's idea and wants to present him a rectangular parallelepiped of marble from which he can carve the sphere. 

Zahar has n stones which are rectangular parallelepipeds. The edges sizes of the i-th of them are a_{i}, b_{i} and c_{i}. He can take no more than two stones and present them to Kostya. 

If Zahar takes two stones, he should glue them together on one of the faces in order to get a new piece of rectangular parallelepiped of marble. Thus, it is possible to glue a pair of stones together if and only if two faces on which they are glued together match as rectangles. In such gluing it is allowed to rotate and flip the stones in any way. 

Help Zahar choose such a present so that Kostya can carve a sphere of the maximum possible volume and present it to Zahar.


-----Input-----

The first line contains the integer n (1 ≤ n ≤ 10^5).

n lines follow, in the i-th of which there are three integers a_{i}, b_{i} and c_{i} (1 ≤ a_{i}, b_{i}, c_{i} ≤ 10^9) — the lengths of edges of the i-th stone. Note, that two stones may have exactly the same sizes, but they still will be considered two different stones.


-----Output-----

In the first line print k (1 ≤ k ≤ 2) the number of stones which Zahar has chosen. In the second line print k distinct integers from 1 to n — the numbers of stones which Zahar needs to choose. Consider that stones are numbered from 1 to n in the order as they are given in the input data.

You can print the stones in arbitrary order. If there are several answers print any of them. 


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

Output
1
1

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

Output
2
1 5



-----Note-----

In the first example we can connect the pairs of stones:  2 and 4, the size of the parallelepiped: 3 × 2 × 5, the radius of the inscribed sphere 1  2 and 5, the size of the parallelepiped: 3 × 2 × 8 or 6 × 2 × 4 or 3 × 4 × 4, the radius of the inscribed sphere 1, or 1, or 1.5 respectively.  2 and 6, the size of the parallelepiped: 3 × 5 × 4, the radius of the inscribed sphere 1.5  4 and 5, the size of the parallelepiped: 3 × 2 × 5, the radius of the inscribed sphere 1  5 and 6, the size of the parallelepiped: 3 × 4 × 5, the radius of the inscribed sphere 1.5 

Or take only one stone:  1 the size of the parallelepiped: 5 × 5 × 5, the radius of the inscribed sphere 2.5  2 the size of the parallelepiped: 3 × 2 × 4, the radius of the inscribed sphere 1  3 the size of the parallelepiped: 1 × 4 × 1, the radius of the inscribed sphere 0.5  4 the size of the parallelepiped: 2 × 1 × 3, the radius of the inscribed sphere 0.5  5 the size of the parallelepiped: 3 × 2 × 4, the radius of the inscribed sphere 1  6 the size of the parallelepiped: 3 × 3 × 4, the radius of the inscribed sphere 1.5 

It is most profitable to take only the first stone.
user: Find the largest integer that can be formed with exactly N matchsticks, under the following conditions:
 - Every digit in the integer must be one of the digits A_1, A_2, ..., A_M (1 \leq A_i \leq 9).
 - The number of matchsticks used to form digits 1, 2, 3, 4, 5, 6, 7, 8, 9 should be 2, 5, 5, 4, 5, 6, 3, 7, 6, respectively.

-----Constraints-----
 - All values in input are integers.
 - 2 \leq N \leq 10^4
 - 1 \leq M \leq 9
 - 1 \leq A_i \leq 9
 - A_i are all different.
 - There exists an integer that can be formed by exactly N matchsticks under the conditions.

-----Input-----
Input is given from Standard Input in the following format:
N M
A_1 A_2 ... A_M

-----Output-----
Print the largest integer that can be formed with exactly N matchsticks under the conditions in the problem statement.

-----Sample Input-----
20 4
3 7 8 4

-----Sample Output-----
777773

The integer 777773 can be formed with 3 + 3 + 3 + 3 + 3 + 5 = 20 matchsticks, and this is the largest integer that can be formed by 20 matchsticks under the conditions.
user: You are given a sequence of positive integers of length N, A=a_1,a_2,…,a_{N}, and an integer K.
How many contiguous subsequences of A satisfy the following condition?
 - (Condition) The sum of the elements in the contiguous subsequence is at least K.
We consider two contiguous subsequences different if they derive from different positions in A, even if they are the same in content.
Note that the answer may not fit into a 32-bit integer type.

-----Constraints-----
 - 1 \leq a_i \leq 10^5
 - 1 \leq N \leq 10^5
 - 1 \leq K \leq 10^{10}

-----Input-----
Input is given from Standard Input in the following format:
N K
a_1 a_2 ... a_N

-----Output-----
Print the number of contiguous subsequences of A that satisfy the condition.

-----Sample Input-----
4 10
6 1 2 7

-----Sample Output-----
2

The following two contiguous subsequences satisfy the condition:
 - A[1..4]=a_1,a_2,a_3,a_4, with the sum of 16
 - A[2..4]=a_2,a_3,a_4, with the sum of 10
user: There is a grid of square cells with H horizontal rows and W vertical columns. The cell at the i-th row and the j-th column will be denoted as Cell (i, j).
In Cell (i, j), a_{ij} coins are placed.
You can perform the following operation any number of times:
Operation: Choose a cell that was not chosen before and contains one or more coins, then move one of those coins to a vertically or horizontally adjacent cell.
Maximize the number of cells containing an even number of coins.

-----Constraints-----
 - All values in input are integers.
 - 1 \leq H, W \leq 500
 - 0 \leq a_{ij} \leq 9

-----Input-----
Input is given from Standard Input in the following format:
H W
a_{11} a_{12} ... a_{1W}
a_{21} a_{22} ... a_{2W}
:
a_{H1} a_{H2} ... a_{HW}

-----Output-----
Print a sequence of operations that maximizes the number of cells containing an even number of coins, in the following format:
N
y_1 x_1 y_1' x_1'
y_2 x_2 y_2' x_2'
:
y_N x_N y_N' x_N'

That is, in the first line, print an integer N between 0 and H \times W (inclusive), representing the number of operations.
In the (i+1)-th line (1 \leq i \leq N), print four integers y_i, x_i, y_i' and x_i' (1 \leq y_i, y_i' \leq H and 1 \leq x_i, x_i' \leq W), representing the i-th operation. These four integers represents the operation of moving one of the coins placed in Cell (y_i, x_i) to a vertically or horizontally adjacent cell, (y_i', x_i').
Note that if the specified operation violates the specification in the problem statement or the output format is invalid, it will result in Wrong Answer.

-----Sample Input-----
2 3
1 2 3
0 1 1

-----Sample Output-----
3
2 2 2 3
1 1 1 2
1 3 1 2

Every cell contains an even number of coins after the following sequence of operations:
 - Move the coin in Cell (2, 2) to Cell (2, 3).
 - Move the coin in Cell (1, 1) to Cell (1, 2).
 - Move one of the coins in Cell (1, 3) to Cell (1, 2).
user: There is a building with n rooms, numbered 1 to n.
We can move from any room to any other room in the building.
Let us call the following event a move: a person in some room i goes to another room j~ (i \neq j).
Initially, there was one person in each room in the building.
After that, we know that there were exactly k moves happened up to now.
We are interested in the number of people in each of the n rooms now. How many combinations of numbers of people in the n rooms are possible?
Find the count modulo (10^9 + 7).

-----Constraints-----
 - All values in input are integers.
 - 3 \leq n \leq 2 \times 10^5
 - 2 \leq k \leq 10^9

-----Input-----
Input is given from Standard Input in the following format:
n k

-----Output-----
Print the number of possible combinations of numbers of people in the n rooms now, modulo (10^9 + 7).

-----Sample Input-----
3 2

-----Sample Output-----
10

Let c_1, c_2, and c_3 be the number of people in Room 1, 2, and 3 now, respectively. There are 10 possible combination of (c_1, c_2, c_3):
 - (0, 0, 3)
 - (0, 1, 2)
 - (0, 2, 1)
 - (0, 3, 0)
 - (1, 0, 2)
 - (1, 1, 1)
 - (1, 2, 0)
 - (2, 0, 1)
 - (2, 1, 0)
 - (3, 0, 0)
For example, (c_1, c_2, c_3) will be (0, 1, 2) if the person in Room 1 goes to Room 2 and then one of the persons in Room 2 goes to Room 3.
user: Inna and Dima decided to surprise Sereja. They brought a really huge candy matrix, it's big even for Sereja! Let's number the rows of the giant matrix from 1 to n from top to bottom and the columns — from 1 to m, from left to right. We'll represent the cell on the intersection of the i-th row and j-th column as (i, j). Just as is expected, some cells of the giant candy matrix contain candies. Overall the matrix has p candies: the k-th candy is at cell (x_{k}, y_{k}).

The time moved closer to dinner and Inna was already going to eat p of her favourite sweets from the matrix, when suddenly Sereja (for the reason he didn't share with anyone) rotated the matrix x times clockwise by 90 degrees. Then he performed the horizontal rotate of the matrix y times. And then he rotated the matrix z times counterclockwise by 90 degrees. The figure below shows how the rotates of the matrix looks like. [Image] 

Inna got really upset, but Duma suddenly understood two things: the candies didn't get damaged and he remembered which cells contained Inna's favourite sweets before Sereja's strange actions. Help guys to find the new coordinates in the candy matrix after the transformation Sereja made!


-----Input-----

The first line of the input contains fix integers n, m, x, y, z, p (1 ≤ n, m ≤ 10^9; 0 ≤ x, y, z ≤ 10^9; 1 ≤ p ≤ 10^5).

Each of the following p lines contains two integers x_{k}, y_{k} (1 ≤ x_{k} ≤ n; 1 ≤ y_{k} ≤ m) — the initial coordinates of the k-th candy. Two candies can lie on the same cell.


-----Output-----

For each of the p candies, print on a single line its space-separated new coordinates.


-----Examples-----
Input
3 3 3 1 1 9
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

Output
1 3
1 2
1 1
2 3
2 2
2 1
3 3
3 2
3 1



-----Note-----

Just for clarity. Horizontal rotating is like a mirroring of the matrix. For matrix:

QWER      REWQ 

ASDF  ->  FDSA

ZXCV      VCXZ
user: 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
user: Many modern text editors automatically check the spelling of the user's text. Some editors even suggest how to correct typos.

In this problem your task to implement a small functionality to correct two types of typos in a word. We will assume that three identical letters together is a typo (for example, word "helllo" contains a typo). Besides, a couple of identical letters immediately followed by another couple of identical letters is a typo too (for example, words "helloo" and "wwaatt" contain typos).

Write a code that deletes the minimum number of letters from a word, correcting described typos in the word. You are allowed to delete letters from both ends and from the middle of the word.


-----Input-----

The single line of the input contains word s, its length is from 1 to 200000 characters. The given word s consists of lowercase English letters.


-----Output-----

Print such word t that it doesn't contain any typos described in the problem statement and is obtained from s by deleting the least number of letters.

If there are multiple solutions, print any of them.


-----Examples-----
Input
helloo

Output
hello

Input
woooooow

Output
woow



-----Note-----

The second valid answer to the test from the statement is "heloo".
user: Gennady owns a small hotel in the countryside where he lives a peaceful life. He loves to take long walks, watch sunsets and play cards with tourists staying in his hotel. His favorite game is called "Mau-Mau".

To play Mau-Mau, you need a pack of $52$ cards. Each card has a suit (Diamonds — D, Clubs — C, Spades — S, or Hearts — H), and a rank (2, 3, 4, 5, 6, 7, 8, 9, T, J, Q, K, or A).

At the start of the game, there is one card on the table and you have five cards in your hand. You can play a card from your hand if and only if it has the same rank or the same suit as the card on the table.

In order to check if you'd be a good playing partner, Gennady has prepared a task for you. Given the card on the table and five cards in your hand, check if you can play at least one card.


-----Input-----

The first line of the input contains one string which describes the card on the table. The second line contains five strings which describe the cards in your hand.

Each string is two characters long. The first character denotes the rank and belongs to the set $\{{\tt 2}, {\tt 3}, {\tt 4}, {\tt 5}, {\tt 6}, {\tt 7}, {\tt 8}, {\tt 9}, {\tt T}, {\tt J}, {\tt Q}, {\tt K}, {\tt A}\}$. The second character denotes the suit and belongs to the set $\{{\tt D}, {\tt C}, {\tt S}, {\tt H}\}$.

All the cards in the input are different.


-----Output-----

If it is possible to play a card from your hand, print one word "YES". Otherwise, print "NO".

You can print each letter in any case (upper or lower).


-----Examples-----
Input
AS
2H 4C TH JH AD

Output
YES

Input
2H
3D 4C AC KD AS

Output
NO

Input
4D
AS AC AD AH 5H

Output
YES



-----Note-----

In the first example, there is an Ace of Spades (AS) on the table. You can play an Ace of Diamonds (AD) because both of them are Aces.

In the second example, you cannot play any card.

In the third example, you can play an Ace of Diamonds (AD) because it has the same suit as a Four of Diamonds (4D), which lies on the table.
user: After winning gold and silver in IOI 2014, Akshat and Malvika want to have some fun. Now they are playing a game on a grid made of n horizontal and m vertical sticks.

An intersection point is any point on the grid which is formed by the intersection of one horizontal stick and one vertical stick.

In the grid shown below, n = 3 and m = 3. There are n + m = 6 sticks in total (horizontal sticks are shown in red and vertical sticks are shown in green). There are n·m = 9 intersection points, numbered from 1 to 9.

 [Image] 

The rules of the game are very simple. The players move in turns. Akshat won gold, so he makes the first move. During his/her move, a player must choose any remaining intersection point and remove from the grid all sticks which pass through this point. A player will lose the game if he/she cannot make a move (i.e. there are no intersection points remaining on the grid at his/her move).

Assume that both players play optimally. Who will win the game?


-----Input-----

The first line of input contains two space-separated integers, n and m (1 ≤ n, m ≤ 100).


-----Output-----

Print a single line containing "Akshat" or "Malvika" (without the quotes), depending on the winner of the game.


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

Output
Malvika

Input
2 3

Output
Malvika

Input
3 3

Output
Akshat



-----Note-----

Explanation of the first sample:

The grid has four intersection points, numbered from 1 to 4.

 [Image] 

If Akshat chooses intersection point 1, then he will remove two sticks (1 - 2 and 1 - 3). The resulting grid will look like this.

 [Image] 

Now there is only one remaining intersection point (i.e. 4). Malvika must choose it and remove both remaining sticks. After her move the grid will be empty.

In the empty grid, Akshat cannot make any move, hence he will lose.

Since all 4 intersection points of the grid are equivalent, Akshat will lose no matter which one he picks.