meetforever/GRPO_CL huggingface dataset:
user: Natasha is planning an expedition to Mars for $n$ people. One of the important tasks is to provide food for each participant.

The warehouse has $m$ daily food packages. Each package has some food type $a_i$.

Each participant must eat exactly one food package each day. Due to extreme loads, each participant must eat the same food type throughout the expedition. Different participants may eat different (or the same) types of food.

Formally, for each participant $j$ Natasha should select his food type $b_j$ and each day $j$-th participant will eat one food package of type $b_j$. The values $b_j$ for different participants may be different.

What is the maximum possible number of days the expedition can last, following the requirements above?


-----Input-----

The first line contains two integers $n$ and $m$ ($1 \le n \le 100$, $1 \le m \le 100$) — the number of the expedition participants and the number of the daily food packages available.

The second line contains sequence of integers $a_1, a_2, \dots, a_m$ ($1 \le a_i \le 100$), where $a_i$ is the type of $i$-th food package.


-----Output-----

Print the single integer — the number of days the expedition can last. If it is not possible to plan the expedition for even one day, print 0.


-----Examples-----
Input
4 10
1 5 2 1 1 1 2 5 7 2

Output
2

Input
100 1
1

Output
0

Input
2 5
5 4 3 2 1

Output
1

Input
3 9
42 42 42 42 42 42 42 42 42

Output
3



-----Note-----

In the first example, Natasha can assign type $1$ food to the first participant, the same type $1$ to the second, type $5$ to the third and type $2$ to the fourth. In this case, the expedition can last for $2$ days, since each participant can get two food packages of his food type (there will be used $4$ packages of type $1$, two packages of type $2$ and two packages of type $5$).

In the second example, there are $100$ participants and only $1$ food package. In this case, the expedition can't last even $1$ day.
user: Takahashi is at an all-you-can-eat restaurant.
The restaurant offers N kinds of dishes. It takes A_i minutes to eat the i-th dish, whose deliciousness is B_i.
The restaurant has the following rules:
 - You can only order one dish at a time. The dish ordered will be immediately served and ready to eat.
 - You cannot order the same kind of dish more than once.
 - Until you finish eating the dish already served, you cannot order a new dish.
 - After T-0.5 minutes from the first order, you can no longer place a new order, but you can continue eating the dish already served.
Let Takahashi's happiness be the sum of the deliciousness of the dishes he eats in this restaurant.
What is the maximum possible happiness achieved by making optimal choices?

-----Constraints-----
 - 2 \leq N \leq 3000
 - 1 \leq T \leq 3000
 - 1 \leq A_i \leq 3000
 - 1 \leq B_i \leq 3000
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N T
A_1 B_1
:
A_N B_N

-----Output-----
Print the maximum possible happiness Takahashi can achieve.

-----Sample Input-----
2 60
10 10
100 100

-----Sample Output-----
110

By ordering the first and second dishes in this order, Takahashi's happiness will be 110.
Note that, if we manage to order a dish in time, we can spend any amount of time to eat it.
user: There is a knight - the chess piece - at the origin (0, 0) of a two-dimensional grid.
When the knight is at the square (i, j), it can be moved to either (i+1,j+2) or (i+2, j+1).
In how many ways can the knight reach the square (X, Y)?
Find the number of ways modulo 10^9 + 7.

-----Constraints-----
 - 1 \leq X \leq 10^6
 - 1 \leq Y \leq 10^6
 - All values in input are integers.

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

-----Output-----
Print the number of ways for the knight to reach (X, Y) from (0, 0), modulo 10^9 + 7.

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

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

There are two ways: (0,0) \to (1,2) \to (3,3) and (0,0) \to (2,1) \to (3,3).
user: Tonight is brain dinner night and all zombies will gather together to scarf down some delicious brains. The artful Heidi plans to crash the party, incognito, disguised as one of them. Her objective is to get away with at least one brain, so she can analyze the zombies' mindset back home and gain a strategic advantage.

They will be N guests tonight: N - 1 real zombies and a fake one, our Heidi. The living-dead love hierarchies as much as they love brains: each one has a unique rank in the range 1 to N - 1, and Heidi, who still appears slightly different from the others, is attributed the highest rank, N. Tonight there will be a chest with brains on display and every attendee sees how many there are. These will then be split among the attendees according to the following procedure:

