meetforever/GRPO_CL huggingface dataset:
user: Salmon is playing a game!
He is given two integers $N$ and $K$. His goal is to output $K$ pairs $(x_i,y_i)$. He creates a function $f$ such that $f(x_i) = y_i$ and $f$ is undefined for all other values of $x$. His pairs must then meet the following conditions:
- All $x_i$ are distinct.
- All $y_i$ are distinct.
- All $x_i, y_i$ are in the range $[0,2^N - 1]$ and are integers.
- $f(f(x_i))$ is defined for all $i$.
- Let $H(x)$ be the number of set bits in the binary representation of $x$. Then, $H(x_i) \neq H(f(f(x_i)))$ for all $i$.
Unfortunately, Salmon is unable to solve this. Help Salmon win the game!

If there are multiple correct solutions, you may output any one of them. It can be proven that a solution exists for all $N$ and $K$ that meet constraints.

-----Input-----
- The first line input contains a single integer $T$ denoting the number of testcases
- Each of the next $T$ lines contains two space-separated integers $N$ and $K$ respectively.

-----Output-----
- Output $K$ lines for each testcase.
- The $i$-th line of a testcase should contain two space-separated integers: $x_i$ and $y_i$, following the given constraints.

-----Constraints-----
- $1 \leq T \leq 2^{15}$
- $3 \leq N \leq 18$ 
- $3 \leq K \leq 2^N$ 
- The sum of $2^N$ over all testcases doesn't exceed $2^{18}$

-----Subtasks-----
- Subtask 1 [20 points]: $K \leq 8$
- Subtask 2 [40 points]: $K = 2^N$
- Subtask 3 [40 points]: No additional constraints.

-----Sample Input-----
2
3 7
4 6

-----Sample Output-----
5 3
1 7
0 4
2 5
3 1
4 2 
7 0
1 10
10 14
15 1
14 13
5 15
13 5

-----Explanation-----
In the answer to the first testcase, there are 7 pairs. $x_i$ and $y_i$ are all in the range $[0,2^3 - 1]$, which is the range $[0,7]$. All values of $x_i$ are distinct, and all values of $y_i$ are distinct. However, note that some integers appear in both lists. For example, 5 appears both as $x_1$ and as $y_4$. This is allowed. For all $x_i$, $f(f(x_i))$ is defined and $H(f(f(x_i))) \neq H(x_i)$. For example, $f(f(7)) = 4$. $H(7) = 3$, but $H(4) = 1$. Therefore, $H(f(f(7))) \neq H(7)$, as desired.
user: Recently Chef learned about Longest Increasing Subsequence. To be precise, he means longest strictly increasing subsequence, when he talks of longest increasing subsequence.  To check his understanding, he took his favorite n-digit number and for each of its n digits, he computed the length of the longest increasing subsequence of digits ending with that digit. Then he stored these lengths in an array named LIS.
For example, let us say that Chef's favourite 4-digit number is 1531, then the LIS array would be [1, 2, 2, 1]. The length of longest increasing subsequence ending at first digit is 1 (the digit 1 itself) and at the second digit is 2 ([1, 5]), at third digit is also 2 ([1, 3]), and at the 4th digit is 1 (the digit 1 itself).
Now Chef wants to give you a challenge. He has a valid LIS array with him, and wants you to find any n-digit number having exactly the same LIS array? You are guaranteed that Chef's LIS array is valid, i.e. there exists at least one n-digit number corresponding to the given LIS array.

-----Input-----
The first line of the input contains an integer T denoting the number of test cases. 
For each test case, the first line contains an integer n denoting the number of digits in Chef's favourite number.
The second line will contain n space separated integers denoting LIS array, i.e. LIS1, LIS2, ..., LISn.

-----Output-----
For each test case, output a single n-digit number (without leading zeroes) having exactly the given LIS array. If there are multiple n-digit numbers satisfying this requirement, any of them will be accepted.

-----Constraints-----
- 1 ≤ T ≤ 30 000
- 1 ≤ n ≤ 9
- It is guaranteed that at least one n-digit number having the given LIS array exists

-----Example-----
Input:
5
1 
1
2 
1 2
2 
1 1
4
1 2 2 1
7 
1 2 2 1 3 2 4

Output:
7
36
54
1531
1730418

