meetforever/GRPO_CL huggingface dataset:
user: Manao works on a sports TV. He's spent much time watching the football games of some country. After a while he began to notice different patterns. For example, each team has two sets of uniforms: home uniform and guest uniform. When a team plays a game at home, the players put on the home uniform. When a team plays as a guest on somebody else's stadium, the players put on the guest uniform. The only exception to that rule is: when the home uniform color of the host team matches the guests' uniform, the host team puts on its guest uniform as well. For each team the color of the home and guest uniform is different.

There are n teams taking part in the national championship. The championship consists of n·(n - 1) games: each team invites each other team to its stadium. At this point Manao wondered: how many times during the championship is a host team going to put on the guest uniform? Note that the order of the games does not affect this number.

You know the colors of the home and guest uniform for each team. For simplicity, the colors are numbered by integers in such a way that no two distinct colors have the same number. Help Manao find the answer to his question.


-----Input-----

The first line contains an integer n (2 ≤ n ≤ 30). Each of the following n lines contains a pair of distinct space-separated integers h_{i}, a_{i} (1 ≤ h_{i}, a_{i} ≤ 100) — the colors of the i-th team's home and guest uniforms, respectively.


-----Output-----

In a single line print the number of games where the host team is going to play in the guest uniform.


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

Output
1

Input
4
100 42
42 100
5 42
100 5

Output
5

Input
2
1 2
1 2

Output
0



-----Note-----

In the first test case the championship consists of 6 games. The only game with the event in question is the game between teams 2 and 1 on the stadium of team 2.

In the second test sample the host team will have to wear guest uniform in the games between teams: 1 and 2, 2 and 1, 2 and 3, 3 and 4, 4 and 2 (the host team is written first).
user: Valera loves his garden, where n fruit trees grow.

This year he will enjoy a great harvest! On the i-th tree b_{i} fruit grow, they will ripen on a day number a_{i}. Unfortunately, the fruit on the tree get withered, so they can only be collected on day a_{i} and day a_{i} + 1 (all fruits that are not collected in these two days, become unfit to eat).

Valera is not very fast, but there are some positive points. Valera is ready to work every day. In one day, Valera can collect no more than v fruits. The fruits may be either from the same tree, or from different ones. What is the maximum amount of fruit Valera can collect for all time, if he operates optimally well?


-----Input-----

The first line contains two space-separated integers n and v (1 ≤ n, v ≤ 3000) — the number of fruit trees in the garden and the number of fruits that Valera can collect in a day. 

Next n lines contain the description of trees in the garden. The i-th line contains two space-separated integers a_{i} and b_{i} (1 ≤ a_{i}, b_{i} ≤ 3000) — the day the fruits ripen on the i-th tree and the number of fruits on the i-th tree.


-----Output-----

Print a single integer — the maximum number of fruit that Valera can collect. 


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

Output
8

Input
5 10
3 20
2 20
1 20
4 20
5 20

Output
60



-----Note-----

In the first sample, in order to obtain the optimal answer, you should act as follows.   On the first day collect 3 fruits from the 1-st tree.  On the second day collect 1 fruit from the 2-nd tree and 2 fruits from the 1-st tree.  On the third day collect the remaining fruits from the 2-nd tree.  

In the second sample, you can only collect 60 fruits, the remaining fruit will simply wither.
user: Some time ago Leonid have known about idempotent functions. Idempotent function defined on a set {1, 2, ..., n} is such function $g : \{1,2, \ldots, n \} \rightarrow \{1,2, \ldots, n \}$, that for any $x \in \{1,2, \ldots, n \}$ the formula g(g(x)) = g(x) holds.

Let's denote as f^{(}k)(x) the function f applied k times to the value x. More formally, f^{(1)}(x) = f(x), f^{(}k)(x) = f(f^{(}k - 1)(x)) for each k > 1.

You are given some function $f : \{1,2, \ldots, n \} \rightarrow \{1,2, \ldots, n \}$. Your task is to find minimum positive integer k such that function f^{(}k)(x) is idempotent.


-----Input-----

In the first line of the input there is a single integer n (1 ≤ n ≤ 200) — the size of function f domain.

In the second line follow f(1), f(2), ..., f(n) (1 ≤ f(i) ≤ n for each 1 ≤ i ≤ n), the values of a function.


