meetforever/GRPO_CL huggingface dataset:
user: Every Codeforces user has rating, described with one integer, possibly negative or zero. Users are divided into two divisions. The first division is for users with rating 1900 or higher. Those with rating 1899 or lower belong to the second division. In every contest, according to one's performance, his or her rating changes by some value, possibly negative or zero.

Limak competed in n contests in the year 2016. He remembers that in the i-th contest he competed in the division d_{i} (i.e. he belonged to this division just before the start of this contest) and his rating changed by c_{i} just after the contest. Note that negative c_{i} denotes the loss of rating.

What is the maximum possible rating Limak can have right now, after all n contests? If his rating may be arbitrarily big, print "Infinity". If there is no scenario matching the given information, print "Impossible".


-----Input-----

The first line of the input contains a single integer n (1 ≤ n ≤ 200 000).

The i-th of next n lines contains two integers c_{i} and d_{i} ( - 100 ≤ c_{i} ≤ 100, 1 ≤ d_{i} ≤ 2), describing Limak's rating change after the i-th contest and his division during the i-th contest contest.


-----Output-----

If Limak's current rating can be arbitrarily big, print "Infinity" (without quotes). If the situation is impossible, print "Impossible" (without quotes). Otherwise print one integer, denoting the maximum possible value of Limak's current rating, i.e. rating after the n contests.


-----Examples-----
Input
3
-7 1
5 2
8 2

Output
1907

Input
2
57 1
22 2

Output
Impossible

Input
1
-5 1

Output
Infinity

Input
4
27 2
13 1
-50 1
8 2

Output
1897



-----Note-----

In the first sample, the following scenario matches all information Limak remembers and has maximum possible final rating:  Limak has rating 1901 and belongs to the division 1 in the first contest. His rating decreases by 7.  With rating 1894 Limak is in the division 2. His rating increases by 5.  Limak has rating 1899 and is still in the division 2. In the last contest of the year he gets  + 8 and ends the year with rating 1907. 

In the second sample, it's impossible that Limak is in the division 1, his rating increases by 57 and after that Limak is in the division 2 in the second contest.
user: You are given a string q. A sequence of k strings s_1, s_2, ..., s_{k} is called beautiful, if the concatenation of these strings is string q (formally, s_1 + s_2 + ... + s_{k} = q) and the first characters of these strings are distinct.

Find any beautiful sequence of strings or determine that the beautiful sequence doesn't exist.


-----Input-----

The first line contains a positive integer k (1 ≤ k ≤ 26) — the number of strings that should be in a beautiful sequence. 

The second line contains string q, consisting of lowercase Latin letters. The length of the string is within range from 1 to 100, inclusive.


-----Output-----

If such sequence doesn't exist, then print in a single line "NO" (without the quotes). Otherwise, print in the first line "YES" (without the quotes) and in the next k lines print the beautiful sequence of strings s_1, s_2, ..., s_{k}.

If there are multiple possible answers, print any of them.


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

Output
YES
abca

Input
2
aaacas

Output
YES
aaa
cas

Input
4
abc

Output
NO



-----Note-----

In the second sample there are two possible answers: {"aaaca", "s"} and {"aaa", "cas"}.
user: -----Input-----

The only line of the input is a string of 7 characters. The first character is letter A, followed by 6 digits. The input is guaranteed to be valid (for certain definition of "valid").


-----Output-----

Output a single integer.


-----Examples-----
Input
A221033

Output
21

Input
A223635

Output
22

Input
A232726

Output
23
user: Once again Tavas started eating coffee mix without water! Keione told him that it smells awful, but he didn't stop doing that. That's why Keione told his smart friend, SaDDas to punish him! SaDDas took Tavas' headphones and told him: "If you solve the following problem, I'll return it to you." [Image] 

The problem is: 

You are given a lucky number n. Lucky numbers are the positive integers whose decimal representations contain only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

If we sort all lucky numbers in increasing order, what's the 1-based index of n? 

Tavas is not as smart as SaDDas, so he asked you to do him a favor and solve this problem so he can have his headphones back.


-----Input-----

The first and only line of input contains a lucky number n (1 ≤ n ≤ 10^9).


