meetforever/GRPO_CL huggingface dataset:
user: Count the pairs of length-N sequences consisting of integers between 1 and M (inclusive), A_1, A_2, \cdots, A_{N} and B_1, B_2, \cdots, B_{N}, that satisfy all of the following conditions:
 - A_i \neq B_i, for every i such that 1\leq i\leq N.
 - A_i \neq A_j and B_i \neq B_j, for every (i, j) such that 1\leq i < j\leq N.
Since the count can be enormous, print it modulo (10^9+7).

-----Constraints-----
 - 1\leq N \leq M \leq 5\times10^5
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N M

-----Output-----
Print the count modulo (10^9+7).

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

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

A_1=1,A_2=2,B_1=2,B_2=1 and A_1=2,A_2=1,B_1=1,B_2=2 satisfy the conditions.
user: This morning Chef wants to jump a little. In a few minutes he will arrive at the point 0. Then he will perform a lot of jumps in such a sequence: 1-jump, 2-jump, 3-jump, 1-jump, 2-jump, 3-jump, 1-jump, and so on.
1-jump means that if Chef is at the point x, he will jump to the point x+1. 
2-jump means that if Chef is at the point x, he will jump to the point x+2. 
3-jump means that if Chef is at the point x, he will jump to the point x+3. 
Before the start Chef asks you: will he arrive at the point a after some number of jumps?

-----Input-----

The first line contains a single integer a denoting the point Chef asks about. 

-----Output-----
Output "yes" without a quotes if Chef can arrive at point a or "no" without a quotes otherwise.

-----Constraints-----

- 0 ≤ a ≤ 1018

-----Example-----
Input:
0

Output:
yes

Input:
1

Output:
yes

Input:
2

Output:
no

Input:
3

Output:
yes

Input:
6

Output:
yes

Input:
7

Output:
yes

Input:
10

Output:
no

-----Explanation-----
The first reached points are: 0 (+1) 1 (+2) 3 (+3) 6 (+1) 7, and so on.
user: You have a new professor of graph theory and he speaks very quickly. You come up with the following plan to keep up with his lecture and make notes.

You know two languages, and the professor is giving the lecture in the first one. The words in both languages consist of lowercase English characters, each language consists of several words. For each language, all words are distinct, i.e. they are spelled differently. Moreover, the words of these languages have a one-to-one correspondence, that is, for each word in each language, there exists exactly one word in the other language having has the same meaning.

You can write down every word the professor says in either the first language or the second language. Of course, during the lecture you write down each word in the language in which the word is shorter. In case of equal lengths of the corresponding words you prefer the word of the first language.

You are given the text of the lecture the professor is going to read. Find out how the lecture will be recorded in your notes.


-----Input-----

The first line contains two integers, n and m (1 ≤ n ≤ 3000, 1 ≤ m ≤ 3000) — the number of words in the professor's lecture and the number of words in each of these languages.

The following m lines contain the words. The i-th line contains two strings a_{i}, b_{i} meaning that the word a_{i} belongs to the first language, the word b_{i} belongs to the second language, and these two words have the same meaning. It is guaranteed that no word occurs in both languages, and each word occurs in its language exactly once.

The next line contains n space-separated strings c_1, c_2, ..., c_{n} — the text of the lecture. It is guaranteed that each of the strings c_{i} belongs to the set of strings {a_1, a_2, ... a_{m}}.

All the strings in the input are non-empty, each consisting of no more than 10 lowercase English letters.


-----Output-----

Output exactly n words: how you will record the lecture in your notebook. Output the words of the lecture in the same order as in the input.


-----Examples-----
Input
4 3
codeforces codesecrof
contest round
letter message
codeforces contest letter contest

Output
codeforces round letter round

Input
5 3
joll wuqrd
euzf un
hbnyiyc rsoqqveh
hbnyiyc joll joll euzf joll

Output
hbnyiyc joll joll un joll
user: One very well-known internet resource site (let's call it X) has come up with a New Year adventure. Specifically, they decided to give ratings to all visitors.

There are n users on the site, for each user we know the rating value he wants to get as a New Year Present. We know that user i wants to get at least a_{i} rating units as a present.

The X site is administered by very creative and thrifty people. On the one hand, they want to give distinct ratings and on the other hand, the total sum of the ratings in the present must be as small as possible.

Help site X cope with the challenging task of rating distribution. Find the optimal distribution.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 3·10^5) — the number of users on the site. The next line contains integer sequence a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9).


-----Output-----

Print a sequence of integers b_1, b_2, ..., b_{n}. Number b_{i} means that user i gets b_{i} of rating as a present. The printed sequence must meet the problem conditions. 