-----Explanation-----
Example case 1. All one-digit numbers have the same LIS array, so any answer from 0 to 9 will be accepted.
Example cases 2 & 3. For a two digit number we always have LIS1 = 1, but the value of LIS2 depends on whether the first digit is strictly less than the second one. If this is the case (like for number 36), LIS2 = 2, otherwise (like for numbers 54 or 77) the values of LIS2 is 1.
Example case 4. This has already been explained in the problem statement.
Example case 5. 7-digit number 1730418 has LIS array [1, 2, 2, 1, 3, 2, 4]:
indexLISlength117304181217304182317304182417304181517304183617304182717304184
user: Meanwhile, Candace and Stacy are busy planning to attend the concert of the famous Love Händel. Jeremy will also be attending the event. Therefore, Candace plans to offer the best possible gift to Jeremy.
Candace has $N$ strings, each of length $M$. Each character of each string can either be a lowercase English letter or the character '#'. She denotes the substring of $i$-$th$ string starting from the $l$-$th$ character and ending with the $r$-$th$ character as $S_{i}[l, r]$. She has to choose a list $a$ of $N - 1$ numbers such that  
- $1 \leq a_1 \leq a_2 \leq a_3 \leq ... \leq a_{N-1} \leq  M$.
- The final gift string is obtained by appending the substrings $S_{1}[1, a_{1}]$, $S_{2}[a_{1}, a_{2}]$, $S_{3}[a_{2}, a_{3}]$, .., $S_{N-1}[a_{N-2}, a_{N-1}]$, $S_{N}[a_{N-1}, M]$.
- Candace considers the gift to be the most beautiful one if the final gift string is the lexicographically smallest possible string and it doesn't contain the '#' character.
Let $P$ = $S_{1}[1, a_{1}]$ + $S_{2}[a_{1}, a_{2}]$ + $S_{3}[a_{2}, a_{3}]$ + .., + $S_{N-1}[a_{N-2}, a_{N-1}]$ + $S_{N}[a_{N-1}, M]$, then $P$ should be the lexicographically smallest string  possible and it should not contain '#' character, where '+' denotes concatenation of two substrings.
Help Candace find the best possible gift string quickly as she does not want Jeremy to wait for her. Also, it is guaranteed that at least one such valid string exists.

-----Input-----
- The first line contains a single integer $T$ denoting the number of testcases.
- The first line of each test case contains $2$ space separated integers denoting the values of $N$ and $M$ respectively.
- $N$ lines follow. Each line contains a string $S_i$ of length $M$ as described above.

-----Output-----
For every test case, print a line containing lexicographically lowest possible gift string.

-----Constraints-----
- $1 \leq T \leq 10^4$
- $1 \leq N, M \leq 10^6$
- $|S_i| = M$
- All $S_i$ will contain either a lower English letter ('a' to 'z' ) or the character '#' (ASCII $35$).
- Sum of $N * M$ over all test cases for a particular test file does not exceed $10^7$.
- It is guaranteed that a valid solution will always exist.

-----Sample Input-----
2
3 3
xab
a#z
caa
5 4
pyqs
vcot
qbiu
lihj
uvmz

-----Sample Output-----
xabza
pvcbihjz

-----Explanation-----
For test $1$:
The array $a$ chosen is: $[3, 3]$
The resulting string $P$ is formed by = $S_{1}[1, 3]$ + $S_{2}[3, 3]$ + $S_{3}[3, 3]$ = xabza
For test $2$:
The array $a$ chosen is: $[1, 2, 3, 4]$
The resulting string $P$ is formed by = $S_{1}[1, 1]$ + $S_{2}[1, 2]$ + $S_{3}[2, 3]$ + $S_{4}[3, 4]$ + $S_{5}[4, 4]$ = pvcbihjz
user: Indian National Olympiad in Informatics 2013
N people live in Sequence Land. Instead of a name, each person is identified by a sequence of integers, called his or her id. Each id is a sequence with no duplicate elements. Two people are said to be each other’s relatives if their ids have at least K elements in common. The extended family of a resident of Sequence Land includes herself or himself, all relatives, relatives of relatives, relatives of relatives of relatives, and so on without any limit.
Given the ids of all residents of Sequence Land, including its President, and the number K, find the number of people in the extended family of the President of Sequence Land.
For example, suppose N = 4 and K = 2. Suppose the President has id (4, 6, 7, 8) and the other three residents have ids (8, 3, 0, 4), (0, 10), and (1, 2, 3, 0, 5, 8). Here, the President is directly related to (8, 3, 0, 4), who in turn is directly related to (1, 2, 3, 0, 5, 8). Thus, the President’s extended family consists of everyone other than (0, 10) and so has size 3.

