meetforever/GRPO_CL huggingface dataset:
user: There are n students who have taken part in an olympiad. Now it's time to award the students.

Some of them will receive diplomas, some wiil get certificates, and others won't receive anything. Students with diplomas and certificates are called winners. But there are some rules of counting the number of diplomas and certificates. The number of certificates must be exactly k times greater than the number of diplomas. The number of winners must not be greater than half of the number of all students (i.e. not be greater than half of n). It's possible that there are no winners.

You have to identify the maximum possible number of winners, according to these rules. Also for this case you have to calculate the number of students with diplomas, the number of students with certificates and the number of students who are not winners.


-----Input-----

The first (and the only) line of input contains two integers n and k (1 ≤ n, k ≤ 10^12), where n is the number of students and k is the ratio between the number of certificates and the number of diplomas.


-----Output-----

Output three numbers: the number of students with diplomas, the number of students with certificates and the number of students who are not winners in case when the number of winners is maximum possible.

It's possible that there are no winners.


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

Output
3 6 9

Input
9 10

Output
0 0 9

Input
1000000000000 5

Output
83333333333 416666666665 500000000002

Input
1000000000000 499999999999

Output
1 499999999999 500000000000
user: Let quasi-palindromic number be such number that adding some leading zeros (possible none) to it produces a palindromic string. 

String t is called a palindrome, if it reads the same from left to right and from right to left.

For example, numbers 131 and 2010200 are quasi-palindromic, they can be transformed to strings "131" and "002010200", respectively, which are palindromes.

You are given some integer number x. Check if it's a quasi-palindromic number.


-----Input-----

The first line contains one integer number x (1 ≤ x ≤ 10^9). This number is given without any leading zeroes.


-----Output-----

Print "YES" if number x is quasi-palindromic. Otherwise, print "NO" (without quotes).


-----Examples-----
Input
131

Output
YES

Input
320

Output
NO

Input
2010200

Output
YES
user: Imp is in a magic forest, where xorangles grow (wut?)

 [Image] 

A xorangle of order n is such a non-degenerate triangle, that lengths of its sides are integers not exceeding n, and the xor-sum of the lengths is equal to zero. Imp has to count the number of distinct xorangles of order n to get out of the forest. 

Formally, for a given integer n you have to find the number of such triples (a, b, c), that:

  1 ≤ a ≤ b ≤ c ≤ n;  $a \oplus b \oplus c = 0$, where $x \oplus y$ denotes the bitwise xor of integers x and y.  (a, b, c) form a non-degenerate (with strictly positive area) triangle. 


-----Input-----

The only line contains a single integer n (1 ≤ n ≤ 2500).


-----Output-----

Print the number of xorangles of order n.


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

Output
1

Input
10

Output
2



-----Note-----

The only xorangle in the first sample is (3, 5, 6).
user: You play a computer game. Your character stands on some level of a multilevel ice cave. In order to move on forward, you need to descend one level lower and the only way to do this is to fall through the ice.

The level of the cave where you are is a rectangular square grid of n rows and m columns. Each cell consists either from intact or from cracked ice. From each cell you can move to cells that are side-adjacent with yours (due to some limitations of the game engine you cannot make jumps on the same place, i.e. jump from a cell to itself). If you move to the cell with cracked ice, then your character falls down through it and if you move to the cell with intact ice, then the ice on this cell becomes cracked.

Let's number the rows with integers from 1 to n from top to bottom and the columns with integers from 1 to m from left to right. Let's denote a cell on the intersection of the r-th row and the c-th column as (r, c). 

You are staying in the cell (r_1, c_1) and this cell is cracked because you've just fallen here from a higher level. You need to fall down through the cell (r_2, c_2) since the exit to the next level is there. Can you do this?


-----Input-----

The first line contains two integers, n and m (1 ≤ n, m ≤ 500) — the number of rows and columns in the cave description.

Each of the next n lines describes the initial state of the level of the cave, each line consists of m characters "." (that is, intact ice) and "X" (cracked ice).