-----Output-----

Print the index of n among all lucky numbers.


-----Examples-----
Input
4

Output
1

Input
7

Output
2

Input
77

Output
6
user: Mr. Chanek is currently participating in a science fair that is popular in town. He finds an exciting puzzle in the fair and wants to solve it.

There are $N$ atoms numbered from $1$ to $N$. These atoms are especially quirky. Initially, each atom is in normal state. Each atom can be in an excited. Exciting atom $i$ requires $D_i$ energy. When atom $i$ is excited, it will give $A_i$ energy. You can excite any number of atoms (including zero).

These atoms also form a peculiar one-way bond. For each $i$, $(1 \le i < N)$, if atom $i$ is excited, atom $E_i$ will also be excited at no cost. Initially, $E_i$ = $i+1$. Note that atom $N$ cannot form a bond to any atom.

Mr. Chanek must change exactly $K$ bonds. Exactly $K$ times, Mr. Chanek chooses an atom $i$, $(1 \le i < N)$ and changes $E_i$ to a different value other than $i$ and the current $E_i$. Note that an atom's bond can remain unchanged or changed more than once. Help Mr. Chanek determine the maximum energy that he can achieve!

note: You must first change exactly $K$ bonds before you can start exciting atoms.


-----Input-----

The first line contains two integers $N$ $K$ $(4 \le N \le 10^5, 0 \le K < N)$, the number of atoms, and the number of bonds that must be changed.

The second line contains $N$ integers $A_i$ $(1 \le A_i \le 10^6)$, which denotes the energy given by atom $i$ when on excited state.

The third line contains $N$ integers $D_i$ $(1 \le D_i \le 10^6)$, which denotes the energy needed to excite atom $i$.


-----Output-----

A line with an integer that denotes the maximum number of energy that Mr. Chanek can get.


-----Example-----
Input
6 1
5 6 7 8 10 2
3 5 6 7 1 10

Output
35



-----Note-----

An optimal solution to change $E_5$ to 1 and then excite atom 5 with energy 1. It will cause atoms 1, 2, 3, 4, 5 be excited. The total energy gained by Mr. Chanek is (5 + 6 + 7 + 8 + 10) - 1 = 35.

Another possible way is to change $E_3$ to 1 and then exciting atom 3 (which will excite atom 1, 2, 3) and exciting atom 4 (which will excite atom 4, 5, 6). The total energy gained by Mr. Chanek is (5 + 6 + 7 + 8 + 10 + 2) - (6 + 7) = 25 which is not optimal.
user: Sergey is testing a next-generation processor. Instead of bytes the processor works with memory cells consisting of n bits. These bits are numbered from 1 to n. An integer is stored in the cell in the following way: the least significant bit is stored in the first bit of the cell, the next significant bit is stored in the second bit, and so on; the most significant bit is stored in the n-th bit.

Now Sergey wants to test the following instruction: "add 1 to the value of the cell". As a result of the instruction, the integer that is written in the cell must be increased by one; if some of the most significant bits of the resulting number do not fit into the cell, they must be discarded.

Sergey wrote certain values ​​of the bits in the cell and is going to add one to its value. How many bits of the cell will change after the operation?


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 100) — the number of bits in the cell.

The second line contains a string consisting of n characters — the initial state of the cell. The first character denotes the state of the first bit of the cell. The second character denotes the second least significant bit and so on. The last character denotes the state of the most significant bit.


-----Output-----

Print a single integer — the number of bits in the cell which change their state after we add 1 to the cell.


-----Examples-----
Input
4
1100

Output
3

Input
4
1111

Output
4



-----Note-----

In the first sample the cell ends up with value 0010, in the second sample — with 0000.
user: Recenlty Luba got a credit card and started to use it. Let's consider n consecutive days Luba uses the card.

She starts with 0 money on her account.

In the evening of i-th day a transaction a_{i} occurs. If a_{i} > 0, then a_{i} bourles are deposited to Luba's account. If a_{i} < 0, then a_{i} bourles are withdrawn. And if a_{i} = 0, then the amount of money on Luba's account is checked.

In the morning of any of n days Luba can go to the bank and deposit any positive integer amount of burles to her account. But there is a limitation: the amount of money on the account can never exceed d.