-----Input format-----
• Line 1: Two space-separated integers, N followed by K.
• Lines 2 to N + 1: Each line describes an id of one of the residents of Sequence Land, beginning with the President on line 2. Each line consists of an integer p, followed by p distinct integers, the id.

-----Output format-----
The output consists of a single integer, the number of people in the extended family of the President.

-----Test Data-----
The testdata is grouped into two subtasks. In both subtasks, 1 ≤ N ≤ 300 and 1 ≤ K ≤ 300. Each number in each id is between 0 and 109 inclusive.
• Subtask 1 [30 points]: The number of elements in each id is between 1 and 10 inclusive.
• Subtask 2 [70 points]: The number of elements in each id is between 1 and 300 inclusive.

-----Example-----
Here is the sample input and output corresponding to the example above.

-----Sample input -----
4 2
4 4 6 7 8
4 8 3 0 4
2 0 10
6 1 2 3 0 5 8

-----Sample output-----
3

Note: Your program should not print anything other than what is specified in the output format. Please remove all diagnostic print statements before making your final submission. A program with extraneous output will be treated as incorrect!
user: Codefortia is a small island country located somewhere in the West Pacific. It consists of $n$ settlements connected by $m$ bidirectional gravel roads. Curiously enough, the beliefs of the inhabitants require the time needed to pass each road to be equal either to $a$ or $b$ seconds. It's guaranteed that one can go between any pair of settlements by following a sequence of roads.

Codefortia was recently struck by the financial crisis. Therefore, the king decided to abandon some of the roads so that:

  it will be possible to travel between each pair of cities using the remaining roads only,  the sum of times required to pass each remaining road will be minimum possible (in other words, remaining roads must form minimum spanning tree, using the time to pass the road as its weight),  among all the plans minimizing the sum of times above, the time required to travel between the king's residence (in settlement $1$) and the parliament house (in settlement $p$) using the remaining roads only will be minimum possible. 

The king, however, forgot where the parliament house was. For each settlement $p = 1, 2, \dots, n$, can you tell what is the minimum time required to travel between the king's residence and the parliament house (located in settlement $p$) after some roads are abandoned?


-----Input-----

The first line of the input contains four integers $n$, $m$, $a$ and $b$ ($2 \leq n \leq 70$, $n - 1 \leq m \leq 200$, $1 \leq a < b \leq 10^7$) — the number of settlements and gravel roads in Codefortia, and two possible travel times. Each of the following lines contains three integers $u, v, c$ ($1 \leq u, v \leq n$, $u \neq v$, $c \in \{a, b\}$) denoting a single gravel road between the settlements $u$ and $v$, which requires $c$ minutes to travel.

You can assume that the road network is connected and has no loops or multiedges.


-----Output-----

Output a single line containing $n$ integers. The $p$-th of them should denote the minimum possible time required to travel from $1$ to $p$ after the selected roads are abandoned. Note that for each $p$ you can abandon a different set of roads.


-----Examples-----
Input
5 5 20 25
1 2 25
2 3 25
3 4 20
4 5 20
5 1 20

Output
0 25 60 40 20

Input
6 7 13 22
1 2 13
2 3 13
1 4 22
3 4 13
4 5 13
5 6 13
6 1 13

Output
0 13 26 39 26 13



-----Note-----

The minimum possible sum of times required to pass each road in the first example is $85$ — exactly one of the roads with passing time $25$ must be abandoned. Note that after one of these roads is abandoned, it's now impossible to travel between settlements $1$ and $3$ in time $50$.
user: Pikachu had an array with him. He wrote down all the non-empty subsequences of the array on paper. Note that an array of size n has 2^{n} - 1 non-empty subsequences in it. 

Pikachu being mischievous as he always is, removed all the subsequences in which Maximum_element_of_the_subsequence  -  Minimum_element_of_subsequence  ≥ d

Pikachu was finally left with X subsequences. 

However, he lost the initial array he had, and now is in serious trouble. He still remembers the numbers X and d. He now wants you to construct any such array which will satisfy the above conditions. All the numbers in the final array should be positive integers less than 10^18. 

Note the number of elements in the output array should not be more than 10^4. If no answer is possible, print  - 1.


-----Input-----

The only line of input consists of two space separated integers X and d (1 ≤ X, d ≤ 10^9).


-----Output-----

Output should consist of two lines.

