meetforever/GRPO_CL huggingface dataset:
user: Having written another programming contest, three Rabbits decided to grab some lunch. The coach gave the team exactly k time units for the lunch break.

The Rabbits have a list of n restaurants to lunch in: the i-th restaurant is characterized by two integers f_{i} and t_{i}. Value t_{i} shows the time the Rabbits need to lunch in the i-th restaurant. If time t_{i} exceeds the time k that the coach has given for the lunch break, then the Rabbits' joy from lunching in this restaurant will equal f_{i} - (t_{i} - k). Otherwise, the Rabbits get exactly f_{i} units of joy.

Your task is to find the value of the maximum joy the Rabbits can get from the lunch, depending on the restaurant. The Rabbits must choose exactly one restaurant to lunch in. Note that the joy value isn't necessarily a positive value. 


-----Input-----

The first line contains two space-separated integers — n (1 ≤ n ≤ 10^4) and k (1 ≤ k ≤ 10^9) — the number of restaurants in the Rabbits' list and the time the coach has given them to lunch, correspondingly. Each of the next n lines contains two space-separated integers — f_{i} (1 ≤ f_{i} ≤ 10^9) and t_{i} (1 ≤ t_{i} ≤ 10^9) — the characteristics of the i-th restaurant.


-----Output-----

In a single line print a single integer — the maximum joy value that the Rabbits will get from the lunch. 


-----Examples-----
Input
2 5
3 3
4 5

Output
4

Input
4 6
5 8
3 6
2 3
2 2

Output
3

Input
1 5
1 7

Output
-1
user: Pupils decided to go to amusement park. Some of them were with parents. In total, n people came to the park and they all want to get to the most extreme attraction and roll on it exactly once.

Tickets for group of x people are sold on the attraction, there should be at least one adult in each group (it is possible that the group consists of one adult). The ticket price for such group is c_1 + c_2·(x - 1)^2 (in particular, if the group consists of one person, then the price is c_1). 

All pupils who came to the park and their parents decided to split into groups in such a way that each visitor join exactly one group, and the total price of visiting the most extreme attraction is as low as possible. You are to determine this minimum possible total price. There should be at least one adult in each group. 


-----Input-----

The first line contains three integers n, c_1 and c_2 (1 ≤ n ≤ 200 000, 1 ≤ c_1, c_2 ≤ 10^7) — the number of visitors and parameters for determining the ticket prices for a group.

The second line contains the string of length n, which consists of zeros and ones. If the i-th symbol of the string is zero, then the i-th visitor is a pupil, otherwise the i-th person is an adult. It is guaranteed that there is at least one adult. It is possible that there are no pupils.


-----Output-----

Print the minimum price of visiting the most extreme attraction for all pupils and their parents. Each of them should roll on the attraction exactly once.


-----Examples-----
Input
3 4 1
011

Output
8

Input
4 7 2
1101

Output
18



-----Note-----

In the first test one group of three people should go to the attraction. Then they have to pay 4 + 1 * (3 - 1)^2 = 8.

In the second test it is better to go to the attraction in two groups. The first group should consist of two adults (for example, the first and the second person), the second should consist of one pupil and one adult (the third and the fourth person). Then each group will have a size of two and for each the price of ticket is 7 + 2 * (2 - 1)^2 = 9. Thus, the total price for two groups is 18.
user: Vasya has a string $s$ of length $n$. He decides to make the following modification to the string:   Pick an integer $k$, ($1 \leq k \leq n$).  For $i$ from $1$ to $n-k+1$, reverse the substring $s[i:i+k-1]$ of $s$. For example, if string $s$ is qwer and $k = 2$, below is the series of transformations the string goes through:   qwer (original string)  wqer (after reversing the first substring of length $2$)  weqr (after reversing the second substring of length $2$)  werq (after reversing the last substring of length $2$)  Hence, the resulting string after modifying $s$ with $k = 2$ is werq. 

Vasya wants to choose a $k$ such that the string obtained after the above-mentioned modification is lexicographically smallest possible among all choices of $k$. Among all such $k$, he wants to choose the smallest one. Since he is busy attending Felicity 2020, he asks for your help.

