meetforever/GRPO_CL huggingface dataset:
user: Given is a positive integer N.

Find the number of pairs (A, B) of positive integers not greater than N that satisfy the following condition:
 - When A and B are written in base ten without leading zeros, the last digit of A is equal to the first digit of B, and the first digit of A is equal to the last digit of B.

-----Constraints-----
 - 1 \leq N \leq 2 \times 10^5
 - All values in input are integers.

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

-----Output-----
Print the answer.

-----Sample Input-----
25

-----Sample Output-----
17

The following 17 pairs satisfy the condition: (1,1), (1,11), (2,2), (2,22), (3,3), (4,4), (5,5), (6,6), (7,7), (8,8), (9,9), (11,1), (11,11), (12,21), (21,12), (22,2), and (22,22).
user: Takahashi has a water bottle with the shape of a rectangular prism whose base is a square of side a~\mathrm{cm} and whose height is b~\mathrm{cm}. (The thickness of the bottle can be ignored.)
We will pour x~\mathrm{cm}^3 of water into the bottle, and gradually tilt the bottle around one of the sides of the base.
When will the water be spilled? More formally, find the maximum angle in which we can tilt the bottle without spilling any water.

-----Constraints-----
 - All values in input are integers.
 - 1 \leq a \leq 100
 - 1 \leq b \leq 100
 - 1 \leq x \leq a^2b

-----Input-----
Input is given from Standard Input in the following format:
a b x

-----Output-----
Print the maximum angle in which we can tilt the bottle without spilling any water, in degrees.
Your output will be judged as correct when the absolute or relative error from the judge's output is at most 10^{-6}.

-----Sample Input-----
2 2 4

-----Sample Output-----
45.0000000000

This bottle has a cubic shape, and it is half-full. The water gets spilled when we tilt the bottle more than 45 degrees.
user: Takahashi has N sticks that are distinguishable from each other. The length of the i-th stick is L_i.
He is going to form a triangle using three of these sticks. Let a, b, and c be the lengths of the three sticks used. Here, all of the following conditions must be satisfied:
 - a < b + c
 - b < c + a
 - c < a + b
How many different triangles can be formed? Two triangles are considered different when there is a stick used in only one of them.

-----Constraints-----
 - All values in input are integers.
 - 3 \leq N \leq 2 \times 10^3
 - 1 \leq L_i \leq 10^3

-----Input-----
Input is given from Standard Input in the following format:
N
L_1 L_2 ... L_N

-----Constraints-----
Print the number of different triangles that can be formed.

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

-----Sample Output-----
1

Only one triangle can be formed: the triangle formed by the first, second, and third sticks.
user: As a token of his gratitude, Takahashi has decided to give his mother an integer sequence.
The sequence A needs to satisfy the conditions below:
 - A consists of integers between X and Y (inclusive).
 - For each 1\leq i \leq |A|-1, A_{i+1} is a multiple of A_i and strictly greater than A_i.
Find the maximum possible length of the sequence.

-----Constraints-----
 - 1 \leq X \leq Y \leq 10^{18}
 - All input values are integers.

-----Input-----
Input is given from Standard Input in the following format:
X Y

-----Output-----
Print the maximum possible length of the sequence.

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

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

The sequence 3,6,18 satisfies the conditions.
user: For an integer n not less than 0, let us define f(n) as follows:
 - f(n) = 1 (if n < 2)
 - f(n) = n f(n-2) (if n \geq 2)
Given is an integer N. Find the number of trailing zeros in the decimal notation of f(N).

-----Constraints-----
 - 0 \leq N \leq 10^{18}

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

-----Output-----
Print the number of trailing zeros in the decimal notation of f(N).

-----Sample Input-----
12

-----Sample Output-----
1

f(12) = 12 × 10 × 8 × 6 × 4 × 2 = 46080, which has one trailing zero.
user: An altar enshrines N stones arranged in a row from left to right. The color of the i-th stone from the left (1 \leq i \leq N) is given to you as a character c_i; R stands for red and W stands for white.
You can do the following two kinds of operations any number of times in any order:
 - Choose two stones (not necessarily adjacent) and swap them.
 - Choose one stone and change its color (from red to white and vice versa).
According to a fortune-teller, a white stone placed to the immediate left of a red stone will bring a disaster. At least how many operations are needed to reach a situation without such a white stone?

-----Constraints-----
 - 2 \leq N \leq 200000
 - c_i is R or W.

