meetforever/GRPO_CL huggingface dataset:
user: Little Petya likes permutations a lot. Recently his mom has presented him permutation q_1, q_2, ..., q_{n} of length n.

A permutation a of length n is a sequence of integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ n), all integers there are distinct. 

There is only one thing Petya likes more than permutations: playing with little Masha. As it turns out, Masha also has a permutation of length n. Petya decided to get the same permutation, whatever the cost may be. For that, he devised a game with the following rules:  Before the beginning of the game Petya writes permutation 1, 2, ..., n on the blackboard. After that Petya makes exactly k moves, which are described below.  During a move Petya tosses a coin. If the coin shows heads, he performs point 1, if the coin shows tails, he performs point 2.  Let's assume that the board contains permutation p_1, p_2, ..., p_{n} at the given moment. Then Petya removes the written permutation p from the board and writes another one instead: p_{q}_1, p_{q}_2, ..., p_{q}_{n}. In other words, Petya applies permutation q (which he has got from his mother) to permutation p.  All actions are similar to point 1, except that Petya writes permutation t on the board, such that: t_{q}_{i} = p_{i} for all i from 1 to n. In other words, Petya applies a permutation that is inverse to q to permutation p. 

We know that after the k-th move the board contained Masha's permutation s_1, s_2, ..., s_{n}. Besides, we know that throughout the game process Masha's permutation never occurred on the board before the k-th move. Note that the game has exactly k moves, that is, throughout the game the coin was tossed exactly k times.

Your task is to determine whether the described situation is possible or else state that Petya was mistaken somewhere. See samples and notes to them for a better understanding.


-----Input-----

The first line contains two integers n and k (1 ≤ n, k ≤ 100). The second line contains n space-separated integers q_1, q_2, ..., q_{n} (1 ≤ q_{i} ≤ n) — the permutation that Petya's got as a present. The third line contains Masha's permutation s, in the similar format.

It is guaranteed that the given sequences q and s are correct permutations.


-----Output-----

If the situation that is described in the statement is possible, print "YES" (without the quotes), otherwise print "NO" (without the quotes).


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

Output
NO

Input
4 1
4 3 1 2
3 4 2 1

Output
YES

Input
4 3
4 3 1 2
3 4 2 1

Output
YES

Input
4 2
4 3 1 2
2 1 4 3

Output
YES

Input
4 1
4 3 1 2
2 1 4 3

Output
NO



-----Note-----

In the first sample Masha's permutation coincides with the permutation that was written on the board before the beginning of the game. Consequently, that violates the condition that Masha's permutation never occurred on the board before k moves were performed.

In the second sample the described situation is possible, in case if after we toss a coin, we get tails.

In the third sample the possible coin tossing sequence is: heads-tails-tails.

In the fourth sample the possible coin tossing sequence is: heads-heads.
user: Ivan places knights on infinite chessboard. Initially there are $n$ knights. If there is free cell which is under attack of at least $4$ knights then he places new knight in this cell. Ivan repeats this until there are no such free cells. One can prove that this process is finite. One can also prove that position in the end does not depend on the order in which new knights are placed.

Ivan asked you to find initial placement of exactly $n$ knights such that in the end there will be at least $\lfloor \frac{n^{2}}{10} \rfloor$ knights.


-----Input-----

The only line of input contains one integer $n$ ($1 \le n \le 10^{3}$) — number of knights in the initial placement.


-----Output-----

Print $n$ lines. Each line should contain $2$ numbers $x_{i}$ and $y_{i}$ ($-10^{9} \le x_{i}, \,\, y_{i} \le 10^{9}$) — coordinates of $i$-th knight. For all $i \ne j$, $(x_{i}, \,\, y_{i}) \ne (x_{j}, \,\, y_{j})$ should hold. In other words, all knights should be in different cells.

It is guaranteed that the solution exists.


-----Examples-----
Input
4

Output
1 1
3 1
1 5
4 4

Input
7

Output
2 1
1 2
4 1
5 2
2 6
5 7
6 6



-----Note-----

Let's look at second example:

$\left. \begin{array}{|l|l|l|l|l|l|l|l|l|} \hline 7 & {} & {} & {} & {} & {0} & {} & {} \\ \hline 6 & {} & {0} & {} & {} & {} & {0} & {} \\ \hline 5 & {} & {} & {} & {2} & {} & {} & {} \\ \hline 4 & {} & {} & {} & {} & {} & {} & {} \\ \hline 3 & {} & {} & {1} & {} & {} & {} & {} \\ \hline 2 & {0} & {} & {} & {} & {0} & {} & {} \\ \hline 1 & {} & {0} & {} & {0} & {} & {} & {} \\ \hline & {1} & {2} & {3} & {4} & {5} & {6} & {7} \\ \hline \end{array} \right.$

Green zeroes are initial knights. Cell $(3, \,\, 3)$ is under attack of $4$ knights in cells $(1, \,\, 2)$, $(2, \,\, 1)$, $(4, \,\, 1)$ and $(5, \,\, 2)$, therefore Ivan will place a knight in this cell. Cell $(4, \,\, 5)$ is initially attacked by only $3$ knights in cells $(2, \,\, 6)$, $(5, \,\, 7)$ and $(6, \,\, 6)$. But new knight in cell $(3, \,\, 3)$ also attacks cell $(4, \,\, 5)$, now it is attacked by $4$ knights and Ivan will place another knight in this cell. There are no more free cells which are attacked by $4$ or more knights, so the process stops. There are $9$ knights in the end, which is not less than $\lfloor \frac{7^{2}}{10} \rfloor = 4$.
user: 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-----

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-----

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.


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

Output
-1

Input
3
1 2 3

Output
3



-----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.
user: In order to put away old things and welcome a fresh new year, a thorough cleaning of the house is a must.

Little Tommy finds an old polynomial and cleaned it up by taking it modulo another. But now he regrets doing this...

Given two integers p and k, find a polynomial f(x) with non-negative integer coefficients strictly less than k, whose remainder is p when divided by (x + k). That is, f(x) = q(x)·(x + k) + p, where q(x) is a polynomial (not necessarily with integer coefficients).


-----Input-----

The only line of input contains two space-separated integers p and k (1 ≤ p ≤ 10^18, 2 ≤ k ≤ 2 000).


-----Output-----

If the polynomial does not exist, print a single integer -1, or output two lines otherwise.

In the first line print a non-negative integer d — the number of coefficients in the polynomial.

In the second line print d space-separated integers a_0, a_1, ..., a_{d} - 1, describing a polynomial $f(x) = \sum_{i = 0}^{d - 1} a_{i} \cdot x^{i}$ fulfilling the given requirements. Your output should satisfy 0 ≤ a_{i} < k for all 0 ≤ i ≤ d - 1, and a_{d} - 1 ≠ 0.

If there are many possible solutions, print any of them.


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

Output
7
0 1 0 0 1 1 1

Input
2018 214

Output
3
92 205 1



-----Note-----

In the first example, f(x) = x^6 + x^5 + x^4 + x = (x^5 - x^4 + 3x^3 - 6x^2 + 12x - 23)·(x + 2) + 46.

In the second example, f(x) = x^2 + 205x + 92 = (x - 9)·(x + 214) + 2018.
user: Mikhail the Freelancer dreams of two things: to become a cool programmer and to buy a flat in Moscow. To become a cool programmer, he needs at least p experience points, and a desired flat in Moscow costs q dollars. Mikhail is determined to follow his dreams and registered at a freelance site.

He has suggestions to work on n distinct projects. Mikhail has already evaluated that the participation in the i-th project will increase his experience by a_{i} per day and bring b_{i} dollars per day. As freelance work implies flexible working hours, Mikhail is free to stop working on one project at any time and start working on another project. Doing so, he receives the respective share of experience and money. Mikhail is only trying to become a cool programmer, so he is able to work only on one project at any moment of time.

Find the real value, equal to the minimum number of days Mikhail needs to make his dream come true.

For example, suppose Mikhail is suggested to work on three projects and a_1 = 6, b_1 = 2, a_2 = 1, b_2 = 3, a_3 = 2, b_3 = 6. Also, p = 20 and q = 20. In order to achieve his aims Mikhail has to work for 2.5 days on both first and third projects. Indeed, a_1·2.5 + a_2·0 + a_3·2.5 = 6·2.5 + 1·0 + 2·2.5 = 20 and b_1·2.5 + b_2·0 + b_3·2.5 = 2·2.5 + 3·0 + 6·2.5 = 20.