The next line contains two integers, r_1 and c_1 (1 ≤ r_1 ≤ n, 1 ≤ c_1 ≤ m) — your initial coordinates. It is guaranteed that the description of the cave contains character 'X' in cell (r_1, c_1), that is, the ice on the starting cell is initially cracked.

The next line contains two integers r_2 and c_2 (1 ≤ r_2 ≤ n, 1 ≤ c_2 ≤ m) — the coordinates of the cell through which you need to fall. The final cell may coincide with the starting one.


-----Output-----

If you can reach the destination, print 'YES', otherwise print 'NO'.


-----Examples-----
Input
4 6
X...XX
...XX.
.X..X.
......
1 6
2 2

Output
YES

Input
5 4
.X..
...X
X.X.
....
.XX.
5 3
1 1

Output
NO

Input
4 7
..X.XX.
.XX..X.
X...X..
X......
2 2
1 6

Output
YES



-----Note-----

In the first sample test one possible path is:

[Image]

After the first visit of cell (2, 2) the ice on it cracks and when you step there for the second time, your character falls through the ice as intended.
user: There are N islands lining up from west to east, connected by N-1 bridges.
The i-th bridge connects the i-th island from the west and the (i+1)-th island from the west.
One day, disputes took place between some islands, and there were M requests from the inhabitants of the islands:
Request i: A dispute took place between the a_i-th island from the west and the b_i-th island from the west. Please make traveling between these islands with bridges impossible.
You decided to remove some bridges to meet all these M requests.
Find the minimum number of bridges that must be removed.

-----Constraints-----
 - All values in input are integers.
 - 2 \leq N \leq 10^5
 - 1 \leq M \leq 10^5
 - 1 \leq a_i < b_i \leq N
 - All pairs (a_i, b_i) are distinct.

-----Input-----
Input is given from Standard Input in the following format:
N M
a_1 b_1
a_2 b_2
:
a_M b_M

-----Output-----
Print the minimum number of bridges that must be removed.

-----Sample Input-----
5 2
1 4
2 5

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

The requests can be met by removing the bridge connecting the second and third islands from the west.
user: Vasya has become interested in wrestling. In wrestling wrestlers use techniques for which they are awarded points by judges. The wrestler who gets the most points wins.

When the numbers of points of both wrestlers are equal, the wrestler whose sequence of points is lexicographically greater, wins.

If the sequences of the awarded points coincide, the wrestler who performed the last technique wins. Your task is to determine which wrestler won.


-----Input-----

The first line contains number n — the number of techniques that the wrestlers have used (1 ≤ n ≤ 2·10^5). 

The following n lines contain integer numbers a_{i} (|a_{i}| ≤ 10^9, a_{i} ≠ 0). If a_{i} is positive, that means that the first wrestler performed the technique that was awarded with a_{i} points. And if a_{i} is negative, that means that the second wrestler performed the technique that was awarded with ( - a_{i}) points.

The techniques are given in chronological order.


-----Output-----

If the first wrestler wins, print string "first", otherwise print "second"


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

Output
second

Input
3
-1
-2
3

Output
first

Input
2
4
-4

Output
second



-----Note-----

Sequence x  =  x_1x_2... x_{|}x| is lexicographically larger than sequence y  =  y_1y_2... y_{|}y|, if either |x|  >  |y| and x_1  =  y_1,  x_2  =  y_2, ... ,  x_{|}y|  =  y_{|}y|, or there is such number r (r  <  |x|, r  <  |y|), that x_1  =  y_1,  x_2  =  y_2,  ... ,  x_{r}  =  y_{r} and x_{r}  +  1  >  y_{r}  +  1.

We use notation |a| to denote length of sequence a.
user: The programming competition season has already started and it's time to train for ICPC. Sereja coaches his teams for a number of year and he knows that to get ready for the training session it's not enough to prepare only problems and editorial. As the training sessions lasts for several hours, teams become hungry. Thus, Sereja orders a number of pizzas so they can eat right after the end of the competition.