A string $a$ is lexicographically smaller than a string $b$ if and only if one of the following holds:   $a$ is a prefix of $b$, but $a \ne b$;  in the first position where $a$ and $b$ differ, the string $a$ has a letter that appears earlier in the alphabet than the corresponding letter in $b$. 


-----Input-----

Each test contains multiple test cases. 

The first line contains the number of test cases $t$ ($1 \le t \le 5000$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 5000$) — the length of the string $s$.

The second line of each test case contains the string $s$ of $n$ lowercase latin letters.

It is guaranteed that the sum of $n$ over all test cases does not exceed $5000$.


-----Output-----

For each testcase output two lines:

In the first line output the lexicographically smallest string $s'$ achievable after the above-mentioned modification. 

In the second line output the appropriate value of $k$ ($1 \leq k \leq n$) that you chose for performing the modification. If there are multiple values of $k$ that give the lexicographically smallest string, output the smallest value of $k$ among them.


-----Example-----
Input
6
4
abab
6
qwerty
5
aaaaa
6
alaska
9
lfpbavjsm
1
p

Output
abab
1
ertyqw
3
aaaaa
1
aksala
6
avjsmbpfl
5
p
1



-----Note-----

In the first testcase of the first sample, the string modification results for the sample abab are as follows :   for $k = 1$ : abab  for $k = 2$ : baba  for $k = 3$ : abab  for $k = 4$ : baba

The lexicographically smallest string achievable through modification is abab for $k = 1$ and $3$. Smallest value of $k$ needed to achieve is hence $1$.
user: Parmida is a clever girl and she wants to participate in Olympiads this year. Of course she wants her partner to be clever too (although he's not)! Parmida has prepared the following test problem for Pashmak.

There is a sequence a that consists of n integers a_1, a_2, ..., a_{n}. Let's denote f(l, r, x) the number of indices k such that: l ≤ k ≤ r and a_{k} = x. His task is to calculate the number of pairs of indicies i, j (1 ≤ i < j ≤ n) such that f(1, i, a_{i}) > f(j, n, a_{j}).

Help Pashmak with the test.


-----Input-----

The first line of the input contains an integer n (1 ≤ n ≤ 10^6). The second line contains n space-separated integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9).


-----Output-----

Print a single integer — the answer to the problem.


-----Examples-----
Input
7
1 2 1 1 2 2 1

Output
8

Input
3
1 1 1

Output
1

Input
5
1 2 3 4 5

Output
0
user: Patrick likes to play baseball, but sometimes he will spend so many hours hitting home runs that his mind starts to get foggy! Patrick is sure that his scores across $n$ sessions follow the identity permutation (ie. in the first game he scores $1$ point, in the second game he scores $2$ points and so on). However, when he checks back to his record, he sees that all the numbers are mixed up! 

Define a special exchange as the following: choose any subarray of the scores and permute elements such that no element of subarray gets to the same position as it was before the exchange. For example, performing a special exchange on $[1,2,3]$ can yield $[3,1,2]$ but it cannot yield $[3,2,1]$ since the $2$ is in the same position. 

Given a permutation of $n$ integers, please help Patrick find the minimum number of special exchanges needed to make the permutation sorted! It can be proved that under given constraints this number doesn't exceed $10^{18}$.

An array $a$ is a subarray of an array $b$ if $a$ can be obtained from $b$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). Description of the test cases follows.

The first line of each test case contains integer $n$ ($1 \leq n \leq 2 \cdot 10^5$)  — the length of the given permutation.

The second line of each test case contains $n$ integers $a_{1},a_{2},...,a_{n}$ ($1 \leq a_{i} \leq n$)  — the initial permutation.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case, output one integer: the minimum number of special exchanges needed to sort the permutation.


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

Output
0
2



-----Note-----

In the first permutation, it is already sorted so no exchanges are needed.

It can be shown that you need at least $2$ exchanges to sort the second permutation.

$[3, 2, 4, 5, 1, 6, 7]$

Perform special exchange on range ($1, 5$)

$[4, 1, 2, 3, 5, 6, 7]$

Perform special exchange on range ($1, 4$)