-----Input-----

The first line of the input contains three integers n, p and q (1 ≤ n ≤ 100 000, 1 ≤ p, q ≤ 1 000 000) — the number of projects and the required number of experience and money.

Each of the next n lines contains two integers a_{i} and b_{i} (1 ≤ a_{i}, b_{i} ≤ 1 000 000) — the daily increase in experience and daily income for working on the i-th project.


-----Output-----

Print a real value — the minimum number of days Mikhail needs to get the required amount of experience and money. Your answer will be considered correct if its absolute or relative error does not exceed 10^{ - 6}. 

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if $\frac{|a - b|}{\operatorname{max}(1, b)} \leq 10^{-6}$.


-----Examples-----
Input
3 20 20
6 2
1 3
2 6

Output
5.000000000000000

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

Output
0.400000000000000



-----Note-----

First sample corresponds to the example in the problem statement.
user: Robbers, who attacked the Gerda's cab, are very successful in covering from the kingdom police. To make the goal of catching them even harder, they use their own watches.

First, as they know that kingdom police is bad at math, robbers use the positional numeral system with base 7. Second, they divide one day in n hours, and each hour in m minutes. Personal watches of each robber are divided in two parts: first of them has the smallest possible number of places that is necessary to display any integer from 0 to n - 1, while the second has the smallest possible number of places that is necessary to display any integer from 0 to m - 1. Finally, if some value of hours or minutes can be displayed using less number of places in base 7 than this watches have, the required number of zeroes is added at the beginning of notation.

Note that to display number 0 section of the watches is required to have at least one place.

Little robber wants to know the number of moments of time (particular values of hours and minutes), such that all digits displayed on the watches are distinct. Help her calculate this number.


-----Input-----

The first line of the input contains two integers, given in the decimal notation, n and m (1 ≤ n, m ≤ 10^9) — the number of hours in one day and the number of minutes in one hour, respectively.


-----Output-----

Print one integer in decimal notation — the number of different pairs of hour and minute, such that all digits displayed on the watches are distinct.


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

Output
4

Input
8 2

Output
5



-----Note-----

In the first sample, possible pairs are: (0: 1), (0: 2), (1: 0), (1: 2).

In the second sample, possible pairs are: (02: 1), (03: 1), (04: 1), (05: 1), (06: 1).
user: Edogawa Conan got tired of solving cases, and invited his friend, Professor Agasa, over. They decided to play a game of cards. Conan has n cards, and the i-th card has a number a_{i} written on it.

They take turns playing, starting with Conan. In each turn, the player chooses a card and removes it. Also, he removes all cards having a number strictly lesser than the number on the chosen card. Formally, if the player chooses the i-th card, he removes that card and removes the j-th card for all j such that a_{j} < a_{i}.

A player loses if he cannot make a move on his turn, that is, he loses if there are no cards left. Predict the outcome of the game, assuming both players play optimally.


-----Input-----

The first line contains an integer n (1 ≤ n ≤ 10^5) — the number of cards Conan has. 

The next line contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^5), where a_{i} is the number on the i-th card.


-----Output-----

If Conan wins, print "Conan" (without quotes), otherwise print "Agasa" (without quotes).


-----Examples-----
Input
3
4 5 7

Output
Conan

Input
2
1 1

Output
Agasa



-----Note-----

In the first example, Conan can just choose the card having number 7 on it and hence remove all the cards. After that, there are no cards left on Agasa's turn.

In the second example, no matter which card Conan chooses, there will be one one card left, which Agasa can choose. After that, there are no cards left when it becomes Conan's turn again.
user: You are given two integers A and B.
Print a grid where each square is painted white or black that satisfies the following conditions, in the format specified in Output section:
 - Let the size of the grid be h \times w (h vertical, w horizontal). Both h and w are at most 100.
 - The set of the squares painted white is divided into exactly A connected components.
 - The set of the squares painted black is divided into exactly B connected components.
