meetforever/GRPO_CL huggingface dataset:
user: In Takahashi Kingdom, there is a east-west railroad and N cities along it, numbered 1, 2, 3, ..., N from west to east.
A company called AtCoder Express possesses M trains, and the train i runs from City L_i to City R_i (it is possible that L_i = R_i).
Takahashi the king is interested in the following Q matters:
 - The number of the trains that runs strictly within the section from City p_i to City q_i, that is, the number of trains j such that p_i \leq L_j and R_j \leq q_i.
Although he is genius, this is too much data to process by himself. Find the answer for each of these Q queries to help him.

-----Constraints-----
 - N is an integer between 1 and 500 (inclusive).
 - M is an integer between 1 and 200 \ 000 (inclusive).
 - Q is an integer between 1 and 100 \ 000 (inclusive).
 - 1 \leq L_i \leq R_i \leq N (1 \leq i \leq M)
 - 1 \leq p_i \leq q_i \leq N (1 \leq i \leq Q)

-----Input-----
Input is given from Standard Input in the following format:
N M Q
L_1 R_1
L_2 R_2
:
L_M R_M
p_1 q_1
p_2 q_2
:
p_Q q_Q

-----Output-----
Print Q lines. The i-th line should contain the number of the trains that runs strictly within the section from City p_i to City q_i.

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

-----Sample Output-----
3

As all the trains runs within the section from City 1 to City 2, the answer to the only query is 3.
user: We have an integer N.
Print an integer x between N and 10^{13} (inclusive) such that, for every integer y between 2 and N (inclusive), the remainder when x is divided by y is 1.
Under the constraints of this problem, there is always at least one such integer x.

-----Constraints-----
 - All values in input are integers.
 - 2 \leq N \leq 30

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

-----Output-----
Print an integer x between N and 10^{13} (inclusive) such that, for every integer y between 2 and N (inclusive), the remainder when x is divided by y is 1.
If there are multiple such integers, any of them will be accepted.

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

-----Sample Output-----
7

The remainder when 7 is divided by 2 is 1, and the remainder when 7 is divided by 3 is 1, too.
7 is an integer between 3 and 10^{13}, so this is a desirable output.
user: There is a sequence of length N: A_1, A_2, ..., A_N. Initially, this sequence is a permutation of 1, 2, ..., N.
On this sequence, Snuke can perform the following operation:
 - Choose K consecutive elements in the sequence. Then, replace the value of each chosen element with the minimum value among the chosen elements.
Snuke would like to make all the elements in this sequence equal by repeating the operation above some number of times.
Find the minimum number of operations required.
It can be proved that, Under the constraints of this problem, this objective is always achievable.

-----Constraints-----
 - 2 \leq K \leq N \leq 100000
 - A_1, A_2, ..., A_N is a permutation of 1, 2, ..., N.

-----Input-----
Input is given from Standard Input in the following format:
N K
A_1 A_2 ... A_N

-----Output-----
Print the minimum number of operations required.

-----Sample Input-----
4 3
2 3 1 4

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

One optimal strategy is as follows:
 - In the first operation, choose the first, second and third elements. The sequence A becomes 1, 1, 1, 4.
 - In the second operation, choose the second, third and fourth elements. The sequence A becomes 1, 1, 1, 1.
user: You are given an integer N. Find the number of strings of length N that satisfy the following conditions, modulo 10^9+7:
 - The string does not contain characters other than A, C, G and T.
 - The string does not contain AGC as a substring.
 - The condition above cannot be violated by swapping two adjacent characters once.

-----Notes-----
A substring of a string T is a string obtained by removing zero or more characters from the beginning and the end of T.
For example, the substrings of ATCODER include TCO, AT, CODER, ATCODER and  (the empty string), but not AC.

-----Constraints-----
 - 3 \leq N \leq 100

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

-----Output-----
Print the number of strings of length N that satisfy the following conditions, modulo 10^9+7.

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

-----Sample Output-----
61

There are 4^3 = 64 strings of length 3 that do not contain characters other than A, C, G and T. Among them, only AGC, ACG and GAC violate the condition, so the answer is 64 - 3 = 61.
user: Olya loves energy drinks. She loves them so much that her room is full of empty cans from energy drinks.