-----Output-----

Output minimum k such that function f^{(}k)(x) is idempotent.


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

Output
1

Input
3
2 3 3

Output
2

Input
3
2 3 1

Output
3



-----Note-----

In the first sample test function f(x) = f^{(1)}(x) is already idempotent since f(f(1)) = f(1) = 1, f(f(2)) = f(2) = 2, f(f(3)) = f(3) = 2, f(f(4)) = f(4) = 4.

In the second sample test:   function f(x) = f^{(1)}(x) isn't idempotent because f(f(1)) = 3 but f(1) = 2;  function f(x) = f^{(2)}(x) is idempotent since for any x it is true that f^{(2)}(x) = 3, so it is also true that f^{(2)}(f^{(2)}(x)) = 3. 

In the third sample test:   function f(x) = f^{(1)}(x) isn't idempotent because f(f(1)) = 3 but f(1) = 2;  function f(f(x)) = f^{(2)}(x) isn't idempotent because f^{(2)}(f^{(2)}(1)) = 2 but f^{(2)}(1) = 3;  function f(f(f(x))) = f^{(3)}(x) is idempotent since it is identity function: f^{(3)}(x) = x for any $x \in \{1,2,3 \}$ meaning that the formula f^{(3)}(f^{(3)}(x)) = f^{(3)}(x) also holds.
user: Polycarpus loves hamburgers very much. He especially adores the hamburgers he makes with his own hands. Polycarpus thinks that there are only three decent ingredients to make hamburgers from: a bread, sausage and cheese. He writes down the recipe of his favorite "Le Hamburger de Polycarpus" as a string of letters 'B' (bread), 'S' (sausage) и 'C' (cheese). The ingredients in the recipe go from bottom to top, for example, recipe "ВSCBS" represents the hamburger where the ingredients go from bottom to top as bread, sausage, cheese, bread and sausage again.

Polycarpus has n_{b} pieces of bread, n_{s} pieces of sausage and n_{c} pieces of cheese in the kitchen. Besides, the shop nearby has all three ingredients, the prices are p_{b} rubles for a piece of bread, p_{s} for a piece of sausage and p_{c} for a piece of cheese.

Polycarpus has r rubles and he is ready to shop on them. What maximum number of hamburgers can he cook? You can assume that Polycarpus cannot break or slice any of the pieces of bread, sausage or cheese. Besides, the shop has an unlimited number of pieces of each ingredient.


-----Input-----

The first line of the input contains a non-empty string that describes the recipe of "Le Hamburger de Polycarpus". The length of the string doesn't exceed 100, the string contains only letters 'B' (uppercase English B), 'S' (uppercase English S) and 'C' (uppercase English C).

The second line contains three integers n_{b}, n_{s}, n_{c} (1 ≤ n_{b}, n_{s}, n_{c} ≤ 100) — the number of the pieces of bread, sausage and cheese on Polycarpus' kitchen. The third line contains three integers p_{b}, p_{s}, p_{c} (1 ≤ p_{b}, p_{s}, p_{c} ≤ 100) — the price of one piece of bread, sausage and cheese in the shop. Finally, the fourth line contains integer r (1 ≤ r ≤ 10^12) — the number of rubles Polycarpus has.

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


-----Output-----

Print the maximum number of hamburgers Polycarpus can make. If he can't make any hamburger, print 0.


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

Output
2

Input
BBC
1 10 1
1 10 1
21

Output
7

Input
BSC
1 1 1
1 1 3
1000000000000

Output
200000000001
user: zscoder wants to generate an input file for some programming competition problem.

His input is a string consisting of n letters 'a'. He is too lazy to write a generator so he will manually generate the input in a text editor.

Initially, the text editor is empty. It takes him x seconds to insert or delete a letter 'a' from the text file and y seconds to copy the contents of the entire text file, and duplicate it.

zscoder wants to find the minimum amount of time needed for him to create the input file of exactly n letters 'a'. Help him to determine the amount of time needed to generate the input.


-----Input-----

The only line contains three integers n, x and y (1 ≤ n ≤ 10^7, 1 ≤ x, y ≤ 10^9) — the number of letters 'a' in the input file and the parameters from the problem statement.


-----Output-----

Print the only integer t — the minimum amount of time needed to generate the input file.


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