First line should contain a single integer n (1 ≤ n ≤ 10 000)— the number of integers in the final array.

Second line should consist of n space separated integers — a_1, a_2, ... , a_{n} (1 ≤ a_{i} < 10^18).

If there is no answer, print a single integer -1. If there are multiple answers, print any of them.


-----Examples-----
Input
10 5

Output
6
5 50 7 15 6 100
Input
4 2

Output
4
10 100 1000 10000


-----Note-----

In the output of the first example case, the remaining subsequences after removing those with Maximum_element_of_the_subsequence  -  Minimum_element_of_subsequence  ≥ 5 are [5], [5, 7], [5, 6], [5, 7, 6], [50], [7], [7, 6], [15], [6], [100]. There are 10 of them. Hence, the array [5, 50, 7, 15, 6, 100] is valid.

Similarly, in the output of the second example case, the remaining sub-sequences after removing those with Maximum_element_of_the_subsequence  -  Minimum_element_of_subsequence  ≥ 2 are [10], [100], [1000], [10000]. There are 4 of them. Hence, the array [10, 100, 1000, 10000] is valid.
user: Vasya and Kolya play a game with a string, using the following rules. Initially, Kolya creates a string s, consisting of small English letters, and uniformly at random chooses an integer k from a segment [0, len(s) - 1]. He tells Vasya this string s, and then shifts it k letters to the left, i. e. creates a new string t = s_{k} + 1s_{k} + 2... s_{n}s_1s_2... s_{k}. Vasya does not know the integer k nor the string t, but he wants to guess the integer k. To do this, he asks Kolya to tell him the first letter of the new string, and then, after he sees it, open one more letter on some position, which Vasya can choose.

Vasya understands, that he can't guarantee that he will win, but he wants to know the probability of winning, if he plays optimally. He wants you to compute this probability. 

Note that Vasya wants to know the value of k uniquely, it means, that if there are at least two cyclic shifts of s that fit the information Vasya knowns, Vasya loses. Of course, at any moment of the game Vasya wants to maximize the probability of his win.


-----Input-----

The only string contains the string s of length l (3 ≤ l ≤ 5000), consisting of small English letters only.


-----Output-----

Print the only number — the answer for the problem. You answer is considered correct, if its absolute or relative error does not exceed 10^{ - 6}.

Formally, let your answer be a, and the jury's answer be b. Your answer is considered correct if $\frac{|a - b|}{\operatorname{max}(1,|b|)} \leq 10^{-6}$


-----Examples-----
Input
technocup

Output
1.000000000000000

Input
tictictactac

Output
0.333333333333333

Input
bbaabaabbb

Output
0.100000000000000



-----Note-----

In the first example Vasya can always open the second letter after opening the first letter, and the cyclic shift is always determined uniquely.

In the second example if the first opened letter of t is "t" or "c", then Vasya can't guess the shift by opening only one other letter. On the other hand, if the first letter is "i" or "a", then he can open the fourth letter and determine the shift uniquely.
user: In the evenings Donkey would join Shrek to look at the stars. They would sit on a log, sipping tea and they would watch the starry sky. The sky hung above the roof, right behind the chimney. Shrek's stars were to the right of the chimney and the Donkey's stars were to the left. Most days the Donkey would just count the stars, so he knew that they are exactly n. This time he wanted a challenge. He imagined a coordinate system: he put the origin of the coordinates at the intersection of the roof and the chimney, directed the OX axis to the left along the roof and the OY axis — up along the chimney (see figure). The Donkey imagined two rays emanating from he origin of axes at angles α_1 and α_2 to the OX axis.

 [Image] 

Now he chooses any star that lies strictly between these rays. After that he imagines more rays that emanate from this star at the same angles α_1 and α_2 to the OX axis and chooses another star that lies strictly between the new rays. He repeats the operation as long as there still are stars he can choose between the rays that emanate from a star. 

 [Image] 

As a result, the Donkey gets a chain of stars. He can consecutively get to each star if he acts by the given rules.

Your task is to find the maximum number of stars m that the Donkey's chain can contain.

Note that the chain must necessarily start in the point of the origin of the axes, that isn't taken into consideration while counting the number m of stars in the chain.


-----Input-----