-----Input-----
Input is given from Standard Input in the following format:
N
c_{1}c_{2}...c_{N}

-----Output-----
Print an integer representing the minimum number of operations needed.

-----Sample Input-----
4
WWRR

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

For example, the two operations below will achieve the objective.
 - Swap the 1-st and 3-rd stones from the left, resulting in RWWR.
 - Change the color of the 4-th stone from the left, resulting in RWWW.
user: Little Chris is very keen on his toy blocks. His teacher, however, wants Chris to solve more problems, so he decided to play a trick on Chris.

There are exactly s blocks in Chris's set, each block has a unique number from 1 to s. Chris's teacher picks a subset of blocks X and keeps it to himself. He will give them back only if Chris can pick such a non-empty subset Y from the remaining blocks, that the equality holds: $\sum_{x \in X}(x - 1) = \sum_{y \in Y}(s - y)$ "Are you kidding me?", asks Chris.

For example, consider a case where s = 8 and Chris's teacher took the blocks with numbers 1, 4 and 5. One way for Chris to choose a set is to pick the blocks with numbers 3 and 6, see figure. Then the required sums would be equal: (1 - 1) + (4 - 1) + (5 - 1) = (8 - 3) + (8 - 6) = 7.

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

However, now Chris has exactly s = 10^6 blocks. Given the set X of blocks his teacher chooses, help Chris to find the required set Y!


-----Input-----

The first line of input contains a single integer n (1 ≤ n ≤ 5·10^5), the number of blocks in the set X. The next line contains n distinct space-separated integers x_1, x_2, ..., x_{n} (1 ≤ x_{i} ≤ 10^6), the numbers of the blocks in X.

Note: since the size of the input and output could be very large, don't use slow output techniques in your language. For example, do not use input and output streams (cin, cout) in C++.


-----Output-----

In the first line of output print a single integer m (1 ≤ m ≤ 10^6 - n), the number of blocks in the set Y. In the next line output m distinct space-separated integers y_1, y_2, ..., y_{m} (1 ≤ y_{i} ≤ 10^6), such that the required equality holds. The sets X and Y should not intersect, i.e. x_{i} ≠ y_{j} for all i, j (1 ≤ i ≤ n; 1 ≤ j ≤ m). It is guaranteed that at least one solution always exists. If there are multiple solutions, output any of them.


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

Output
2
999993 1000000
Input
1
1

Output
1
1000000
user: One day Vitaly was going home late at night and wondering: how many people aren't sleeping at that moment? To estimate, Vitaly decided to look which windows are lit in the house he was passing by at that moment.

Vitaly sees a building of n floors and 2·m windows on each floor. On each floor there are m flats numbered from 1 to m, and two consecutive windows correspond to each flat. If we number the windows from 1 to 2·m from left to right, then the j-th flat of the i-th floor has windows 2·j - 1 and 2·j in the corresponding row of windows (as usual, floors are enumerated from the bottom). Vitaly thinks that people in the flat aren't sleeping at that moment if at least one of the windows corresponding to this flat has lights on.

Given the information about the windows of the given house, your task is to calculate the number of flats where, according to Vitaly, people aren't sleeping.


-----Input-----

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 100) — the number of floors in the house and the number of flats on each floor respectively.

Next n lines describe the floors from top to bottom and contain 2·m characters each. If the i-th window of the given floor has lights on, then the i-th character of this line is '1', otherwise it is '0'.


-----Output-----

Print a single integer — the number of flats that have lights on in at least one window, that is, the flats where, according to Vitaly, people aren't sleeping.


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

Output
3

Input
1 3
1 1 0 1 0 0

Output
2



-----Note-----

In the first test case the house has two floors, two flats on each floor. That is, in total there are 4 flats. The light isn't on only on the second floor in the left flat. That is, in both rooms of the flat the light is off.

In the second test case the house has one floor and the first floor has three flats. The light is on in the leftmost flat (in both windows) and in the middle flat (in one window). In the right flat the light is off.
user: You are given an array $a_1, a_2, \dots, a_n$. All $a_i$ are pairwise distinct.

Let's define function $f(l, r)$ as follows:   let's define array $b_1, b_2, \dots, b_{r - l + 1}$, where $b_i = a_{l - 1 + i}$;  sort array $b$ in increasing order;  result of the function $f(l, r)$ is $\sum\limits_{i = 1}^{r - l + 1}{b_i \cdot i}$. 