It can happen that the amount of money goes greater than d by some transaction in the evening. In this case answer will be «-1».

Luba must not exceed this limit, and also she wants that every day her account is checked (the days when a_{i} = 0) the amount of money on her account is non-negative. It takes a lot of time to go to the bank, so Luba wants to know the minimum number of days she needs to deposit some money to her account (if it is possible to meet all the requirements). Help her!


-----Input-----

The first line contains two integers n, d (1 ≤ n ≤ 10^5, 1 ≤ d ≤ 10^9) —the number of days and the money limitation.

The second line contains n integer numbers a_1, a_2, ... a_{n} ( - 10^4 ≤ a_{i} ≤ 10^4), where a_{i} represents the transaction in i-th day.


-----Output-----

Print -1 if Luba cannot deposit the money to her account in such a way that the requirements are met. Otherwise print the minimum number of days Luba has to deposit money.


-----Examples-----
Input
5 10
-1 5 0 -5 3

Output
0

Input
3 4
-10 0 20

Output
-1

Input
5 10
-5 0 10 -11 0

Output
2
user: You are given two integer sequences S and T of length N and M, respectively, both consisting of integers between 1 and 10^5 (inclusive).
In how many pairs of a subsequence of S and a subsequence of T do the two subsequences are the same in content?
Here the subsequence of A is a sequence obtained by removing zero or more elements from A and concatenating the remaining elements without changing the order.
For both S and T, we distinguish two subsequences if the sets of the indices of the removed elements are different, even if the subsequences are the same in content.
Since the answer can be tremendous, print the number modulo 10^9+7.

-----Constraints-----
 - 1 \leq N, M \leq 2 \times 10^3
 - The length of S is N.
 - The length of T is M.     
 - 1 \leq S_i, T_i \leq 10^5
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N M
S_1 S_2 ... S_{N-1} S_{N}
T_1 T_2 ... T_{M-1} T_{M}

-----Output-----
Print the number of pairs of a subsequence of S and a subsequence of T such that the subsequences are the same in content, modulo 10^9+7.

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

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

S has four subsequences: (), (1), (3), (1, 3).
T has four subsequences: (), (3), (1), (3, 1).
There are 1 \times 1 pair of subsequences in which the subsequences are both (), 1 \times 1 pair of subsequences in which the subsequences are both (1), and 1 \times 1 pair of subsequences in which the subsequences are both (3), for a total of three pairs.
user: You're given an array $a$ of length $2n$. Is it possible to reorder it in such way so that the sum of the first $n$ elements isn't equal to the sum of the last $n$ elements?


-----Input-----

The first line contains an integer $n$ ($1 \le n \le 1000$), where $2n$ is the number of elements in the array $a$.

The second line contains $2n$ space-separated integers $a_1$, $a_2$, $\ldots$, $a_{2n}$ ($1 \le a_i \le 10^6$) — the elements of the array $a$.


-----Output-----

If there's no solution, print "-1" (without quotes). Otherwise, print a single line containing $2n$ space-separated integers. They must form a reordering of $a$. You are allowed to not change the order.


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

Output
2 1 3 1 1 2
Input
1
1 1

Output
-1


-----Note-----

In the first example, the first $n$ elements have sum $2+1+3=6$ while the last $n$ elements have sum $1+1+2=4$. The sums aren't equal.

In the second example, there's no solution.
user: In mathematics, the Pythagorean theorem — is a relation in Euclidean geometry among the three sides of a right-angled triangle. In terms of areas, it states:

 In any right-angled triangle, the area of the square whose side is the hypotenuse (the side opposite the right angle) is equal to the sum of the areas of the squares whose sides are the two legs (the two sides that meet at a right angle). 

The theorem can be written as an equation relating the lengths of the sides a, b and c, often called the Pythagorean equation:

a^2 + b^2 = c^2

where c represents the length of the hypotenuse, and a and b represent the lengths of the other two sides.

 [Image] 

Given n, your task is to count how many right-angled triangles with side-lengths a, b and c that satisfied an inequality 1 ≤ a ≤ b ≤ c ≤ n.


-----Input-----