$[1, 2, 3, 4, 5, 6, 7]$
user: You are given a rectangular field of n × m cells. Each cell is either empty or impassable (contains an obstacle). Empty cells are marked with '.', impassable cells are marked with '*'. Let's call two empty cells adjacent if they share a side.

Let's call a connected component any non-extendible set of cells such that any two of them are connected by the path of adjacent cells. It is a typical well-known definition of a connected component.

For each impassable cell (x, y) imagine that it is an empty cell (all other cells remain unchanged) and find the size (the number of cells) of the connected component which contains (x, y). You should do it for each impassable cell independently.

The answer should be printed as a matrix with n rows and m columns. The j-th symbol of the i-th row should be "." if the cell is empty at the start. Otherwise the j-th symbol of the i-th row should contain the only digit —- the answer modulo 10. The matrix should be printed without any spaces.

To make your output faster it is recommended to build the output as an array of n strings having length m and print it as a sequence of lines. It will be much faster than writing character-by-character.

As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.


-----Input-----

The first line contains two integers n, m (1 ≤ n, m ≤ 1000) — the number of rows and columns in the field.

Each of the next n lines contains m symbols: "." for empty cells, "*" for impassable cells.


-----Output-----

Print the answer as a matrix as described above. See the examples to precise the format of the output.


-----Examples-----
Input
3 3
*.*
.*.
*.*

Output
3.3
.5.
3.3

Input
4 5
**..*
..***
.*.*.
*.*.*

Output
46..3
..732
.6.4.
5.4.3



-----Note-----

In first example, if we imagine that the central cell is empty then it will be included to component of size 5 (cross). If any of the corner cell will be empty then it will be included to component of size 3 (corner).
user: You have a string s = s_1s_2...s_{|}s|, where |s| is the length of string s, and s_{i} its i-th character. 

Let's introduce several definitions:  A substring s[i..j] (1 ≤ i ≤ j ≤ |s|) of string s is string s_{i}s_{i} + 1...s_{j}.  The prefix of string s of length l (1 ≤ l ≤ |s|) is string s[1..l].  The suffix of string s of length l (1 ≤ l ≤ |s|) is string s[|s| - l + 1..|s|]. 

Your task is, for any prefix of string s which matches a suffix of string s, print the number of times it occurs in string s as a substring.


-----Input-----

The single line contains a sequence of characters s_1s_2...s_{|}s| (1 ≤ |s| ≤ 10^5) — string s. The string only consists of uppercase English letters.


-----Output-----

In the first line, print integer k (0 ≤ k ≤ |s|) — the number of prefixes that match a suffix of string s. Next print k lines, in each line print two integers l_{i} c_{i}. Numbers l_{i} c_{i} mean that the prefix of the length l_{i} matches the suffix of length l_{i} and occurs in string s as a substring c_{i} times. Print pairs l_{i} c_{i} in the order of increasing l_{i}.


-----Examples-----
Input
ABACABA

Output
3
1 4
3 2
7 1

Input
AAA

Output
3
1 3
2 2
3 1
user: You are given a string s and should process m queries. Each query is described by two 1-based indices l_{i}, r_{i} and integer k_{i}. It means that you should cyclically shift the substring s[l_{i}... r_{i}] k_{i} times. The queries should be processed one after another in the order they are given.

One operation of a cyclic shift (rotation) is equivalent to moving the last character to the position of the first character and shifting all other characters one position to the right.

For example, if the string s is abacaba and the query is l_1 = 3, r_1 = 6, k_1 = 1 then the answer is abbacaa. If after that we would process the query l_2 = 1, r_2 = 4, k_2 = 2 then we would get the string baabcaa.


-----Input-----

The first line of the input contains the string s (1 ≤ |s| ≤ 10 000) in its initial state, where |s| stands for the length of s. It contains only lowercase English letters.

Second line contains a single integer m (1 ≤ m ≤ 300) — the number of queries.

The i-th of the next m lines contains three integers l_{i}, r_{i} and k_{i} (1 ≤ l_{i} ≤ r_{i} ≤ |s|, 1 ≤ k_{i} ≤ 1 000 000) — the description of the i-th query.


-----Output-----

Print the resulting string s after processing all m queries.


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

Output
baabcaa



-----Note-----