Formally, her room can be represented as a field of n × m cells, each cell of which is empty or littered with cans.

Olya drank a lot of energy drink, so now she can run k meters per second. Each second she chooses one of the four directions (up, down, left or right) and runs from 1 to k meters in this direction. Of course, she can only run through empty cells.

Now Olya needs to get from cell (x_1, y_1) to cell (x_2, y_2). How many seconds will it take her if she moves optimally?

It's guaranteed that cells (x_1, y_1) and (x_2, y_2) are empty. These cells can coincide.


-----Input-----

The first line contains three integers n, m and k (1 ≤ n, m, k ≤ 1000) — the sizes of the room and Olya's speed.

Then n lines follow containing m characters each, the i-th of them contains on j-th position "#", if the cell (i, j) is littered with cans, and "." otherwise.

The last line contains four integers x_1, y_1, x_2, y_2 (1 ≤ x_1, x_2 ≤ n, 1 ≤ y_1, y_2 ≤ m) — the coordinates of the first and the last cells.


-----Output-----

Print a single integer — the minimum time it will take Olya to get from (x_1, y_1) to (x_2, y_2).

If it's impossible to get from (x_1, y_1) to (x_2, y_2), print -1.


-----Examples-----
Input
3 4 4
....
###.
....
1 1 3 1

Output
3
Input
3 4 1
....
###.
....
1 1 3 1

Output
8
Input
2 2 1
.#
#.
1 1 2 2

Output
-1


-----Note-----

In the first sample Olya should run 3 meters to the right in the first second, 2 meters down in the second second and 3 meters to the left in the third second.

In second sample Olya should run to the right for 3 seconds, then down for 2 seconds and then to the left for 3 seconds.

Olya does not recommend drinking energy drinks and generally believes that this is bad.
user: You are given a string $s$. You have to reverse it — that is, the first letter should become equal to the last letter before the reversal, the second letter should become equal to the second-to-last letter before the reversal — and so on. For example, if your goal is to reverse the string "abddea", you should get the string "aeddba". To accomplish your goal, you can swap the neighboring elements of the string. 

Your task is to calculate the minimum number of swaps you have to perform to reverse the given string.


-----Input-----

The first line contains one integer $n$ ($2 \le n \le 200\,000$) — the length of $s$.

The second line contains $s$ — a string consisting of $n$ lowercase Latin letters.


-----Output-----

Print one integer — the minimum number of swaps of neighboring elements you have to perform to reverse the string.


-----Examples-----
Input
5
aaaza

Output
2

Input
6
cbaabc

Output
0

Input
9
icpcsguru

Output
30



-----Note-----

In the first example, you have to swap the third and the fourth elements, so the string becomes "aazaa". Then you have to swap the second and the third elements, so the string becomes "azaaa". So, it is possible to reverse the string in two swaps.

Since the string in the second example is a palindrome, you don't have to do anything to reverse it.
user: There are $n$ students in the first grade of Nlogonia high school. The principal wishes to split the students into two classrooms (each student must be in exactly one of the classrooms). Two distinct students whose name starts with the same letter will be chatty if they are put in the same classroom (because they must have a lot in common). Let $x$ be the number of such pairs of students in a split. Pairs $(a, b)$ and $(b, a)$ are the same and counted only once.

For example, if there are $6$ students: "olivia", "jacob", "tanya", "jack", "oliver" and "jessica", then:  splitting into two classrooms ("jack", "jacob", "jessica", "tanya") and ("olivia", "oliver") will give $x=4$ ($3$ chatting pairs in the first classroom, $1$ chatting pair in the second classroom),  splitting into two classrooms ("jack", "tanya", "olivia") and ("jessica", "oliver", "jacob") will give $x=1$ ($0$ chatting pairs in the first classroom, $1$ chatting pair in the second classroom). 

You are given the list of the $n$ names. What is the minimum $x$ we can obtain by splitting the students into classrooms?

Note that it is valid to place all of the students in one of the classrooms, leaving the other one empty.


-----Input-----

The first line contains a single integer $n$ ($1\leq n \leq 100$) — the number of students.

After this $n$ lines follow.

The $i$-th line contains the name of the $i$-th student.

It is guaranteed each name is a string of lowercase English letters of length at most $20$. Note that multiple students may share the same name.