If there are multiple optimal solutions, print any of them.


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

Output
5 1 2

Input
1
1000000000

Output
1000000000
user: Permutation p is an ordered set of integers p_1,  p_2,  ...,  p_{n}, consisting of n distinct positive integers, each of them doesn't exceed n. We'll denote the i-th element of permutation p as p_{i}. We'll call number n the size or the length of permutation p_1,  p_2,  ...,  p_{n}.

You have a sequence of integers a_1, a_2, ..., a_{n}. In one move, you are allowed to decrease or increase any number by one. Count the minimum number of moves, needed to build a permutation from this sequence.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 3·10^5) — the size of the sought permutation. The second line contains n integers a_1, a_2, ..., a_{n} ( - 10^9 ≤ a_{i} ≤ 10^9).


-----Output-----

Print a single number — the minimum number of moves.

Please, do not use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specifier.


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

Output
2

Input
3
-1 -1 2

Output
6



-----Note-----

In the first sample you should decrease the first number by one and then increase the second number by one. The resulting permutation is (2, 1).

In the second sample you need 6 moves to build permutation (1, 3, 2).
user: There is a system of n vessels arranged one above the other as shown in the figure below. Assume that the vessels are numbered from 1 to n, in the order from the highest to the lowest, the volume of the i-th vessel is a_{i} liters. [Image] 

Initially, all the vessels are empty. In some vessels water is poured. All the water that overflows from the i-th vessel goes to the (i + 1)-th one. The liquid that overflows from the n-th vessel spills on the floor.

Your task is to simulate pouring water into the vessels. To do this, you will need to handle two types of queries:  Add x_{i} liters of water to the p_{i}-th vessel;  Print the number of liters of water in the k_{i}-th vessel. 

When you reply to the second request you can assume that all the water poured up to this point, has already overflown between the vessels.


-----Input-----

The first line contains integer n — the number of vessels (1 ≤ n ≤ 2·10^5). The second line contains n integers a_1, a_2, ..., a_{n} — the vessels' capacities (1 ≤ a_{i} ≤ 10^9). The vessels' capacities do not necessarily increase from the top vessels to the bottom ones (see the second sample). The third line contains integer m — the number of queries (1 ≤ m ≤ 2·10^5). Each of the next m lines contains the description of one query. The query of the first type is represented as "1 p_{i} x_{i}", the query of the second type is represented as "2 k_{i}" (1 ≤ p_{i} ≤ n, 1 ≤ x_{i} ≤ 10^9, 1 ≤ k_{i} ≤ n).


-----Output-----

For each query, print on a single line the number of liters of water in the corresponding vessel.


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

Output
4
5
8

Input
3
5 10 8
6
1 1 12
2 2
1 1 6
1 3 2
2 2
2 3

Output
7
10
5
user: You are given a sequence of $n$ pairs of integers: $(a_1, b_1), (a_2, b_2), \dots , (a_n, b_n)$. This sequence is called bad if it is sorted in non-descending order by first elements or if it is sorted in non-descending order by second elements. Otherwise the sequence is good. There are examples of good and bad sequences:  $s = [(1, 2), (3, 2), (3, 1)]$ is bad because the sequence of first elements is sorted: $[1, 3, 3]$;  $s = [(1, 2), (3, 2), (1, 2)]$ is bad because the sequence of second elements is sorted: $[2, 2, 2]$;  $s = [(1, 1), (2, 2), (3, 3)]$ is bad because both sequences (the sequence of first elements and the sequence of second elements) are sorted;  $s = [(1, 3), (3, 3), (2, 2)]$ is good because neither the sequence of first elements $([1, 3, 2])$ nor the sequence of second elements $([3, 3, 2])$ is sorted. 

Calculate the number of permutations of size $n$ such that after applying this permutation to the sequence $s$ it turns into a good sequence. 

A permutation $p$ of size $n$ is a sequence $p_1, p_2, \dots , p_n$ consisting of $n$ distinct integers from $1$ to $n$ ($1 \le p_i \le n$). If you apply permutation $p_1, p_2, \dots , p_n$ to the sequence $s_1, s_2, \dots , s_n$ you get the sequence $s_{p_1}, s_{p_2}, \dots , s_{p_n}$. For example, if $s = [(1, 2), (1, 3), (2, 3)]$ and $p = [2, 3, 1]$ then $s$ turns into $[(1, 3), (2, 3), (1, 2)]$.


-----Input-----

The first line contains one integer $n$ ($1 \le n \le 3 \cdot 10^5$).