The zombie of the highest rank makes a suggestion on who gets how many brains (every brain is an indivisible entity). A vote follows. If at least half of the attendees accept the offer, the brains are shared in the suggested way and the feast begins. But if majority is not reached, then the highest-ranked zombie is killed, and the next zombie in hierarchy has to make a suggestion. If he is killed too, then the third highest-ranked makes one, etc. (It's enough to have exactly half of the votes – in case of a tie, the vote of the highest-ranked alive zombie counts twice, and he will of course vote in favor of his own suggestion in order to stay alive.)

You should know that zombies are very greedy and sly, and they know this too – basically all zombie brains are alike. Consequently, a zombie will never accept an offer which is suboptimal for him. That is, if an offer is not strictly better than a potential later offer, he will vote against it. And make no mistake: while zombies may normally seem rather dull, tonight their intellects are perfect. Each zombie's priorities for tonight are, in descending order:   survive the event (they experienced death already once and know it is no fun),  get as many brains as possible. 

Heidi goes first and must make an offer which at least half of the attendees will accept, and which allocates at least one brain for Heidi herself.

What is the smallest number of brains that have to be in the chest for this to be possible?


-----Input-----

The only line of input contains one integer: N, the number of attendees (1 ≤ N ≤ 10^9).


-----Output-----

Output one integer: the smallest number of brains in the chest which allows Heidi to take one brain home.


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

Output
1

Input
4

Output
2



-----Note-----
user: There exists an island called Arpa’s land, some beautiful girls live there, as ugly ones do.

Mehrdad wants to become minister of Arpa’s land. Arpa has prepared an exam. Exam has only one question, given n, print the last digit of 1378^{n}. 

 [Image] 

Mehrdad has become quite confused and wants you to help him. Please help, although it's a naive cheat.


-----Input-----

The single line of input contains one integer n (0  ≤  n  ≤  10^9).


-----Output-----

Print single integer — the last digit of 1378^{n}.


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

Output
8
Input
2

Output
4


-----Note-----

In the first example, last digit of 1378^1 = 1378 is 8.

In the second example, last digit of 1378^2 = 1378·1378 = 1898884 is 4.
user: One day Vasya the Hipster decided to count how many socks he had. It turned out that he had a red socks and b blue socks.

According to the latest fashion, hipsters should wear the socks of different colors: a red one on the left foot, a blue one on the right foot.

Every day Vasya puts on new socks in the morning and throws them away before going to bed as he doesn't want to wash them.

Vasya wonders, what is the maximum number of days when he can dress fashionable and wear different socks, and after that, for how many days he can then wear the same socks until he either runs out of socks or cannot make a single pair from the socks he's got.

Can you help him?


-----Input-----

The single line of the input contains two positive integers a and b (1 ≤ a, b ≤ 100) — the number of red and blue socks that Vasya's got.


-----Output-----

Print two space-separated integers — the maximum number of days when Vasya can wear different socks and the number of days when he can wear the same socks until he either runs out of socks or cannot make a single pair from the socks he's got.

Keep in mind that at the end of the day Vasya throws away the socks that he's been wearing on that day.


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

Output
1 1

Input
2 3

Output
2 0

Input
7 3

Output
3 2



-----Note-----

In the first sample Vasya can first put on one pair of different socks, after that he has two red socks left to wear on the second day.
user: Luke Skywalker got locked up in a rubbish shredder between two presses. R2D2 is already working on his rescue, but Luke needs to stay alive as long as possible. For simplicity we will assume that everything happens on a straight line, the presses are initially at coordinates 0 and L, and they move towards each other with speed v_1 and v_2, respectively. Luke has width d and is able to choose any position between the presses. Luke dies as soon as the distance between the presses is less than his width. Your task is to determine for how long Luke can stay alive.


-----Input-----

The first line of the input contains four integers d, L, v_1, v_2 (1 ≤ d, L, v_1, v_2 ≤ 10 000, d < L) — Luke's width, the initial position of the second press and the speed of the first and second presses, respectively.


-----Output-----

Print a single real value — the maximum period of time Luke can stay alive for. Your answer will be considered correct if its absolute or relative error does not exceed 10^{ - 6}. 

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if $\frac{|a - b|}{\operatorname{max}(1, b)} \leq 10^{-6}$.


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

Output
1.00000000000000000000

Input
1 9 1 2

Output
2.66666666666666650000



-----Note-----

In the first sample Luke should stay exactly in the middle of the segment, that is at coordinates [2;4], as the presses move with the same speed.

In the second sample he needs to occupy the position $[ 2 \frac{2}{3} ; 3 \frac{2}{3} ]$. In this case both presses move to his edges at the same time.
user: These days Arkady works as an air traffic controller at a large airport. He controls a runway which is usually used for landings only. Thus, he has a schedule of planes that are landing in the nearest future, each landing lasts $1$ minute.

He was asked to insert one takeoff in the schedule. The takeoff takes $1$ minute itself, but for safety reasons there should be a time space between the takeoff and any landing of at least $s$ minutes from both sides.

Find the earliest time when Arkady can insert the takeoff.


-----Input-----

The first line of input contains two integers $n$ and $s$ ($1 \le n \le 100$, $1 \le s \le 60$) — the number of landings on the schedule and the minimum allowed time (in minutes) between a landing and a takeoff.

Each of next $n$ lines contains two integers $h$ and $m$ ($0 \le h \le 23$, $0 \le m \le 59$) — the time, in hours and minutes, when a plane will land, starting from current moment (i. e. the current time is $0$ $0$). These times are given in increasing order.


-----Output-----

Print two integers $h$ and $m$ — the hour and the minute from the current moment of the earliest time Arkady can insert the takeoff.


-----Examples-----
Input
6 60
0 0
1 20
3 21
5 0
19 30
23 40

Output
6 1

Input
16 50
0 30
1 20
3 0
4 30
6 10
7 50
9 30
11 10
12 50
14 30
16 10
17 50
19 30
21 10
22 50
23 59

Output
24 50

Input
3 17
0 30
1 0
12 0

Output
0 0



-----Note-----

In the first example note that there is not enough time between 1:20 and 3:21, because each landing and the takeoff take one minute.

In the second example there is no gaps in the schedule, so Arkady can only add takeoff after all landings. Note that it is possible that one should wait more than $24$ hours to insert the takeoff.

In the third example Arkady can insert the takeoff even between the first landing.
user: You're given an array $a$ of length $n$. You can perform the following operation on it as many times as you want:  Pick two integers $i$ and $j$ $(1 \le i,j \le n)$ such that $a_i+a_j$ is odd, then swap $a_i$ and $a_j$. 

What is lexicographically the smallest array you can obtain?

An array $x$ is lexicographically smaller than an array $y$ if there exists an index $i$ such that $x_i<y_i$, and $x_j=y_j$ for all $1 \le j < i$. Less formally, at the first index $i$ in which they differ, $x_i<y_i$


-----Input-----

The first line contains an integer $n$ ($1 \le n \le 10^5$) — the number of elements in the array $a$.

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


-----Output-----

The only line contains $n$ space-separated integers, the lexicographically smallest array you can obtain.


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

Output
1 4 7 
Input
2
1 1

Output
1 1 


-----Note-----

In the first example, we can swap $1$ and $4$ since $1+4=5$, which is odd.
user: Scrooge McDuck keeps his most treasured savings in a home safe with a combination lock. Each time he wants to put there the treasures that he's earned fair and square, he has to open the lock.

 [Image] 

The combination lock is represented by n rotating disks with digits from 0 to 9 written on them. Scrooge McDuck has to turn some disks so that the combination of digits on the disks forms a secret combination. In one move, he can rotate one disk one digit forwards or backwards. In particular, in one move he can go from digit 0 to digit 9 and vice versa. What minimum number of actions does he need for that?


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 1000) — the number of disks on the combination lock.