-----Output-----

The output must consist of a single integer $x$ — the minimum possible number of chatty pairs.


-----Examples-----
Input
4
jorge
jose
oscar
jerry

Output
1

Input
7
kambei
gorobei
shichiroji
kyuzo
heihachi
katsushiro
kikuchiyo

Output
2

Input
5
mike
mike
mike
mike
mike

Output
4



-----Note-----

In the first sample the minimum number of pairs is $1$. This can be achieved, for example, by putting everyone except jose in one classroom, and jose in the other, so jorge and jerry form the only chatty pair.

In the second sample the minimum number of pairs is $2$. This can be achieved, for example, by putting kambei, gorobei, shichiroji and kyuzo in one room and putting heihachi, katsushiro and kikuchiyo in the other room. In this case the two pairs are kambei and kyuzo, and katsushiro and kikuchiyo.

In the third sample the minimum number of pairs is $4$. This can be achieved by placing three of the students named mike in one classroom and the other two students in another classroom. Thus there will be three chatty pairs in one classroom and one chatty pair in the other classroom.
user: Mahmoud was trying to solve the vertex cover problem on trees. The problem statement is:

Given an undirected tree consisting of n nodes, find the minimum number of vertices that cover all the edges. Formally, we need to find a set of vertices such that for each edge (u, v) that belongs to the tree, either u is in the set, or v is in the set, or both are in the set. Mahmoud has found the following algorithm:  Root the tree at node 1.  Count the number of nodes at an even depth. Let it be evenCnt.  Count the number of nodes at an odd depth. Let it be oddCnt.  The answer is the minimum between evenCnt and oddCnt. 

The depth of a node in a tree is the number of edges in the shortest path between this node and the root. The depth of the root is 0.

Ehab told Mahmoud that this algorithm is wrong, but he didn't believe because he had tested his algorithm against many trees and it worked, so Ehab asked you to find 2 trees consisting of n nodes. The algorithm should find an incorrect answer for the first tree and a correct answer for the second one.


-----Input-----

The only line contains an integer n (2 ≤ n ≤ 10^5), the number of nodes in the desired trees.


-----Output-----

The output should consist of 2 independent sections, each containing a tree. The algorithm should find an incorrect answer for the tree in the first section and a correct answer for the tree in the second. If a tree doesn't exist for some section, output "-1" (without quotes) for that section only.

If the answer for a section exists, it should contain n - 1 lines, each containing 2 space-separated integers u and v (1 ≤ u, v ≤ n), which means that there's an undirected edge between node u and node v. If the given graph isn't a tree or it doesn't follow the format, you'll receive wrong answer verdict.

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


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

Output
-1
1 2

Input
8

Output
1 2
1 3
2 4
2 5
3 6
4 7
4 8
1 2
1 3
2 4
2 5
2 6
3 7
6 8


-----Note-----

In the first sample, there is only 1 tree with 2 nodes (node 1 connected to node 2). The algorithm will produce a correct answer in it so we printed  - 1 in the first section, but notice that we printed this tree in the second section.

In the second sample:

In the first tree, the algorithm will find an answer with 4 nodes, while there exists an answer with 3 nodes like this: [Image] In the second tree, the algorithm will find an answer with 3 nodes which is correct: [Image]
user: Valera has array a, consisting of n integers a_0, a_1, ..., a_{n} - 1, and function f(x), taking an integer from 0 to 2^{n} - 1 as its single argument. Value f(x) is calculated by formula $f(x) = \sum_{i = 0}^{n - 1} a_{i} \cdot b i t(i)$, where value bit(i) equals one if the binary representation of number x contains a 1 on the i-th position, and zero otherwise.

For example, if n = 4 and x = 11 (11 = 2^0 + 2^1 + 2^3), then f(x) = a_0 + a_1 + a_3.

Help Valera find the maximum of function f(x) among all x, for which an inequality holds: 0 ≤ x ≤ m.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^5) — the number of array elements. The next line contains n space-separated integers a_0, a_1, ..., a_{n} - 1 (0 ≤ a_{i} ≤ 10^4) — elements of array a.

The third line contains a sequence of digits zero and one without spaces s_0s_1... s_{n} - 1 — the binary representation of number m. Number m equals $\sum_{i = 0}^{n - 1} 2^{i} \cdot s_{i}$.