Calculate $\left(\sum\limits_{1 \le l \le r \le n}{f(l, r)}\right) \mod (10^9+7)$, i.e. total sum of $f$ for all subsegments of $a$ modulo $10^9+7$.


-----Input-----

The first line contains one integer $n$ ($1 \le n \le 5 \cdot 10^5$) — the length of array $a$.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$, $a_i \neq a_j$ for $i \neq j$) — array $a$.


-----Output-----

Print one integer — the total sum of $f$ for all subsegments of $a$ modulo $10^9+7$


-----Examples-----
Input
4
5 2 4 7

Output
167

Input
3
123456789 214365879 987654321

Output
582491518



-----Note-----

Description of the first example:   $f(1, 1) = 5 \cdot 1 = 5$;  $f(1, 2) = 2 \cdot 1 + 5 \cdot 2 = 12$;  $f(1, 3) = 2 \cdot 1 + 4 \cdot 2 + 5 \cdot 3 = 25$;  $f(1, 4) = 2 \cdot 1 + 4 \cdot 2 + 5 \cdot 3 + 7 \cdot 4 = 53$;  $f(2, 2) = 2 \cdot 1 = 2$;  $f(2, 3) = 2 \cdot 1 + 4 \cdot 2 = 10$;  $f(2, 4) = 2 \cdot 1 + 4 \cdot 2 + 7 \cdot 3 = 31$;  $f(3, 3) = 4 \cdot 1 = 4$;  $f(3, 4) = 4 \cdot 1 + 7 \cdot 2 = 18$;  $f(4, 4) = 7 \cdot 1 = 7$;
user: Old timers of Summer Informatics School can remember previous camps in which each student was given a drink of his choice on the vechorka (late-evening meal). Or may be the story was more complicated?

There are $n$ students living in a building, and for each of them the favorite drink $a_i$ is known. So you know $n$ integers $a_1, a_2, \dots, a_n$, where $a_i$ ($1 \le a_i \le k$) is the type of the favorite drink of the $i$-th student. The drink types are numbered from $1$ to $k$.

There are infinite number of drink sets. Each set consists of exactly two portions of the same drink. In other words, there are $k$ types of drink sets, the $j$-th type contains two portions of the drink $j$. The available number of sets of each of the $k$ types is infinite.

You know that students will receive the minimum possible number of sets to give all students exactly one drink. Obviously, the number of sets will be exactly $\lceil \frac{n}{2} \rceil$, where $\lceil x \rceil$ is $x$ rounded up.

After students receive the sets, they will distribute their portions by their choice: each student will get exactly one portion. Note, that if $n$ is odd then one portion will remain unused and the students' teacher will drink it.

What is the maximum number of students that can get their favorite drink if $\lceil \frac{n}{2} \rceil$ sets will be chosen optimally and students will distribute portions between themselves optimally?


-----Input-----

The first line of the input contains two integers $n$ and $k$ ($1 \le n, k \le 1\,000$) — the number of students in the building and the number of different drinks.

The next $n$ lines contain student's favorite drinks. The $i$-th line contains a single integer from $1$ to $k$ — the type of the favorite drink of the $i$-th student.


-----Output-----

Print exactly one integer — the maximum number of students that can get a favorite drink.


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

Output
4

Input
10 3
2
1
3
2
3
3
1
3
1
2

Output
9



-----Note-----

In the first example, students could choose three sets with drinks $1$, $1$ and $2$ (so they will have two sets with two drinks of the type $1$ each and one set with two drinks of the type $2$, so portions will be $1, 1, 1, 1, 2, 2$). This way all students except the second one will get their favorite drinks.

Another possible answer is sets with drinks $1$, $2$ and $3$. In this case the portions will be $1, 1, 2, 2, 3, 3$. Then all the students except one will gain their favorite drinks. The only student that will not gain the favorite drink will be a student with $a_i = 1$ (i.e. the first, the third or the fourth).
user: Some large corporation where Polycarpus works has its own short message service center (SMSC). The center's task is to send all sorts of crucial information. Polycarpus decided to check the efficiency of the SMSC. 

For that, he asked to give him the statistics of the performance of the SMSC for some period of time. In the end, Polycarpus got a list of n tasks that went to the SMSC of the corporation. Each task was described by the time it was received by the SMSC and the number of text messages to send. More formally, the i-th task was described by two integers t_{i} and c_{i} — the receiving time (the second) and the number of the text messages, correspondingly.