Output
4

Input
8 1 10

Output
8
user: You are given n × m table. Each cell of the table is colored white or black. Find the number of non-empty sets of cells such that:

  All cells in a set have the same color.  Every two cells in a set share row or column. 


-----Input-----

The first line of input contains integers n and m (1 ≤ n, m ≤ 50) — the number of rows and the number of columns correspondingly.

The next n lines of input contain descriptions of rows. There are m integers, separated by spaces, in each line. The number equals 0 if the corresponding cell is colored white and equals 1 if the corresponding cell is colored black.


-----Output-----

Output single integer  — the number of non-empty sets from the problem description.


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

Output
1

Input
2 3
1 0 1
0 1 0

Output
8



-----Note-----

In the second example, there are six one-element sets. Additionally, there are two two-element sets, the first one consists of the first and the third cells of the first row, the second one consists of the first and the third cells of the second row. To sum up, there are 8 sets.
user: Many students live in a dormitory. A dormitory is a whole new world of funny amusements and possibilities but it does have its drawbacks. 

There is only one shower and there are multiple students who wish to have a shower in the morning. That's why every morning there is a line of five people in front of the dormitory shower door. As soon as the shower opens, the first person from the line enters the shower. After a while the first person leaves the shower and the next person enters the shower. The process continues until everybody in the line has a shower.

Having a shower takes some time, so the students in the line talk as they wait. At each moment of time the students talk in pairs: the (2i - 1)-th man in the line (for the current moment) talks with the (2i)-th one. 

Let's look at this process in more detail. Let's number the people from 1 to 5. Let's assume that the line initially looks as 23154 (person number 2 stands at the beginning of the line). Then, before the shower opens, 2 talks with 3, 1 talks with 5, 4 doesn't talk with anyone. Then 2 enters the shower. While 2 has a shower, 3 and 1 talk, 5 and 4 talk too. Then, 3 enters the shower. While 3 has a shower, 1 and 5 talk, 4 doesn't talk to anyone. Then 1 enters the shower and while he is there, 5 and 4 talk. Then 5 enters the shower, and then 4 enters the shower.

We know that if students i and j talk, then the i-th student's happiness increases by g_{ij} and the j-th student's happiness increases by g_{ji}. Your task is to find such initial order of students in the line that the total happiness of all students will be maximum in the end. Please note that some pair of students may have a talk several times. In the example above students 1 and 5 talk while they wait for the shower to open and while 3 has a shower.


-----Input-----

The input consists of five lines, each line contains five space-separated integers: the j-th number in the i-th line shows g_{ij} (0 ≤ g_{ij} ≤ 10^5). It is guaranteed that g_{ii} = 0 for all i.

Assume that the students are numbered from 1 to 5.


-----Output-----

Print a single integer — the maximum possible total happiness of the students.


-----Examples-----
Input
0 0 0 0 9
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
7 0 0 0 0

Output
32

Input
0 43 21 18 2
3 0 21 11 65
5 2 0 1 4
54 62 12 0 99
87 64 81 33 0

Output
620



-----Note-----

In the first sample, the optimal arrangement of the line is 23154. In this case, the total happiness equals:

(g_23 + g_32 + g_15 + g_51) + (g_13 + g_31 + g_54 + g_45) + (g_15 + g_51) + (g_54 + g_45) = 32.
user: The term of this problem is the same as the previous one, the only exception — increased restrictions.


-----Input-----

The first line contains two positive integers n and k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ 10^9) — the number of ingredients and the number of grams of the magic powder.

The second line contains the sequence a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9), where the i-th number is equal to the number of grams of the i-th ingredient, needed to bake one cookie.

The third line contains the sequence b_1, b_2, ..., b_{n} (1 ≤ b_{i} ≤ 10^9), where the i-th number is equal to the number of grams of the i-th ingredient, which Apollinaria has.


-----Output-----

Print the maximum number of cookies, which Apollinaria will be able to bake using the ingredients that she has and the magic powder.


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

Output
2000000000

Input
10 1
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
1 1 1 1 1 1 1 1 1 1

Output
0

Input
3 1
2 1 4
11 3 16

Output
4

Input
4 3
4 3 5 6
11 12 14 20

Output
3
user: The subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

You are given an integer $n$. 