The second line contains a string of n digits — the original state of the disks.

The third line contains a string of n digits — Scrooge McDuck's combination that opens the lock.


-----Output-----

Print a single integer — the minimum number of moves Scrooge McDuck needs to open the lock.


-----Examples-----
Input
5
82195
64723

Output
13



-----Note-----

In the sample he needs 13 moves:

  1 disk: $8 \rightarrow 7 \rightarrow 6$  2 disk: $2 \rightarrow 3 \rightarrow 4$  3 disk: $1 \rightarrow 0 \rightarrow 9 \rightarrow 8 \rightarrow 7$  4 disk: $9 \rightarrow 0 \rightarrow 1 \rightarrow 2$  5 disk: $5 \rightarrow 4 \rightarrow 3$
user: A permutation is a sequence of integers p_1, p_2, ..., p_{n}, consisting of n distinct positive integers, each of them doesn't exceed n. Let's denote the i-th element of permutation p as p_{i}. We'll call number n the size of permutation p_1, p_2, ..., p_{n}.

Nickolas adores permutations. He likes some permutations more than the others. He calls such permutations perfect. A perfect permutation is such permutation p that for any i (1 ≤ i ≤ n) (n is the permutation size) the following equations hold p_{p}_{i} = i and p_{i} ≠ i. Nickolas asks you to print any perfect permutation of size n for the given n.