The next $n$ lines contains description of sequence $s$. The $i$-th line contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le n$) — the first and second elements of $i$-th pair in the sequence.

The sequence $s$ may contain equal elements.


-----Output-----

Print the number of permutations of size $n$ such that after applying this permutation to the sequence $s$ it turns into a good sequence. Print the answer modulo $998244353$ (a prime number).


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

Output
3

Input
4
2 3
2 2
2 1
2 4

Output
0

Input
3
1 1
1 1
2 3

Output
4



-----Note-----

In first test case there are six permutations of size $3$:   if $p = [1, 2, 3]$, then $s = [(1, 1), (2, 2), (3, 1)]$ — bad sequence (sorted by first elements);  if $p = [1, 3, 2]$, then $s = [(1, 1), (3, 1), (2, 2)]$ — bad sequence (sorted by second elements);  if $p = [2, 1, 3]$, then $s = [(2, 2), (1, 1), (3, 1)]$ — good sequence;  if $p = [2, 3, 1]$, then $s = [(2, 2), (3, 1), (1, 1)]$ — good sequence;  if $p = [3, 1, 2]$, then $s = [(3, 1), (1, 1), (2, 2)]$ — bad sequence (sorted by second elements);  if $p = [3, 2, 1]$, then $s = [(3, 1), (2, 2), (1, 1)]$ — good sequence.
user: You are given two integers $A$ and $B$, calculate the number of pairs $(a, b)$ such that $1 \le a \le A$, $1 \le b \le B$, and the equation $a \cdot b + a + b = conc(a, b)$ is true; $conc(a, b)$ is the concatenation of $a$ and $b$ (for example, $conc(12, 23) = 1223$, $conc(100, 11) = 10011$). $a$ and $b$ should not contain leading zeroes.


-----Input-----

The first line contains $t$ ($1 \le t \le 100$) — the number of test cases.

Each test case contains two integers $A$ and $B$ $(1 \le A, B \le 10^9)$.


-----Output-----

Print one integer — the number of pairs $(a, b)$ such that $1 \le a \le A$, $1 \le b \le B$, and the equation $a \cdot b + a + b = conc(a, b)$ is true.


-----Example-----
Input
3
1 11
4 2
191 31415926

Output
1
0
1337



-----Note-----

There is only one suitable pair in the first test case: $a = 1$, $b = 9$ ($1 + 9 + 1 \cdot 9 = 19$).
user: Vasya has got $n$ books, numbered from $1$ to $n$, arranged in a stack. The topmost book has number $a_1$, the next one — $a_2$, and so on. The book at the bottom of the stack has number $a_n$. All numbers are distinct.

Vasya wants to move all the books to his backpack in $n$ steps. During $i$-th step he wants to move the book number $b_i$ into his backpack. If the book with number $b_i$ is in the stack, he takes this book and all the books above the book $b_i$, and puts them into the backpack; otherwise he does nothing and begins the next step. For example, if books are arranged in the order $[1, 2, 3]$ (book $1$ is the topmost), and Vasya moves the books in the order $[2, 1, 3]$, then during the first step he will move two books ($1$ and $2$), during the second step he will do nothing (since book $1$ is already in the backpack), and during the third step — one book (the book number $3$). Note that $b_1, b_2, \dots, b_n$ are distinct.

Help Vasya! Tell him the number of books he will put into his backpack during each step.


-----Input-----

The first line contains one integer $n~(1 \le n \le 2 \cdot 10^5)$ — the number of books in the stack.

The second line contains $n$ integers $a_1, a_2, \dots, a_n~(1 \le a_i \le n)$ denoting the stack of books.

The third line contains $n$ integers $b_1, b_2, \dots, b_n~(1 \le b_i \le n)$ denoting the steps Vasya is going to perform.

All numbers $a_1 \dots a_n$ are distinct, the same goes for $b_1 \dots b_n$.


-----Output-----

Print $n$ integers. The $i$-th of them should be equal to the number of books Vasya moves to his backpack during the $i$-th step.


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

Output
2 0 1 

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

Output
3 2 0 0 0 

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

Output
1 1 2 0 1 1 



-----Note-----

The first example is described in the statement.

In the second example, during the first step Vasya will move the books $[3, 1, 4]$. After that only books $2$ and $5$ remain in the stack ($2$ is above $5$). During the second step Vasya will take the books $2$ and $5$. After that the stack becomes empty, so during next steps Vasya won't move any books.
user: Little girl Susie accidentally found her elder brother's notebook. She has many things to do, more important than solving problems, but she found this problem too interesting, so she wanted to know its solution and decided to ask you about it. So, the problem statement is as follows.