The sample is described in problem statement.
user: Demiurges Shambambukli and Mazukta love to watch the games of ordinary people. Today, they noticed two men who play the following game.

There is a rooted tree on n nodes, m of which are leaves (a leaf is a nodes that does not have any children), edges of the tree are directed from parent to children. In the leaves of the tree integers from 1 to m are placed in such a way that each number appears exactly in one leaf.

Initially, the root of the tree contains a piece. Two players move this piece in turns, during a move a player moves the piece from its current nodes to one of its children; if the player can not make a move, the game ends immediately. The result of the game is the number placed in the leaf where a piece has completed its movement. The player who makes the first move tries to maximize the result of the game and the second player, on the contrary, tries to minimize the result. We can assume that both players move optimally well.

Demiurges are omnipotent, so before the game they can arbitrarily rearrange the numbers placed in the leaves. Shambambukli wants to rearrange numbers so that the result of the game when both players play optimally well is as large as possible, and Mazukta wants the result to be as small as possible. What will be the outcome of the game, if the numbers are rearranged by Shambambukli, and what will it be if the numbers are rearranged by Mazukta? Of course, the Demiurges choose the best possible option of arranging numbers.


-----Input-----

The first line contains a single integer n — the number of nodes in the tree (1 ≤ n ≤ 2·10^5).

Each of the next n - 1 lines contains two integers u_{i} and v_{i} (1 ≤ u_{i}, v_{i} ≤ n) — the ends of the edge of the tree; the edge leads from node u_{i} to node v_{i}. It is guaranteed that the described graph is a rooted tree, and the root is the node 1.


-----Output-----

Print two space-separated integers — the maximum possible and the minimum possible result of the game.


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

Output
3 2

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

Output
3 3



-----Note-----

Consider the first sample. The tree contains three leaves: 3, 4 and 5. If we put the maximum number 3 at node 3, then the first player moves there and the result will be 3. On the other hand, it is easy to see that for any rearrangement the first player can guarantee the result of at least 2.

In the second sample no matter what the arragment is the first player can go along the path that ends with a leaf with number 3.
user: Galya is playing one-dimensional Sea Battle on a 1 × n grid. In this game a ships are placed on the grid. Each of the ships consists of b consecutive cells. No cell can be part of two ships, however, the ships can touch each other.

Galya doesn't know the ships location. She can shoot to some cells and after each shot she is told if that cell was a part of some ship (this case is called "hit") or not (this case is called "miss").

Galya has already made k shots, all of them were misses.

Your task is to calculate the minimum number of cells such that if Galya shoot at all of them, she would hit at least one ship.

It is guaranteed that there is at least one valid ships placement.


-----Input-----

The first line contains four positive integers n, a, b, k (1 ≤ n ≤ 2·10^5, 1 ≤ a, b ≤ n, 0 ≤ k ≤ n - 1) — the length of the grid, the number of ships on the grid, the length of each ship and the number of shots Galya has already made.

The second line contains a string of length n, consisting of zeros and ones. If the i-th character is one, Galya has already made a shot to this cell. Otherwise, she hasn't. It is guaranteed that there are exactly k ones in this string. 


-----Output-----

In the first line print the minimum number of cells such that if Galya shoot at all of them, she would hit at least one ship.

In the second line print the cells Galya should shoot at.

Each cell should be printed exactly once. You can print the cells in arbitrary order. The cells are numbered from 1 to n, starting from the left.

If there are multiple answers, you can print any of them.


-----Examples-----
Input
5 1 2 1
00100

Output
2
4 2

Input
13 3 2 3
1000000010001

Output
2
7 11



-----Note-----

There is one ship in the first sample. It can be either to the left or to the right from the shot Galya has already made (the "1" character). So, it is necessary to make two shots: one at the left part, and one at the right part.
user: You are given an array of positive integers. While there are at least two equal elements, we will perform the following operation. We choose the smallest value $x$ that occurs in the array $2$ or more times. Take the first two occurrences of $x$ in this array (the two leftmost occurrences). Remove the left of these two occurrences, and the right one is replaced by the sum of this two values (that is, $2 \cdot x$).

Determine how the array will look after described operations are performed.