The only line contains one integer n (1 ≤ n ≤ 10^4) as we mentioned above.


-----Output-----

Print a single integer — the answer to the problem.


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

Output
1

Input
74

Output
35
user: You have $n \times n$ square grid and an integer $k$. Put an integer in each cell while satisfying the conditions below.  All numbers in the grid should be between $1$ and $k$ inclusive.  Minimum number of the $i$-th row is $1$ ($1 \le i \le n$).  Minimum number of the $j$-th column is $1$ ($1 \le j \le n$). 

Find the number of ways to put integers in the grid. Since the answer can be very large, find the answer modulo $(10^{9} + 7)$. [Image] These are the examples of valid and invalid grid when $n=k=2$. 


-----Input-----

The only line contains two integers $n$ and $k$ ($1 \le n \le 250$, $1 \le k \le 10^{9}$).


-----Output-----

Print the answer modulo $(10^{9} + 7)$.


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

Output
7

Input
123 456789

Output
689974806



-----Note-----

In the first example, following $7$ cases are possible. [Image] 

In the second example, make sure you print the answer modulo $(10^{9} + 7)$.
user: Seryozha conducts a course dedicated to building a map of heights of Stepanovo recreation center. He laid a rectangle grid of size $n \times m$ cells on a map (rows of grid are numbered from $1$ to $n$ from north to south, and columns are numbered from $1$ to $m$ from west to east). After that he measured the average height of each cell above Rybinsk sea level and obtained a matrix of heights of size $n \times m$. The cell $(i, j)$ lies on the intersection of the $i$-th row and the $j$-th column and has height $h_{i, j}$. 

Seryozha is going to look at the result of his work in the browser. The screen of Seryozha's laptop can fit a subrectangle of size $a \times b$ of matrix of heights ($1 \le a \le n$, $1 \le b \le m$). Seryozha tries to decide how the weather can affect the recreation center — for example, if it rains, where all the rainwater will gather. To do so, he is going to find the cell having minimum height among all cells that are shown on the screen of his laptop.

Help Seryozha to calculate the sum of heights of such cells for all possible subrectangles he can see on his screen. In other words, you have to calculate the sum of minimum heights in submatrices of size $a \times b$ with top left corners in $(i, j)$ over all $1 \le i \le n - a + 1$ and $1 \le j \le m - b + 1$.

Consider the sequence $g_i = (g_{i - 1} \cdot x + y) \bmod z$. You are given integers $g_0$, $x$, $y$ and $z$. By miraculous coincidence, $h_{i, j} = g_{(i - 1) \cdot m + j - 1}$ ($(i - 1) \cdot m + j - 1$ is the index).


-----Input-----

The first line of the input contains four integers $n$, $m$, $a$ and $b$ ($1 \le n, m \le 3\,000$, $1 \le a \le n$, $1 \le b \le m$) — the number of rows and columns in the matrix Seryozha has, and the number of rows and columns that can be shown on the screen of the laptop, respectively.

The second line of the input contains four integers $g_0$, $x$, $y$ and $z$ ($0 \le g_0, x, y < z \le 10^9$).


-----Output-----

Print a single integer — the answer to the problem.


-----Example-----
Input
3 4 2 1
1 2 3 59

Output
111



-----Note-----

The matrix from the first example:  $\left. \begin{array}{|c|c|c|c|} \hline 1 & {5} & {13} & {29} \\ \hline 2 & {7} & {17} & {37} \\ \hline 18 & {39} & {22} & {47} \\ \hline \end{array} \right.$
user: Mad scientist Mike is busy carrying out experiments in chemistry. Today he will attempt to join three atoms into one molecule.

A molecule consists of atoms, with some pairs of atoms connected by atomic bonds. Each atom has a valence number — the number of bonds the atom must form with other atoms. An atom can form one or multiple bonds with any other atom, but it cannot form a bond with itself. The number of bonds of an atom in the molecule must be equal to its valence number. [Image] 

Mike knows valence numbers of the three atoms. Find a molecule that can be built from these atoms according to the stated rules, or determine that it is impossible.


-----Input-----

The single line of the input contains three space-separated integers a, b and c (1 ≤ a, b, c ≤ 10^6) — the valence numbers of the given atoms.