Teams plan to train for n times during n consecutive days. During the training session Sereja orders exactly one pizza for each team that is present this day. He already knows that there will be a_{i} teams on the i-th day.

There are two types of discounts in Sereja's favourite pizzeria. The first discount works if one buys two pizzas at one day, while the second is a coupon that allows to buy one pizza during two consecutive days (two pizzas in total).

As Sereja orders really a lot of pizza at this place, he is the golden client and can use the unlimited number of discounts and coupons of any type at any days.

Sereja wants to order exactly a_{i} pizzas on the i-th day while using only discounts and coupons. Note, that he will never buy more pizzas than he need for this particular day. Help him determine, whether he can buy the proper amount of pizzas each day if he is allowed to use only coupons and discounts. Note, that it's also prohibited to have any active coupons after the end of the day n.


-----Input-----

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

The second line contains n integers a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ 10 000) — the number of teams that will be present on each of the days.


-----Output-----

If there is a way to order pizzas using only coupons and discounts and do not buy any extra pizzas on any of the days, then print "YES" (without quotes) in the only line of output. Otherwise, print "NO" (without quotes).


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

Output
YES

Input
3
1 0 1

Output
NO



-----Note-----

In the first sample, Sereja can use one coupon to buy one pizza on the first and the second days, one coupon to buy pizza on the second and the third days and one discount to buy pizzas on the fourth days. This is the only way to order pizzas for this sample.

In the second sample, Sereja can't use neither the coupon nor the discount without ordering an extra pizza. Note, that it's possible that there will be no teams attending the training sessions on some days.
user: You are given a string $s$ consisting of $n$ lowercase Latin letters. $n$ is even.

For each position $i$ ($1 \le i \le n$) in string $s$ you are required to change the letter on this position either to the previous letter in alphabetic order or to the next one (letters 'a' and 'z' have only one of these options). Letter in every position must be changed exactly once.

For example, letter 'p' should be changed either to 'o' or to 'q', letter 'a' should be changed to 'b' and letter 'z' should be changed to 'y'.

That way string "codeforces", for example, can be changed to "dpedepqbft" ('c' $\rightarrow$ 'd', 'o' $\rightarrow$ 'p', 'd' $\rightarrow$ 'e', 'e' $\rightarrow$ 'd', 'f' $\rightarrow$ 'e', 'o' $\rightarrow$ 'p', 'r' $\rightarrow$ 'q', 'c' $\rightarrow$ 'b', 'e' $\rightarrow$ 'f', 's' $\rightarrow$ 't').

String $s$ is called a palindrome if it reads the same from left to right and from right to left. For example, strings "abba" and "zz" are palindromes and strings "abca" and "zy" are not.

Your goal is to check if it's possible to make string $s$ a palindrome by applying the aforementioned changes to every position. Print "YES" if string $s$ can be transformed to a palindrome and "NO" otherwise.

Each testcase contains several strings, for each of them you are required to solve the problem separately.


-----Input-----

The first line contains a single integer $T$ ($1 \le T \le 50$) — the number of strings in a testcase.

Then $2T$ lines follow — lines $(2i - 1)$ and $2i$ of them describe the $i$-th string. The first line of the pair contains a single integer $n$ ($2 \le n \le 100$, $n$ is even) — the length of the corresponding string. The second line of the pair contains a string $s$, consisting of $n$ lowercase Latin letters.


-----Output-----

Print $T$ lines. The $i$-th line should contain the answer to the $i$-th string of the input. Print "YES" if it's possible to make the $i$-th string a palindrome by applying the aforementioned changes to every position. Print "NO" otherwise.


-----Example-----
Input
5
6
abccba
2
cf
4
adfa
8
abaazaba
2
ml

Output
YES
NO
YES
NO
NO



-----Note-----

The first string of the example can be changed to "bcbbcb", two leftmost letters and two rightmost letters got changed to the next letters, two middle letters got changed to the previous letters.