It can be proved that there always exist one or more solutions under the conditions specified in Constraints section.
If there are multiple solutions, any of them may be printed.

-----Notes-----
Two squares painted white, c_1 and c_2, are called connected when the square c_2 can be reached from the square c_1 passing only white squares by repeatedly moving up, down, left or right to an adjacent square.
A set of squares painted white, S, forms a connected component when the following conditions are met:
 - Any two squares in S are connected.
 - No pair of a square painted white that is not included in S and a square included in S is connected.
A connected component of squares painted black is defined similarly.

-----Constraints-----
 - 1 \leq A \leq 500
 - 1 \leq B \leq 500

-----Input-----
Input is given from Standard Input in the following format:
A B

-----Output-----
Output should be in the following format:
 - In the first line, print integers h and w representing the size of the grid you constructed, with a space in between.
 - Then, print h more lines. The i-th (1 \leq i \leq h) of these lines should contain a string s_i as follows:
 - If the square at the i-th row and j-th column (1 \leq j \leq w) in the grid is painted white, the j-th character in s_i should be ..
 - If the square at the i-th row and j-th column (1 \leq j \leq w) in the grid is painted black, the j-th character in s_i should be #.

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

-----Sample Output-----
3 3
##.
..#
#.#

This output corresponds to the grid below:
user: Nearly each project of the F company has a whole team of developers working on it. They often are in different rooms of the office in different cities and even countries. To keep in touch and track the results of the project, the F company conducts shared online meetings in a Spyke chat.

One day the director of the F company got hold of the records of a part of an online meeting of one successful team. The director watched the record and wanted to talk to the team leader. But how can he tell who the leader is? The director logically supposed that the leader is the person who is present at any conversation during a chat meeting. In other words, if at some moment of time at least one person is present on the meeting, then the leader is present on the meeting.