-----Input-----

A single line contains a single integer n (1 ≤ n ≤ 100) — the permutation size.


-----Output-----

If a perfect permutation of size n doesn't exist, print a single integer -1. Otherwise print n distinct integers from 1 to n, p_1, p_2, ..., p_{n} — permutation p, that is perfect. Separate printed numbers by whitespaces.


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

Output
-1

Input
2

Output
2 1 

Input
4

Output
2 1 4 3
user: You are playing the following game. There are n points on a plane. They are the vertices of a regular n-polygon. Points are labeled with integer numbers from 1 to n. Each pair of distinct points is connected by a diagonal, which is colored in one of 26 colors. Points are denoted by lowercase English letters. There are three stones positioned on three distinct vertices. All stones are the same. With one move you can move the stone to another free vertex along some diagonal. The color of this diagonal must be the same as the color of the diagonal, connecting another two stones. 

Your goal is to move stones in such way that the only vertices occupied by stones are 1, 2 and 3. You must achieve such position using minimal number of moves. Write a program which plays this game in an optimal way.


-----Input-----

In the first line there is one integer n (3 ≤ n ≤ 70) — the number of points. In the second line there are three space-separated integer from 1 to n — numbers of vertices, where stones are initially located.

Each of the following n lines contains n symbols — the matrix denoting the colors of the diagonals. Colors are denoted by lowercase English letters. The symbol j of line i denotes the color of diagonal between points i and j. Matrix is symmetric, so j-th symbol of i-th line is equal to i-th symbol of j-th line. Main diagonal is filled with '*' symbols because there is no diagonal, connecting point to itself.


-----Output-----

If there is no way to put stones on vertices 1, 2 and 3, print -1 on a single line. Otherwise, on the first line print minimal required number of moves and in the next lines print the description of each move, one move per line. To describe a move print two integers. The point from which to remove the stone, and the point to which move the stone. If there are several optimal solutions, print any of them.


-----Examples-----
Input
4
2 3 4
*aba
a*ab
ba*b
abb*

Output
1
4 1

Input
4
2 3 4
*abc
a*ab
ba*b
cbb*

Output
-1



-----Note-----

In the first example we can move stone from point 4 to point 1 because this points are connected by the diagonal of color 'a' and the diagonal connection point 2 and 3, where the other stones are located, are connected by the diagonal of the same color. After that stones will be on the points 1, 2 and 3.
user: Consider the function p(x), where x is an array of m integers, which returns an array y consisting of m + 1 integers such that y_{i} is equal to the sum of first i elements of array x (0 ≤ i ≤ m).

You have an infinite sequence of arrays A^0, A^1, A^2..., where A^0 is given in the input, and for each i ≥ 1 A^{i} = p(A^{i} - 1). Also you have a positive integer k. You have to find minimum possible i such that A^{i} contains a number which is larger or equal than k.


-----Input-----

The first line contains two integers n and k (2 ≤ n ≤ 200000, 1 ≤ k ≤ 10^18). n is the size of array A^0.

The second line contains n integers A^0_0, A^0_1... A^0_{n} - 1 — the elements of A^0 (0 ≤ A^0_{i} ≤ 10^9). At least two elements of A^0 are positive.