You have to find a sequence $s$ consisting of digits $\{1, 3, 7\}$ such that it has exactly $n$ subsequences equal to $1337$.

For example, sequence $337133377$ has $6$ subsequences equal to $1337$:   $337\underline{1}3\underline{3}\underline{3}7\underline{7}$ (you can remove the second and fifth characters);  $337\underline{1}\underline{3}3\underline{3}7\underline{7}$ (you can remove the third and fifth characters);  $337\underline{1}\underline{3}\underline{3}37\underline{7}$ (you can remove the fourth and fifth characters);  $337\underline{1}3\underline{3}\underline{3}\underline{7}7$ (you can remove the second and sixth characters);  $337\underline{1}\underline{3}3\underline{3}\underline{7}7$ (you can remove the third and sixth characters);  $337\underline{1}\underline{3}\underline{3}3\underline{7}7$ (you can remove the fourth and sixth characters). 

Note that the length of the sequence $s$ must not exceed $10^5$.

You have to answer $t$ independent queries.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 10$) — the number of queries. 

Next $t$ lines contains a description of queries: the $i$-th line contains one integer $n_i$ ($1 \le n_i \le 10^9$).


-----Output-----

For the $i$-th query print one string $s_i$ ($1 \le |s_i| \le 10^5$) consisting of digits $\{1, 3, 7\}$. String $s_i$ must have exactly $n_i$ subsequences $1337$. If there are multiple such strings, print any of them.


-----Example-----
Input
2
6
1

Output
113337
1337
user: Pari has a friend who loves palindrome numbers. A palindrome number is a number that reads the same forward or backward. For example 12321, 100001 and 1 are palindrome numbers, while 112 and 1021 are not.

Pari is trying to love them too, but only very special and gifted people can understand the beauty behind palindrome numbers. Pari loves integers with even length (i.e. the numbers with even number of digits), so she tries to see a lot of big palindrome numbers with even length (like a 2-digit 11 or 6-digit 122221), so maybe she could see something in them.

Now Pari asks you to write a program that gets a huge integer n from the input and tells what is the n-th even-length positive palindrome number?


-----Input-----

The only line of the input contains a single integer n (1 ≤ n ≤ 10^{100 000}).


-----Output-----

Print the n-th even-length palindrome number.


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

Output
11

Input
10

Output
1001



-----Note-----

The first 10 even-length palindrome numbers are 11, 22, 33, ... , 88, 99 and 1001.
user: Little Artem found a grasshopper. He brought it to his house and constructed a jumping area for him.

The area looks like a strip of cells 1 × n. Each cell contains the direction for the next jump and the length of that jump. Grasshopper starts in the first cell and follows the instructions written on the cells. Grasshopper stops immediately if it jumps out of the strip. Now Artem wants to find out if this will ever happen.


-----Input-----

The first line of the input contains a single integer n (1 ≤ n ≤ 100 000) — length of the strip. 

Next line contains a string of length n which consists of characters "<" and ">" only, that provide the direction of the jump from the corresponding cell. Next line contains n integers d_{i} (1 ≤ d_{i} ≤ 10^9) — the length of the jump from the i-th cell.


-----Output-----

Print "INFINITE" (without quotes) if grasshopper will continue his jumps forever. Otherwise print "FINITE" (without quotes).


-----Examples-----
Input
2
><
1 2

Output
FINITE

Input
3
>><
2 1 1

Output
INFINITE


-----Note-----

In the first sample grasshopper starts from the first cell and jumps to the right on the next cell. When he is in the second cell he needs to jump two cells left so he will jump out of the strip.

Second sample grasshopper path is 1 - 3 - 2 - 3 - 2 - 3 and so on. The path is infinite.
user: You are given a string s consisting only of characters 0 and 1. A substring [l, r] of s is a string s_{l}s_{l} + 1s_{l} + 2... s_{r}, and its length equals to r - l + 1. A substring is called balanced if the number of zeroes (0) equals to the number of ones in this substring.

You have to determine the length of the longest balanced substring of s.


-----Input-----

The first line contains n (1 ≤ n ≤ 100000) — the number of characters in s.

The second line contains a string s consisting of exactly n characters. Only characters 0 and 1 can appear in s.


-----Output-----

If there is no non-empty balanced substring in s, print 0. Otherwise, print the length of the longest balanced substring.