Let's assume that we are given a connected weighted undirected graph G = (V, E) (here V is the set of vertices, E is the set of edges). The shortest-path tree from vertex u is such graph G_1 = (V, E_1) that is a tree with the set of edges E_1 that is the subset of the set of edges of the initial graph E, and the lengths of the shortest paths from u to any vertex to G and to G_1 are the same. 

You are given a connected weighted undirected graph G and vertex u. Your task is to find the shortest-path tree of the given graph from vertex u, the total weight of whose edges is minimum possible.


-----Input-----

The first line contains two numbers, n and m (1 ≤ n ≤ 3·10^5, 0 ≤ m ≤ 3·10^5) — the number of vertices and edges of the graph, respectively.

Next m lines contain three integers each, representing an edge — u_{i}, v_{i}, w_{i} — the numbers of vertices connected by an edge and the weight of the edge (u_{i} ≠ v_{i}, 1 ≤ w_{i} ≤ 10^9). It is guaranteed that graph is connected and that there is no more than one edge between any pair of vertices.

The last line of the input contains integer u (1 ≤ u ≤ n) — the number of the start vertex.


-----Output-----

In the first line print the minimum total weight of the edges of the tree.

In the next line print the indices of the edges that are included in the tree, separated by spaces. The edges are numbered starting from 1 in the order they follow in the input. You may print the numbers of the edges in any order.

If there are multiple answers, print any of them.


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

Output
2
1 2 

Input
4 4
1 2 1
2 3 1
3 4 1
4 1 2
4

Output
4
2 3 4 



-----Note-----

In the first sample there are two possible shortest path trees:

  with edges 1 – 3 and 2 – 3 (the total weight is 3);  with edges 1 – 2 and 2 – 3 (the total weight is 2); 

And, for example, a tree with edges 1 – 2 and 1 – 3 won't be a shortest path tree for vertex 3, because the distance from vertex 3 to vertex 2 in this tree equals 3, and in the original graph it is 1.
user: Iahub likes chess very much. He even invented a new chess piece named Coder. A Coder can move (and attack) one square horizontally or vertically. More precisely, if the Coder is located at position (x, y), he can move to (or attack) positions (x + 1, y), (x–1, y), (x, y + 1) and (x, y–1).

Iahub wants to know how many Coders can be placed on an n × n chessboard, so that no Coder attacks any other Coder.


-----Input-----

The first line contains an integer n (1 ≤ n ≤ 1000).


-----Output-----

On the first line print an integer, the maximum number of Coders that can be placed on the chessboard.

On each of the next n lines print n characters, describing the configuration of the Coders. For an empty cell print an '.', and for a Coder print a 'C'.

If there are multiple correct answers, you can print any.


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

Output
2
C.
.C
user: Valera takes part in the Berland Marathon. The marathon race starts at the stadium that can be represented on the plane as a square whose lower left corner is located at point with coordinates (0, 0) and the length of the side equals a meters. The sides of the square are parallel to coordinate axes.

As the length of the marathon race is very long, Valera needs to have extra drink during the race. The coach gives Valera a bottle of drink each d meters of the path. We know that Valera starts at the point with coordinates (0, 0) and runs counter-clockwise. That is, when Valera covers a meters, he reaches the point with coordinates (a, 0). We also know that the length of the marathon race equals nd + 0.5 meters. 

Help Valera's coach determine where he should be located to help Valera. Specifically, determine the coordinates of Valera's positions when he covers d, 2·d, ..., n·d meters.


-----Input-----

The first line contains two space-separated real numbers a and d (1 ≤ a, d ≤ 10^5), given with precision till 4 decimal digits after the decimal point. Number a denotes the length of the square's side that describes the stadium. Number d shows that after each d meters Valera gets an extra drink.

The second line contains integer n (1 ≤ n ≤ 10^5) showing that Valera needs an extra drink n times.


-----Output-----

Print n lines, each line should contain two real numbers x_{i} and y_{i}, separated by a space. Numbers x_{i} and y_{i} in the i-th line mean that Valera is at point with coordinates (x_{i}, y_{i}) after he covers i·d meters. Your solution will be considered correct if the absolute or relative error doesn't exceed 10^{ - 4}.

Note, that this problem have huge amount of output data. Please, do not use cout stream for output in this problem.


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

Output
1.0000000000 2.0000000000
2.0000000000 0.0000000000

Input
4.147 2.8819
6