The first line contains an integer n (1 ≤ n ≤ 10^5) — the number of stars. The second line contains simple fractions representing relationships "a/b c/d", such that $\frac{a}{b} = \frac{\operatorname{sin} \alpha_{1}}{\operatorname{cos} \alpha_{1}}$ and $\frac{c}{d} = \frac{\operatorname{sin} \alpha_{2}}{\operatorname{cos} \alpha}$ (0 ≤ a, b, c, d ≤ 10^5; $0^{\circ} \leq \alpha_{1} < \alpha_{2} \leq 90^{\circ}$; $\frac{a}{b} \neq \frac{0}{0}$; $\frac{c}{d} \neq \frac{0}{0}$). The given numbers a, b, c, d are integers.

Next n lines contain pairs of integers x_{i}, y_{i} (1 ≤ x_{i}, y_{i} ≤ 10^5)— the stars' coordinates.

It is guaranteed that all stars have distinct coordinates.


-----Output-----

In a single line print number m — the answer to the problem.


-----Examples-----
Input
15
1/3 2/1
3 1
6 2
4 2
2 5
4 5
6 6
3 4
1 6
2 1
7 4
9 3
5 3
1 3
15 5
12 4

Output
4



-----Note-----

In the sample the longest chain the Donkey can build consists of four stars. Note that the Donkey can't choose the stars that lie on the rays he imagines.

 [Image]
user: The Little Elephant has an integer a, written in the binary notation. He wants to write this number on a piece of paper.

To make sure that the number a fits on the piece of paper, the Little Elephant ought to delete exactly one any digit from number a in the binary record. At that a new number appears. It consists of the remaining binary digits, written in the corresponding order (possible, with leading zeroes).

The Little Elephant wants the number he is going to write on the paper to be as large as possible. Help him find the maximum number that he can obtain after deleting exactly one binary digit and print it in the binary notation.


-----Input-----

The single line contains integer a, written in the binary notation without leading zeroes. This number contains more than 1 and at most 10^5 digits.


-----Output-----

In the single line print the number that is written without leading zeroes in the binary notation — the answer to the problem.


-----Examples-----
Input
101

Output
11

Input
110010

Output
11010



-----Note-----

In the first sample the best strategy is to delete the second digit. That results in number 11_2 = 3_10.

In the second sample the best strategy is to delete the third or fourth digits — that results in number 11010_2 = 26_10.
user: Toad Rash has a binary string $s$. A binary string consists only of zeros and ones.

Let $n$ be the length of $s$.

Rash needs to find the number of such pairs of integers $l$, $r$ that $1 \leq l \leq r \leq n$ and there is at least one pair of integers $x$, $k$ such that $1 \leq x, k \leq n$, $l \leq x < x + 2k \leq r$, and $s_x = s_{x+k} = s_{x+2k}$.

Find this number of pairs for Rash.


-----Input-----

The first line contains the string $s$ ($1 \leq |s| \leq 300\,000$), consisting of zeros and ones.


-----Output-----

Output one integer: the number of such pairs of integers $l$, $r$ that $1 \leq l \leq r \leq n$ and there is at least one pair of integers $x$, $k$ such that $1 \leq x, k \leq n$, $l \leq x < x + 2k \leq r$, and $s_x = s_{x+k} = s_{x+2k}$.


-----Examples-----
Input
010101

Output
3

Input
11001100

Output
0



-----Note-----

In the first example, there are three $l$, $r$ pairs we need to count: $1$, $6$; $2$, $6$; and $1$, $5$.

In the second example, there are no values $x$, $k$ for the initial string, so the answer is $0$.
user: It is so boring in the summer holiday, isn't it? So Alice and Bob have invented a new game to play. The rules are as follows. First, they get a set of n distinct integers. And then they take turns to make the following moves. During each move, either Alice or Bob (the player whose turn is the current) can choose two distinct integers x and y from the set, such that the set doesn't contain their absolute difference |x - y|. Then this player adds integer |x - y| to the set (so, the size of the set increases by one).

If the current player has no valid move, he (or she) loses the game. The question is who will finally win the game if both players play optimally. Remember that Alice always moves first.


-----Input-----

The first line contains an integer n (2 ≤ n ≤ 100) — the initial number of elements in the set. The second line contains n distinct space-separated integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9) — the elements of the set.


-----Output-----

Print a single line with the winner's name. If Alice wins print "Alice", otherwise print "Bob" (without quotes).


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

Output
Alice

Input
2
5 3

Output
Alice

Input
3
5 6 7

Output
Bob



-----Note-----

Consider the first test sample. Alice moves first, and the only move she can do is to choose 2 and 3, then to add 1 to the set. Next Bob moves, there is no valid move anymore, so the winner is Alice.