For example, consider the given array looks like $[3, 4, 1, 2, 2, 1, 1]$. It will be changed in the following way: $[3, 4, 1, 2, 2, 1, 1]~\rightarrow~[3, 4, 2, 2, 2, 1]~\rightarrow~[3, 4, 4, 2, 1]~\rightarrow~[3, 8, 2, 1]$.

If the given array is look like $[1, 1, 3, 1, 1]$ it will be changed in the following way: $[1, 1, 3, 1, 1]~\rightarrow~[2, 3, 1, 1]~\rightarrow~[2, 3, 2]~\rightarrow~[3, 4]$.


-----Input-----

The first line contains a single integer $n$ ($2 \le n \le 150\,000$) — the number of elements in the array.

The second line contains a sequence from $n$ elements $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^{9}$) — the elements of the array.


-----Output-----

In the first line print an integer $k$ — the number of elements in the array after all the performed operations. In the second line print $k$ integers — the elements of the array after all the performed operations.


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

Output
4
3 8 2 1 

Input
5
1 1 3 1 1

Output
2
3 4 

Input
5
10 40 20 50 30

Output
5
10 40 20 50 30 



-----Note-----

The first two examples were considered in the statement.

In the third example all integers in the given array are distinct, so it will not change.
user: You are given n integers a_1, a_2, ..., a_{n}. Find the number of pairs of indexes i, j (i < j) that a_{i} + a_{j} is a power of 2 (i. e. some integer x exists so that a_{i} + a_{j} = 2^{x}).


-----Input-----

The first line contains the single positive integer n (1 ≤ n ≤ 10^5) — the number of integers.

The second line contains n positive integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9).


-----Output-----

Print the number of pairs of indexes i, j (i < j) that a_{i} + a_{j} is a power of 2.


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

Output
2

Input
3
1 1 1

Output
3



-----Note-----

In the first example the following pairs of indexes include in answer: (1, 4) and (2, 4).

In the second example all pairs of indexes (i, j) (where i < j) include in answer.
user: JATC loves Banh-mi (a Vietnamese food). His affection for Banh-mi is so much that he always has it for breakfast. This morning, as usual, he buys a Banh-mi and decides to enjoy it in a special way.

First, he splits the Banh-mi into $n$ parts, places them on a row and numbers them from $1$ through $n$. For each part $i$, he defines the deliciousness of the part as $x_i \in \{0, 1\}$. JATC's going to eat those parts one by one. At each step, he chooses arbitrary remaining part and eats it. Suppose that part is the $i$-th part then his enjoyment of the Banh-mi will increase by $x_i$ and the deliciousness of all the remaining parts will also increase by $x_i$. The initial enjoyment of JATC is equal to $0$.

For example, suppose the deliciousness of $3$ parts are $[0, 1, 0]$. If JATC eats the second part then his enjoyment will become $1$ and the deliciousness of remaining parts will become $[1, \_, 1]$. Next, if he eats the first part then his enjoyment will become $2$ and the remaining parts will become $[\_, \_, 2]$. After eating the last part, JATC's enjoyment will become $4$.

However, JATC doesn't want to eat all the parts but to save some for later. He gives you $q$ queries, each of them consisting of two integers $l_i$ and $r_i$. For each query, you have to let him know what is the maximum enjoyment he can get if he eats all the parts with indices in the range $[l_i, r_i]$ in some order.

All the queries are independent of each other. Since the answer to the query could be very large, print it modulo $10^9+7$.


-----Input-----

The first line contains two integers $n$ and $q$ ($1 \le n, q \le 100\,000$).

The second line contains a string of $n$ characters, each character is either '0' or '1'. The $i$-th character defines the deliciousness of the $i$-th part.

Each of the following $q$ lines contains two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$) — the segment of the corresponding query.


-----Output-----

Print $q$ lines, where $i$-th of them contains a single integer — the answer to the $i$-th query modulo $10^9 + 7$.


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

Output
14
3

Input
3 2
111
1 2
3 3

Output
3
1



-----Note-----

In the first example:   For query $1$: One of the best ways for JATC to eats those parts is in this order: $1$, $4$, $3$, $2$.  For query $2$: Both $3$, $4$ and $4$, $3$ ordering give the same answer. 

In the second example, any order of eating parts leads to the same answer.