You are the assistant director. Given the 'user logged on'/'user logged off' messages of the meeting in the chronological order, help the director determine who can be the leader. Note that the director has the record of only a continuous part of the meeting (probably, it's not the whole meeting).


-----Input-----

The first line contains integers n and m (1 ≤ n, m ≤ 10^5) — the number of team participants and the number of messages. Each of the next m lines contains a message in the format:  '+ id': the record means that the person with number id (1 ≤ id ≤ n) has logged on to the meeting.  '- id': the record means that the person with number id (1 ≤ id ≤ n) has logged off from the meeting. 

Assume that all the people of the team are numbered from 1 to n and the messages are given in the chronological order. It is guaranteed that the given sequence is the correct record of a continuous part of the meeting. It is guaranteed that no two log on/log off events occurred simultaneously.


-----Output-----

In the first line print integer k (0 ≤ k ≤ n) — how many people can be leaders. In the next line, print k integers in the increasing order — the numbers of the people who can be leaders.

If the data is such that no member of the team can be a leader, print a single number 0.


-----Examples-----
Input
5 4
+ 1
+ 2
- 2
- 1

Output
4
1 3 4 5 
Input
3 2
+ 1
- 2

Output
1
3 
Input
2 4
+ 1
- 1
+ 2
- 2

Output
0

Input
5 6
+ 1
- 1
- 3
+ 3
+ 4
- 4

Output
3
2 3 5 
Input
2 4
+ 1
- 2
+ 2
- 1

Output
0
user: You are given two arrays $a$ and $b$ of positive integers, with length $n$ and $m$ respectively. 

Let $c$ be an $n \times m$ matrix, where $c_{i,j} = a_i \cdot b_j$. 

You need to find a subrectangle of the matrix $c$ such that the sum of its elements is at most $x$, and its area (the total number of elements) is the largest possible.

Formally, you need to find the largest number $s$ such that it is possible to choose integers $x_1, x_2, y_1, y_2$ subject to $1 \leq x_1 \leq x_2 \leq n$, $1 \leq y_1 \leq y_2 \leq m$, $(x_2 - x_1 + 1) \times (y_2 - y_1 + 1) = s$, and $$\sum_{i=x_1}^{x_2}{\sum_{j=y_1}^{y_2}{c_{i,j}}} \leq x.$$


-----Input-----

The first line contains two integers $n$ and $m$ ($1 \leq n, m \leq 2000$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 2000$).

The third line contains $m$ integers $b_1, b_2, \ldots, b_m$ ($1 \leq b_i \leq 2000$).

The fourth line contains a single integer $x$ ($1 \leq x \leq 2 \cdot 10^{9}$).


-----Output-----

If it is possible to choose four integers $x_1, x_2, y_1, y_2$ such that $1 \leq x_1 \leq x_2 \leq n$, $1 \leq y_1 \leq y_2 \leq m$, and $\sum_{i=x_1}^{x_2}{\sum_{j=y_1}^{y_2}{c_{i,j}}} \leq x$, output the largest value of $(x_2 - x_1 + 1) \times (y_2 - y_1 + 1)$ among all such quadruplets, otherwise output $0$.


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

Output
4

Input
5 1
5 4 2 4 5
2
5

Output
1



-----Note-----

Matrix from the first sample and the chosen subrectangle (of blue color):

 [Image] 

Matrix from the second sample and the chosen subrectangle (of blue color):

 $\left. \begin{array}{l l l l l}{10} & {8} & {4} & {8} & {10} \end{array} \right.$
user: Paul hates palindromes. He assumes that string s is tolerable if each its character is one of the first p letters of the English alphabet and s doesn't contain any palindrome contiguous substring of length 2 or more.

Paul has found a tolerable string s of length n. Help him find the lexicographically next tolerable string of the same length or else state that such string does not exist.


-----Input-----

The first line contains two space-separated integers: n and p (1 ≤ n ≤ 1000; 1 ≤ p ≤ 26). The second line contains string s, consisting of n small English letters. It is guaranteed that the string is tolerable (according to the above definition).


-----Output-----

If the lexicographically next tolerable string of the same length exists, print it. Otherwise, print "NO" (without the quotes).


-----Examples-----
Input
3 3
cba

Output
NO

Input
3 4
cba

Output
cbd

Input
4 4
abcd

Output
abda



-----Note-----

String s is lexicographically larger (or simply larger) than string t with the same length, if there is number i, such that s_1 = t_1, ..., s_{i} = t_{i}, s_{i} + 1 > t_{i} + 1.

The lexicographically next tolerable string is the lexicographically minimum tolerable string which is larger than the given one.

A palindrome is a string that reads the same forward or reversed.
user: "Duel!"

Betting on the lovely princess Claris, the duel between Tokitsukaze and Quailty has started.

There are $n$ cards in a row. Each card has two sides, one of which has color. At first, some of these cards are with color sides facing up and others are with color sides facing down. Then they take turns flipping cards, in which Tokitsukaze moves first. In each move, one should choose exactly $k$ consecutive cards and flip them to the same side, which means to make their color sides all face up or all face down. If all the color sides of these $n$ cards face the same direction after one's move, the one who takes this move will win.

Princess Claris wants to know who will win the game if Tokitsukaze and Quailty are so clever that they won't make mistakes.


-----Input-----

The first line contains two integers $n$ and $k$ ($1 \le k \le n \le 10^5$).

The second line contains a single string of length $n$ that only consists of $0$ and $1$, representing the situation of these $n$ cards, where the color side of the $i$-th card faces up if the $i$-th character is $1$, or otherwise, it faces down and the $i$-th character is $0$.


-----Output-----

Print "once again" (without quotes) if the total number of their moves can exceed $10^9$, which is considered a draw.

In other cases, print "tokitsukaze" (without quotes) if Tokitsukaze will win, or "quailty" (without quotes) if Quailty will win.

Note that the output characters are case-sensitive, and any wrong spelling would be rejected.


-----Examples-----
Input
4 2
0101

Output
quailty

Input
6 1
010101

Output
once again

Input
6 5
010101

Output
tokitsukaze

Input
4 1
0011

Output
once again



-----Note-----

In the first example, no matter how Tokitsukaze moves, there would be three cards with color sides facing the same direction after her move, and Quailty can flip the last card to this direction and win.

In the second example, no matter how Tokitsukaze moves, Quailty can choose the same card and flip back to the initial situation, which can allow the game to end in a draw.

In the third example, Tokitsukaze can win by flipping the leftmost five cards up or flipping the rightmost five cards down.

The fourth example can be explained in the same way as the second example does.