-----Output-----

Print a single integer — the maximum value of function f(x) for all $x \in [ 0 . . m ]$.


-----Examples-----
Input
2
3 8
10

Output
3

Input
5
17 0 10 2 1
11010

Output
27



-----Note-----

In the first test case m = 2^0 = 1, f(0) = 0, f(1) = a_0 = 3.

In the second sample m = 2^0 + 2^1 + 2^3 = 11, the maximum value of function equals f(5) = a_0 + a_2 = 17 + 10 = 27.
user: Little penguin Polo has an n × m matrix, consisting of integers. Let's index the matrix rows from 1 to n from top to bottom and let's index the columns from 1 to m from left to right. Let's represent the matrix element on the intersection of row i and column j as a_{ij}.

In one move the penguin can add or subtract number d from some matrix element. Find the minimum number of moves needed to make all matrix elements equal. If the described plan is impossible to carry out, say so.


-----Input-----

The first line contains three integers n, m and d (1 ≤ n, m ≤ 100, 1 ≤ d ≤ 10^4) — the matrix sizes and the d parameter. Next n lines contain the matrix: the j-th integer in the i-th row is the matrix element a_{ij} (1 ≤ a_{ij} ≤ 10^4).


-----Output-----

In a single line print a single integer — the minimum number of moves the penguin needs to make all matrix elements equal. If that is impossible, print "-1" (without the quotes).


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

Output
4

Input
1 2 7
6 7

Output
-1
user: Recently Luba bought a very interesting book. She knows that it will take t seconds to read the book. Luba wants to finish reading as fast as she can.

But she has some work to do in each of n next days. The number of seconds that Luba has to spend working during i-th day is a_{i}. If some free time remains, she can spend it on reading.

Help Luba to determine the minimum number of day when she finishes reading.

It is guaranteed that the answer doesn't exceed n.

Remember that there are 86400 seconds in a day.


-----Input-----

The first line contains two integers n and t (1 ≤ n ≤ 100, 1 ≤ t ≤ 10^6) — the number of days and the time required to read the book.

The second line contains n integers a_{i} (0 ≤ a_{i} ≤ 86400) — the time Luba has to spend on her work during i-th day.


-----Output-----

Print the minimum day Luba can finish reading the book.

It is guaranteed that answer doesn't exceed n.


-----Examples-----
Input
2 2
86400 86398

Output
2

Input
2 86400
0 86400

Output
1
user: Little Susie listens to fairy tales before bed every day. Today's fairy tale was about wood cutters and the little girl immediately started imagining the choppers cutting wood. She imagined the situation that is described below.

There are n trees located along the road at points with coordinates x_1, x_2, ..., x_{n}. Each tree has its height h_{i}. Woodcutters can cut down a tree and fell it to the left or to the right. After that it occupies one of the segments [x_{i} - h_{i}, x_{i}] or [x_{i};x_{i} + h_{i}]. The tree that is not cut down occupies a single point with coordinate x_{i}. Woodcutters can fell a tree if the segment to be occupied by the fallen tree doesn't contain any occupied point. The woodcutters want to process as many trees as possible, so Susie wonders, what is the maximum number of trees to fell. 


-----Input-----

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

Next n lines contain pairs of integers x_{i}, h_{i} (1 ≤ x_{i}, h_{i} ≤ 10^9) — the coordinate and the height of the і-th tree.

The pairs are given in the order of ascending x_{i}. No two trees are located at the point with the same coordinate.


-----Output-----

Print a single number — the maximum number of trees that you can cut down by the given rules.


-----Examples-----
Input
5
1 2
2 1
5 10
10 9
19 1

Output
3

Input
5
1 2
2 1
5 10
10 9
20 1

Output
4



-----Note-----

In the first sample you can fell the trees like that:   fell the 1-st tree to the left — now it occupies segment [ - 1;1]  fell the 2-nd tree to the right — now it occupies segment [2;3]  leave the 3-rd tree — it occupies point 5  leave the 4-th tree — it occupies point 10  fell the 5-th tree to the right — now it occupies segment [19;20] 