-----Output-----

If such a molecule can be built, print three space-separated integers — the number of bonds between the 1-st and the 2-nd, the 2-nd and the 3-rd, the 3-rd and the 1-st atoms, correspondingly. If there are multiple solutions, output any of them. If there is no solution, print "Impossible" (without the quotes).


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

Output
0 1 1

Input
3 4 5

Output
1 3 2

Input
4 1 1

Output
Impossible



-----Note-----

The first sample corresponds to the first figure. There are no bonds between atoms 1 and 2 in this case.

The second sample corresponds to the second figure. There is one or more bonds between each pair of atoms.

The third sample corresponds to the third figure. There is no solution, because an atom cannot form bonds with itself.

The configuration in the fourth figure is impossible as each atom must have at least one atomic bond.
user: In Berland it is the holiday of equality. In honor of the holiday the king decided to equalize the welfare of all citizens in Berland by the expense of the state treasury. 

Totally in Berland there are n citizens, the welfare of each of them is estimated as the integer in a_{i} burles (burle is the currency in Berland).

You are the royal treasurer, which needs to count the minimum charges of the kingdom on the king's present. The king can only give money, he hasn't a power to take away them. 


-----Input-----

The first line contains the integer n (1 ≤ n ≤ 100) — the number of citizens in the kingdom.

The second line contains n integers a_1, a_2, ..., a_{n}, where a_{i} (0 ≤ a_{i} ≤ 10^6) — the welfare of the i-th citizen.


-----Output-----

In the only line print the integer S — the minimum number of burles which are had to spend.


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

Output
10
Input
5
1 1 0 1 1

Output
1
Input
3
1 3 1

Output
4
Input
1
12

Output
0


-----Note-----

In the first example if we add to the first citizen 4 burles, to the second 3, to the third 2 and to the fourth 1, then the welfare of all citizens will equal 4.

In the second example it is enough to give one burle to the third citizen. 

In the third example it is necessary to give two burles to the first and the third citizens to make the welfare of citizens equal 3.

In the fourth example it is possible to give nothing to everyone because all citizens have 12 burles.
user: Flatland has recently introduced a new type of an eye check for the driver's licence. The check goes like that: there is a plane with mannequins standing on it. You should tell the value of the minimum angle with the vertex at the origin of coordinates and with all mannequins standing inside or on the boarder of this angle. 

As you spend lots of time "glued to the screen", your vision is impaired. So you have to write a program that will pass the check for you.


-----Input-----

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

Next n lines contain two space-separated integers each: x_{i}, y_{i} (|x_{i}|, |y_{i}| ≤ 1000) — the coordinates of the i-th mannequin. It is guaranteed that the origin of the coordinates has no mannequin. It is guaranteed that no two mannequins are located in the same point on the plane.


-----Output-----

Print a single real number — the value of the sought angle in degrees. The answer will be considered valid if the relative or absolute error doesn't exceed 10^{ - 6}. 


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

Output
90.0000000000

Input
3
2 0
0 2
-2 2

Output
135.0000000000

Input
4
2 0
0 2
-2 0
0 -2

Output
270.0000000000

Input
2
2 1
1 2

Output
36.8698976458



-----Note-----

Solution for the first sample test is shown below:  [Image] 

Solution for the second sample test is shown below:  [Image] 

Solution for the third sample test is shown below:  [Image] 

Solution for the fourth sample test is shown below:  $\#$
user: In this problem MEX of a certain array is the smallest positive integer not contained in this array.

Everyone knows this definition, including Lesha. But Lesha loves MEX, so he comes up with a new problem involving MEX every day, including today.

You are given an array $a$ of length $n$. Lesha considers all the non-empty subarrays of the initial array and computes MEX for each of them. Then Lesha computes MEX of the obtained numbers.

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

Lesha understands that the problem is very interesting this time, but he doesn't know how to solve it. Help him and find the MEX of MEXes of all the subarrays!


-----Input-----

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

The next line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$) — the elements of the array.


-----Output-----

Print a single integer — the MEX of MEXes of all subarrays.


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

Output
3

Input
5
1 4 3 1 2

Output
6