-----Output-----

Print the minimum i such that A^{i} contains a number which is larger or equal than k.


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

Output
1

Input
3 6
1 1 1

Output
2

Input
3 1
1 0 1

Output
0
user: There are n problems prepared for the next Codeforces round. They are arranged in ascending order by their difficulty, and no two problems have the same difficulty. Moreover, there are m pairs of similar problems. Authors want to split problems between two division according to the following rules:   Problemset of each division should be non-empty.  Each problem should be used in exactly one division (yes, it is unusual requirement).  Each problem used in division 1 should be harder than any problem used in division 2.  If two problems are similar, they should be used in different divisions. 

Your goal is count the number of ways to split problem between two divisions and satisfy all the rules. Two ways to split problems are considered to be different if there is at least one problem that belongs to division 1 in one of them and to division 2 in the other.

Note, that the relation of similarity is not transitive. That is, if problem i is similar to problem j and problem j is similar to problem k, it doesn't follow that i is similar to k.


-----Input-----

The first line of the input contains two integers n and m (2 ≤ n ≤ 100 000, 0 ≤ m ≤ 100 000) — the number of problems prepared for the round and the number of pairs of similar problems, respectively.

Each of the following m lines contains a pair of similar problems u_{i} and v_{i} (1 ≤ u_{i}, v_{i} ≤ n, u_{i} ≠ v_{i}). It's guaranteed, that no pair of problems meets twice in the input.


-----Output-----

Print one integer — the number of ways to split problems in two divisions.


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

Output
2

Input
3 3
1 2
2 3
1 3

Output
0

Input
3 2
3 1
3 2

Output
1



-----Note-----

In the first sample, problems 1 and 2 should be used in division 2, while problems 4 and 5 in division 1. Problem 3 may be used either in division 1 or in division 2.

In the second sample, all pairs of problems are similar and there is no way to split problem between two divisions without breaking any rules.

Third sample reminds you that the similarity relation is not transitive. Problem 3 is similar to both 1 and 2, but 1 is not similar to 2, so they may be used together.
user: The math faculty of Berland State University has suffered the sudden drop in the math skills of enrolling students. This year the highest grade on the entrance math test was 8. Out of 100! Thus, the decision was made to make the test easier.

Future students will be asked just a single question. They are given a sequence of integer numbers $a_1, a_2, \dots, a_n$, each number is from $1$ to $3$ and $a_i \ne a_{i + 1}$ for each valid $i$. The $i$-th number represents a type of the $i$-th figure:

  circle;  isosceles triangle with the length of height equal to the length of base;  square. 

The figures of the given sequence are placed somewhere on a Cartesian plane in such a way that:

  $(i + 1)$-th figure is inscribed into the $i$-th one;  each triangle base is parallel to OX;  the triangle is oriented in such a way that the vertex opposite to its base is at the top;  each square sides are parallel to the axes;  for each $i$ from $2$ to $n$ figure $i$ has the maximum possible length of side for triangle and square and maximum radius for circle. 

Note that the construction is unique for some fixed position and size of just the first figure.

The task is to calculate the number of distinct points (not necessarily with integer coordinates) where figures touch. The trick is, however, that the number is sometimes infinite. But that won't make the task difficult for you, will it?

So can you pass the math test and enroll into Berland State University?


-----Input-----

The first line contains a single integer $n$ ($2 \le n \le 100$) — the number of figures.

The second line contains $n$ integer numbers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 3$, $a_i \ne a_{i + 1}$) — types of the figures.


-----Output-----

The first line should contain either the word "Infinite" if the number of distinct points where figures touch is infinite or "Finite" otherwise.

If the number is finite than print it in the second line. It's guaranteed that the number fits into 32-bit integer type.


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

Output
Finite
7

Input
3
1 2 3

Output
Infinite



-----Note-----

Here are the glorious pictures for the examples. Note that the triangle is not equilateral but just isosceles with the length of height equal to the length of base. Thus it fits into a square in a unique way.

The distinct points where figures touch are marked red.

In the second example the triangle and the square touch each other for the whole segment, it contains infinite number of points.

 [Image]