The second string can be changed to "be", "bg", "de", "dg", but none of these resulting strings are palindromes.

The third string can be changed to "beeb" which is a palindrome.

The fifth string can be changed to "lk", "lm", "nk", "nm", but none of these resulting strings are palindromes. Also note that no letter can remain the same, so you can't obtain strings "ll" or "mm".
user: Marina loves strings of the same length and Vasya loves when there is a third string, different from them in exactly t characters. Help Vasya find at least one such string.

More formally, you are given two strings s_1, s_2 of length n and number t. Let's denote as f(a, b) the number of characters in which strings a and b are different. Then your task will be to find any string s_3 of length n, such that f(s_1, s_3) = f(s_2, s_3) = t. If there is no such string, print  - 1.


-----Input-----

The first line contains two integers n and t (1 ≤ n ≤ 10^5, 0 ≤ t ≤ n).

The second line contains string s_1 of length n, consisting of lowercase English letters.

The third line contain string s_2 of length n, consisting of lowercase English letters.


-----Output-----

Print a string of length n, differing from string s_1 and from s_2 in exactly t characters. Your string should consist only from lowercase English letters. If such string doesn't exist, print -1.


-----Examples-----
Input
3 2
abc
xyc

Output
ayd
Input
1 0
c
b

Output
-1
user: It's hard times now. Today Petya needs to score 100 points on Informatics exam. The tasks seem easy to Petya, but he thinks he lacks time to finish them all, so he asks you to help with one..

There is a glob pattern in the statements (a string consisting of lowercase English letters, characters "?" and "*"). It is known that character "*" occurs no more than once in the pattern.

Also, n query strings are given, it is required to determine for each of them if the pattern matches it or not.

Everything seemed easy to Petya, but then he discovered that the special pattern characters differ from their usual meaning.

A pattern matches a string if it is possible to replace each character "?" with one good lowercase English letter, and the character "*" (if there is one) with any, including empty, string of bad lowercase English letters, so that the resulting string is the same as the given string.

The good letters are given to Petya. All the others are bad.


-----Input-----

The first line contains a string with length from 1 to 26 consisting of distinct lowercase English letters. These letters are good letters, all the others are bad.

The second line contains the pattern — a string s of lowercase English letters, characters "?" and "*" (1 ≤ |s| ≤ 10^5). It is guaranteed that character "*" occurs in s no more than once.

The third line contains integer n (1 ≤ n ≤ 10^5) — the number of query strings.

n lines follow, each of them contains single non-empty string consisting of lowercase English letters — a query string.

It is guaranteed that the total length of all query strings is not greater than 10^5.


-----Output-----

Print n lines: in the i-th of them print "YES" if the pattern matches the i-th query string, and "NO" otherwise.

You can choose the case (lower or upper) for each letter arbitrary.


-----Examples-----
Input
ab
a?a
2
aaa
aab

Output
YES
NO

Input
abc
a?a?a*
4
abacaba
abaca
apapa
aaaaax

Output
NO
YES
NO
YES



-----Note-----

In the first example we can replace "?" with good letters "a" and "b", so we can see that the answer for the first query is "YES", and the answer for the second query is "NO", because we can't match the third letter.

Explanation of the second example.   The first query: "NO", because character "*" can be replaced with a string of bad letters only, but the only way to match the query string is to replace it with the string "ba", in which both letters are good.  The second query: "YES", because characters "?" can be replaced with corresponding good letters, and character "*" can be replaced with empty string, and the strings will coincide.  The third query: "NO", because characters "?" can't be replaced with bad letters.  The fourth query: "YES", because characters "?" can be replaced with good letters "a", and character "*" can be replaced with a string of bad letters "x".
user: Vanya is managed to enter his favourite site Codehorses. Vanya uses n distinct passwords for sites at all, however he can't remember which one exactly he specified during Codehorses registration.

Vanya will enter passwords in order of non-decreasing their lengths, and he will enter passwords of same length in arbitrary order. Just when Vanya will have entered the correct password, he is immediately authorized on the site. Vanya will not enter any password twice.