Output
2.8819000000 0.0000000000
4.1470000000 1.6168000000
3.7953000000 4.1470000000
0.9134000000 4.1470000000
0.0000000000 2.1785000000
0.7034000000 0.0000000000
user: Bob is a competitive programmer. He wants to become red, and for that he needs a strict training regime. He went to the annual meeting of grandmasters and asked $n$ of them how much effort they needed to reach red.

"Oh, I just spent $x_i$ hours solving problems", said the $i$-th of them. 

Bob wants to train his math skills, so for each answer he wrote down the number of minutes ($60 \cdot x_i$), thanked the grandmasters and went home. Bob could write numbers with leading zeroes — for example, if some grandmaster answered that he had spent $2$ hours, Bob could write $000120$ instead of $120$.

Alice wanted to tease Bob and so she took the numbers Bob wrote down, and for each of them she did one of the following independently:   rearranged its digits, or  wrote a random number. 

This way, Alice generated $n$ numbers, denoted $y_1$, ..., $y_n$.

For each of the numbers, help Bob determine whether $y_i$ can be a permutation of a number divisible by $60$ (possibly with leading zeroes).


-----Input-----

The first line contains a single integer $n$ ($1 \leq n \leq 418$) — the number of grandmasters Bob asked.

Then $n$ lines follow, the $i$-th of which contains a single integer $y_i$ — the number that Alice wrote down.

Each of these numbers has between $2$ and $100$ digits '0' through '9'. They can contain leading zeroes.


-----Output-----

Output $n$ lines.

For each $i$, output the following. If it is possible to rearrange the digits of $y_i$ such that the resulting number is divisible by $60$, output "red" (quotes for clarity). Otherwise, output "cyan".


-----Example-----
Input
6
603
006
205
228
1053
0000000000000000000000000000000000000000000000

Output
red
red
cyan
cyan
cyan
red



-----Note-----

In the first example, there is one rearrangement that yields a number divisible by $60$, and that is $360$.

In the second example, there are two solutions. One is $060$ and the second is $600$.

In the third example, there are $6$ possible rearrangments: $025$, $052$, $205$, $250$, $502$, $520$. None of these numbers is divisible by $60$.

In the fourth example, there are $3$ rearrangements: $228$, $282$, $822$.

In the fifth example, none of the $24$ rearrangements result in a number divisible by $60$.

In the sixth example, note that $000\dots0$ is a valid solution.
user: Три брата договорились о встрече. Пронумеруем братьев следующим образом: пусть старший брат имеет номер 1, средний брат имеет номер 2, а младший брат — номер 3. 

Когда пришло время встречи, один из братьев опоздал. По заданным номерам двух братьев, которые пришли вовремя, вам предстоит определить номер опоздавшего брата.


-----Входные данные-----

В первой строке входных данных следуют два различных целых числа a и b (1 ≤ a, b ≤ 3, a ≠ b) — номера братьев, которые пришли на встречу вовремя. Номера даны в произвольном порядке.


-----Выходные данные-----

Выведите единственное целое число — номер брата, который опоздал на встречу.


-----Пример-----
Входные данные
3 1

Выходные данные
2
user: You are given a boolean function of three variables which is defined by its truth table. You need to find an expression of minimum length that equals to this function. The expression may consist of:   Operation AND ('&', ASCII code 38)  Operation OR ('|', ASCII code 124)  Operation NOT ('!', ASCII code 33)  Variables x, y and z (ASCII codes 120-122)  Parentheses ('(', ASCII code 40, and ')', ASCII code 41) 

If more than one expression of minimum length exists, you should find the lexicographically smallest one.

Operations have standard priority. NOT has the highest priority, then AND goes, and OR has the lowest priority. The expression should satisfy the following grammar:

E ::= E '|' T | T

T ::= T '&' F | F

F ::= '!' F | '(' E ')' | 'x' | 'y' | 'z'


-----Input-----

The first line contains one integer n — the number of functions in the input (1 ≤ n ≤ 10 000).

The following n lines contain descriptions of functions, the i-th of them contains a string of length 8 that consists of digits 0 and 1 — the truth table of the i-th function. The digit on position j (0 ≤ j < 8) equals to the value of the function in case of $x = \lfloor \frac{j}{4} \rfloor$, $y = \lfloor \frac{j}{2} \rfloor \operatorname{mod} 2$ and $z = j \operatorname{mod} 2$.


-----Output-----

You should output n lines, the i-th line should contain the expression of minimum length which equals to the i-th function. If there is more than one such expression, output the lexicographically smallest of them. Expressions should satisfy the given grammar and shouldn't contain white spaces.


-----Example-----
Input
4
00110011
00000111
11110000
00011111

Output
y
(y|z)&x
!x
x|y&z



-----Note-----

The truth table for the second function:

[Image]