Polycarpus knows that the SMSC cannot send more than one text message per second. The SMSC uses a queue to organize its work. Consider a time moment x, the SMSC work at that moment as follows:

  If at the time moment x the queue is not empty, then SMSC sends one message from the queue (SMSC gets the message from the head of the queue). Otherwise it doesn't send messages at the time moment x.  If at the time moment x SMSC receives a task, then it adds to the queue all the messages from this task (SMSC adds messages to the tail of the queue). Note, that the messages from the task cannot be send at time moment x. That's because the decision about sending message or not is made at point 1 before adding these messages to the queue. 

Given the information about all n tasks, Polycarpus wants to count two values: the time when the last text message was sent and the maximum size of the queue at some time. Help him count these two characteristics he needs to evaluate the efficiency of the SMSC.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 10^3) — the number of tasks of the SMSC. Next n lines contain the tasks' descriptions: the i-th line contains two space-separated integers t_{i} and c_{i} (1 ≤ t_{i}, c_{i} ≤ 10^6) — the time (the second) when the i-th task was received and the number of messages to send, correspondingly.

It is guaranteed that all tasks were received at different moments of time. It is guaranteed that the tasks are sorted in the chronological order, that is, t_{i} < t_{i} + 1 for all integer i (1 ≤ i < n).


-----Output-----

In a single line print two space-separated integers — the time when the last text message was sent and the maximum queue size at a certain moment of time.


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

Output
3 1

Input
1
1000000 10

Output
1000010 10

Input
3
3 3
4 3
5 3

Output
12 7



-----Note-----

In the first test sample: 

  second 1: the first message has appeared in the queue, the queue's size is 1;  second 2: the first message is sent, the second message has been received, the queue's size is 1;  second 3: the second message is sent, the queue's size is 0, 

Thus, the maximum size of the queue is 1, the last message was sent at the second 3.
user: The administration of the Tomsk Region firmly believes that it's time to become a megacity (that is, get population of one million). Instead of improving the demographic situation, they decided to achieve its goal by expanding the boundaries of the city.

The city of Tomsk can be represented as point on the plane with coordinates (0; 0). The city is surrounded with n other locations, the i-th one has coordinates (x_{i}, y_{i}) with the population of k_{i} people. You can widen the city boundaries to a circle of radius r. In such case all locations inside the circle and on its border are included into the city.

Your goal is to write a program that will determine the minimum radius r, to which is necessary to expand the boundaries of Tomsk, so that it becomes a megacity.


-----Input-----

The first line of the input contains two integers n and s (1 ≤ n ≤ 10^3; 1 ≤ s < 10^6) — the number of locatons around Tomsk city and the population of the city. Then n lines follow. The i-th line contains three integers — the x_{i} and y_{i} coordinate values of the i-th location and the number k_{i} of people in it (1 ≤ k_{i} < 10^6). Each coordinate is an integer and doesn't exceed 10^4 in its absolute value.

It is guaranteed that no two locations are at the same point and no location is at point (0; 0).


-----Output-----

In the output, print "-1" (without the quotes), if Tomsk won't be able to become a megacity. Otherwise, in the first line print a single real number — the minimum radius of the circle that the city needs to expand to in order to become a megacity.

The answer is considered correct if the absolute or relative error don't exceed 10^{ - 6}.


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

Output
2.8284271

Input
4 999998
1 1 2
2 2 1
3 3 1
2 -2 1

Output
1.4142136

Input
2 1
1 1 999997
2 2 1

Output
-1
user: Eugeny loves listening to music. He has n songs in his play list. We know that song number i has the duration of t_{i} minutes. Eugeny listens to each song, perhaps more than once. He listens to song number i c_{i} times. Eugeny's play list is organized as follows: first song number 1 plays c_1 times, then song number 2 plays c_2 times, ..., in the end the song number n plays c_{n} times.

Eugeny took a piece of paper and wrote out m moments of time when he liked a song. Now for each such moment he wants to know the number of the song that played at that moment. The moment x means that Eugeny wants to know which song was playing during the x-th minute of his listening to the play list.

Help Eugeny and calculate the required numbers of songs.


-----Input-----

The first line contains two integers n, m (1 ≤ n, m ≤ 10^5). The next n lines contain pairs of integers. The i-th line contains integers c_{i}, t_{i} (1 ≤ c_{i}, t_{i} ≤ 10^9) — the description of the play list. It is guaranteed that the play list's total duration doesn't exceed 10^9 $(\sum_{i = 1}^{n} c_{i} \cdot t_{i} \leq 10^{9})$.