Entering any passwords takes one second for Vanya. But if Vanya will enter wrong password k times, then he is able to make the next try only 5 seconds after that. Vanya makes each try immediately, that is, at each moment when Vanya is able to enter password, he is doing that.

Determine how many seconds will Vanya need to enter Codehorses in the best case for him (if he spends minimum possible number of second) and in the worst case (if he spends maximum possible amount of seconds).


-----Input-----

The first line of the input contains two integers n and k (1 ≤ n, k ≤ 100) — the number of Vanya's passwords and the number of failed tries, after which the access to the site is blocked for 5 seconds.

The next n lines contains passwords, one per line — pairwise distinct non-empty strings consisting of latin letters and digits. Each password length does not exceed 100 characters.

The last line of the input contains the Vanya's Codehorses password. It is guaranteed that the Vanya's Codehorses password is equal to some of his n passwords.


-----Output-----

Print two integers — time (in seconds), Vanya needs to be authorized to Codehorses in the best case for him and in the worst case respectively.


-----Examples-----
Input
5 2
cba
abc
bb1
abC
ABC
abc

Output
1 15

Input
4 100
11
22
1
2
22

Output
3 4



-----Note-----

Consider the first sample case. As soon as all passwords have the same length, Vanya can enter the right password at the first try as well as at the last try. If he enters it at the first try, he spends exactly 1 second. Thus in the best case the answer is 1. If, at the other hand, he enters it at the last try, he enters another 4 passwords before. He spends 2 seconds to enter first 2 passwords, then he waits 5 seconds as soon as he made 2 wrong tries. Then he spends 2 more seconds to enter 2 wrong passwords, again waits 5 seconds and, finally, enters the correct password spending 1 more second. In summary in the worst case he is able to be authorized in 15 seconds.

Consider the second sample case. There is no way of entering passwords and get the access to the site blocked. As soon as the required password has length of 2, Vanya enters all passwords of length 1 anyway, spending 2 seconds for that. Then, in the best case, he immediately enters the correct password and the answer for the best case is 3, but in the worst case he enters wrong password of length 2 and only then the right one, spending 4 seconds at all.
user: Leha somehow found an array consisting of n integers. Looking at it, he came up with a task. Two players play the game on the array. Players move one by one. The first player can choose for his move a subsegment of non-zero length with an odd sum of numbers and remove it from the array, after that the remaining parts are glued together into one array and the game continues. The second player can choose a subsegment of non-zero length with an even sum and remove it. Loses the one who can not make a move. Who will win if both play optimally?


-----Input-----

First line of input data contains single integer n (1 ≤ n ≤ 10^6) — length of the array.

Next line contains n integers a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ 10^9).


-----Output-----

Output answer in single line. "First", if first player wins, and "Second" otherwise (without quotes).


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

Output
First

Input
2
2 2

Output
Second



-----Note-----

In first sample first player remove whole array in one move and win.

In second sample first player can't make a move and lose.
user: A big company decided to launch a new series of rectangular displays, and decided that the display must have exactly n pixels. 

Your task is to determine the size of the rectangular display — the number of lines (rows) of pixels a and the number of columns of pixels b, so that:

  there are exactly n pixels on the display;  the number of rows does not exceed the number of columns, it means a ≤ b;  the difference b - a is as small as possible. 


-----Input-----

The first line contains the positive integer n (1 ≤ n ≤ 10^6) — the number of pixels display should have.


-----Output-----

Print two integers — the number of rows and columns on the display. 


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

Output
2 4

Input
64

Output
8 8

Input
5

Output
1 5

Input
999999

Output
999 1001



-----Note-----

In the first example the minimum possible difference equals 2, so on the display should be 2 rows of 4 pixels.

In the second example the minimum possible difference equals 0, so on the display should be 8 rows of 8 pixels.

In the third example the minimum possible difference equals 4, so on the display should be 1 row of 5 pixels.