In the second sample you can also fell 4-th tree to the right, after that it will occupy segment [10;19].
user: You are given a rooted tree with n vertices. The vertices are numbered from 1 to n, the root is the vertex number 1.

Each vertex has a color, let's denote the color of vertex v by c_{v}. Initially c_{v} = 0.

You have to color the tree into the given colors using the smallest possible number of steps. On each step you can choose a vertex v and a color x, and then color all vectices in the subtree of v (including v itself) in color x. In other words, for every vertex u, such that the path from root to u passes through v, set c_{u} = x.

It is guaranteed that you have to color each vertex in a color different from 0.

You can learn what a rooted tree is using the link: https://en.wikipedia.org/wiki/Tree_(graph_theory).


-----Input-----

The first line contains a single integer n (2 ≤ n ≤ 10^4) — the number of vertices in the tree.

The second line contains n - 1 integers p_2, p_3, ..., p_{n} (1 ≤ p_{i} < i), where p_{i} means that there is an edge between vertices i and p_{i}.

The third line contains n integers c_1, c_2, ..., c_{n} (1 ≤ c_{i} ≤ n), where c_{i} is the color you should color the i-th vertex into.

It is guaranteed that the given graph is a tree. 


-----Output-----

Print a single integer — the minimum number of steps you have to perform to color the tree into given colors.


-----Examples-----
Input
6
1 2 2 1 5
2 1 1 1 1 1

Output
3

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

Output
5



-----Note-----

The tree from the first sample is shown on the picture (numbers are vetices' indices):

$A$

On first step we color all vertices in the subtree of vertex 1 into color 2 (numbers are colors):

[Image]

On seond step we color all vertices in the subtree of vertex 5 into color 1:

[Image]

On third step we color all vertices in the subtree of vertex 2 into color 1:

[Image]

The tree from the second sample is shown on the picture (numbers are vetices' indices):

[Image]

On first step we color all vertices in the subtree of vertex 1 into color 3 (numbers are colors):

[Image]

On second step we color all vertices in the subtree of vertex 3 into color 1:

$8$

On third step we color all vertices in the subtree of vertex 6 into color 2:

[Image]

On fourth step we color all vertices in the subtree of vertex 4 into color 1:

[Image]

On fith step we color all vertices in the subtree of vertex 7 into color 3:

[Image]
user: There is a programming language in which every program is a non-empty sequence of "<" and ">" signs and digits. Let's explain how the interpreter of this programming language works. A program is interpreted using movement of instruction pointer (IP) which consists of two parts.  Current character pointer (CP);  Direction pointer (DP) which can point left or right; 

Initially CP points to the leftmost character of the sequence and DP points to the right.

We repeat the following steps until the first moment that CP points to somewhere outside the sequence.  If CP is pointing to a digit the interpreter prints that digit then CP moves one step according to the direction of DP. After that the value of the printed digit in the sequence decreases by one. If the printed digit was 0 then it cannot be decreased therefore it's erased from the sequence and the length of the sequence decreases by one.  If CP is pointing to "<" or ">" then the direction of DP changes to "left" or "right" correspondingly. Then CP moves one step according to DP. If the new character that CP is pointing to is "<" or ">" then the previous character will be erased from the sequence. 

If at any moment the CP goes outside of the sequence the execution is terminated.

It's obvious the every program in this language terminates after some steps.

We have a sequence s_1, s_2, ..., s_{n} of "<", ">" and digits. You should answer q queries. Each query gives you l and r and asks how many of each digit will be printed if we run the sequence s_{l}, s_{l} + 1, ..., s_{r} as an independent program in this language.


-----Input-----

The first line of input contains two integers n and q (1 ≤ n, q ≤ 100) — represents the length of the sequence s and the number of queries. 

The second line contains s, a sequence of "<", ">" and digits (0..9) written from left to right. Note, that the characters of s are not separated with spaces. 

The next q lines each contains two integers l_{i} and r_{i} (1 ≤ l_{i} ≤ r_{i} ≤ n) — the i-th query.


-----Output-----

For each query print 10 space separated integers: x_0, x_1, ..., x_9 where x_{i} equals the number of times the interpreter prints i while running the corresponding program. Print answers to the queries in the order they are given in input.


-----Examples-----
Input
7 4
1>3>22<
1 3
4 7
7 7
1 7

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