The next line contains m positive integers v_1, v_2, ..., v_{m}, that describe the moments Eugeny has written out. It is guaranteed that there isn't such moment of time v_{i}, when the music doesn't play any longer. It is guaranteed that v_{i} < v_{i} + 1 (i < m).

The moment of time v_{i} means that Eugeny wants to know which song was playing during the v_{i}-th munite from the start of listening to the playlist.


-----Output-----

Print m integers — the i-th number must equal the number of the song that was playing during the v_{i}-th minute after Eugeny started listening to the play list.


-----Examples-----
Input
1 2
2 8
1 16

Output
1
1

Input
4 9
1 2
2 1
1 1
2 2
1 2 3 4 5 6 7 8 9

Output
1
1
2
2
3
4
4
4
4
user: At the children's day, the child came to Picks's house, and messed his house up. Picks was angry at him. A lot of important things were lost, in particular the favorite set of Picks.

Fortunately, Picks remembers something about his set S:  its elements were distinct integers from 1 to limit;  the value of $\sum_{x \in S} \text{lowbit}(x)$ was equal to sum; here lowbit(x) equals 2^{k} where k is the position of the first one in the binary representation of x. For example, lowbit(10010_2) = 10_2, lowbit(10001_2) = 1_2, lowbit(10000_2) = 10000_2 (binary representation). 

Can you help Picks and find any set S, that satisfies all the above conditions?


-----Input-----

The first line contains two integers: sum, limit (1 ≤ sum, limit ≤ 10^5).


-----Output-----

In the first line print an integer n (1 ≤ n ≤ 10^5), denoting the size of S. Then print the elements of set S in any order. If there are multiple answers, print any of them.

If it's impossible to find a suitable set, print -1.


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

Output
2
4 5

Input
4 3

Output
3
2 3 1

Input
5 1

Output
-1



-----Note-----

In sample test 1: lowbit(4) = 4, lowbit(5) = 1, 4 + 1 = 5.

In sample test 2: lowbit(1) = 1, lowbit(2) = 2, lowbit(3) = 1, 1 + 2 + 1 = 4.
user: Constanze is the smartest girl in her village but she has bad eyesight.

One day, she was able to invent an incredible machine! When you pronounce letters, the machine will inscribe them onto a piece of paper. For example, if you pronounce 'c', 'o', 'd', and 'e' in that order, then the machine will inscribe "code" onto the paper. Thanks to this machine, she can finally write messages without using her glasses.

However, her dumb friend Akko decided to play a prank on her. Akko tinkered with the machine so that if you pronounce 'w', it will inscribe "uu" instead of "w", and if you pronounce 'm', it will inscribe "nn" instead of "m"! Since Constanze had bad eyesight, she was not able to realize what Akko did.

The rest of the letters behave the same as before: if you pronounce any letter besides 'w' and 'm', the machine will just inscribe it onto a piece of paper.

The next day, I received a letter in my mailbox. I can't understand it so I think it's either just some gibberish from Akko, or Constanze made it using her machine. But since I know what Akko did, I can just list down all possible strings that Constanze's machine would have turned into the message I got and see if anything makes sense.

But I need to know how much paper I will need, and that's why I'm asking you for help. Tell me the number of strings that Constanze's machine would've turned into the message I got.

But since this number can be quite large, tell me instead its remainder when divided by $10^9+7$.

If there are no strings that Constanze's machine would've turned into the message I got, then print $0$.


-----Input-----

Input consists of a single line containing a string $s$ ($1 \leq |s| \leq 10^5$) — the received message. $s$ contains only lowercase Latin letters.


-----Output-----

Print a single integer — the number of strings that Constanze's machine would've turned into the message $s$, modulo $10^9+7$.


-----Examples-----
Input
ouuokarinn

Output
4

Input
banana

Output
1

Input
nnn

Output
3

Input
amanda

Output
0



-----Note-----

For the first example, the candidate strings are the following: "ouuokarinn", "ouuokarim", "owokarim", and "owokarinn".

For the second example, there is only one: "banana".

For the third example, the candidate strings are the following: "nm", "mn" and "nnn".

For the last example, there are no candidate strings that the machine can turn into "amanda", since the machine won't inscribe 'm'.