-----Examples-----
Input
8
11010111

Output
4

Input
3
111

Output
0



-----Note-----

In the first example you can choose the substring [3, 6]. It is balanced, and its length is 4. Choosing the substring [2, 5] is also possible.

In the second example it's impossible to find a non-empty balanced substring.
user: Our good friend Mole is trying to code a big message. He is typing on an unusual keyboard with characters arranged in following way:

qwertyuiop

asdfghjkl;

zxcvbnm,./



Unfortunately Mole is blind, so sometimes it is problem for him to put his hands accurately. He accidentally moved both his hands with one position to the left or to the right. That means that now he presses not a button he wants, but one neighboring button (left or right, as specified in input).

We have a sequence of characters he has typed and we want to find the original message.


-----Input-----

First line of the input contains one letter describing direction of shifting ('L' or 'R' respectively for left or right).

Second line contains a sequence of characters written by Mole. The size of this sequence will be no more than 100. Sequence contains only symbols that appear on Mole's keyboard. It doesn't contain spaces as there is no space on Mole's keyboard.

It is guaranteed that even though Mole hands are moved, he is still pressing buttons on keyboard and not hitting outside it.


-----Output-----

Print a line that contains the original message.


-----Examples-----
Input
R
s;;upimrrfod;pbr

Output
allyouneedislove
user: Mashmokh works in a factory. At the end of each day he must turn off all of the lights. 

The lights on the factory are indexed from 1 to n. There are n buttons in Mashmokh's room indexed from 1 to n as well. If Mashmokh pushes button with index i, then each light with index not less than i that is still turned on turns off.

Mashmokh is not very clever. So instead of pushing the first button he pushes some of the buttons randomly each night. He pushed m distinct buttons b_1, b_2, ..., b_{m} (the buttons were pushed consecutively in the given order) this night. Now he wants to know for each light the index of the button that turned this light off. Please note that the index of button b_{i} is actually b_{i}, not i.

Please, help Mashmokh, print these indices.


-----Input-----

The first line of the input contains two space-separated integers n and m (1 ≤ n, m ≤ 100), the number of the factory lights and the pushed buttons respectively. The next line contains m distinct space-separated integers b_1, b_2, ..., b_{m} (1 ≤ b_{i} ≤ n).

It is guaranteed that all lights will be turned off after pushing all buttons.


-----Output-----

Output n space-separated integers where the i-th number is index of the button that turns the i-th light off.


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

Output
1 1 3 4 4 

Input
5 5
5 4 3 2 1

Output
1 2 3 4 5 



-----Note-----

In the first sample, after pressing button number 4, lights 4 and 5 are turned off and lights 1, 2 and 3 are still on. Then after pressing button number 3, light number 3 is turned off as well. Pressing button number 1 turns off lights number 1 and 2 as well so pressing button number 2 in the end has no effect. Thus button number 4 turned lights 4 and 5 off, button number 3 turned light 3 off and button number 1 turned light 1 and 2 off.
user: Vanya loves playing. He even has a special set of cards to play with. Each card has a single integer. The number on the card can be positive, negative and can even be equal to zero. The only limit is, the number on each card doesn't exceed x in the absolute value.

Natasha doesn't like when Vanya spends a long time playing, so she hid all of his cards. Vanya became sad and started looking for the cards but he only found n of them. Vanya loves the balance, so he wants the sum of all numbers on found cards equal to zero. On the other hand, he got very tired of looking for cards. Help the boy and say what is the minimum number of cards does he need to find to make the sum equal to zero?

You can assume that initially Vanya had infinitely many cards with each integer number from  - x to x.

 


-----Input-----

The first line contains two integers: n (1 ≤ n ≤ 1000) — the number of found cards and x (1 ≤ x ≤ 1000) — the maximum absolute value of the number on a card. The second line contains n space-separated integers — the numbers on found cards. It is guaranteed that the numbers do not exceed x in their absolute value.


-----Output-----

Print a single number — the answer to the problem.


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

Output
1

Input
2 3
-2 -2

Output
2



-----Note-----

In the first sample, Vanya needs to find a single card with number -2.

In the second sample, Vanya needs to find two cards with number 2. He can't find a single card with the required number as the numbers on the lost cards do not exceed 3 in their absolute value.