meetforever/GRPO_CL huggingface dataset:
user: Innocentius has a problem — his computer monitor has broken. Now some of the pixels are "dead", that is, they are always black. As consequence, Innocentius can't play the usual computer games. He is recently playing the following game with his younger brother Polycarpus.

Innocentius is touch-typing a program that paints a white square one-pixel wide frame on the black screen. As the monitor is broken, some pixels that should be white remain black. Polycarpus should look at what the program displayed on the screen and guess the position and size of the frame Innocentius has painted. Polycarpus doesn't like the game but Innocentius persuaded brother to play as "the game is good for the imagination and attention".

Help Polycarpus, automatize his part in the gaming process. Write the code that finds such possible square frame that:  the frame's width is 1 pixel,  the frame doesn't go beyond the borders of the screen,  all white pixels of the monitor are located on the frame,  of all frames that satisfy the previous three conditions, the required frame must have the smallest size. 

Formally, a square frame is represented by such pixels of the solid square, that are on the square's border, that is, are not fully surrounded by the other pixels of the square. For example, if the frame's size is d = 3, then it consists of 8 pixels, if its size is d = 2, then it contains 4 pixels and if d = 1, then the frame is reduced to a single pixel.


-----Input-----

The first line contains the resolution of the monitor as a pair of integers n, m (1 ≤ n, m ≤ 2000). The next n lines contain exactly m characters each — the state of the monitor pixels at the moment of the game. Character "." (period, ASCII code 46) corresponds to the black pixel, and character "w" (lowercase English letter w) corresponds to the white pixel. It is guaranteed that at least one pixel of the monitor is white.


-----Output-----

Print the monitor screen. Represent the sought frame by characters "+" (the "plus" character). The pixels that has become white during the game mustn't be changed. Print them as "w". If there are multiple possible ways to position the frame of the minimum size, print any of them.

If the required frame doesn't exist, then print a single line containing number -1.


-----Examples-----
Input
4 8
..w..w..
........
........
..w..w..

Output
..w++w..
..+..+..
..+..+..
..w++w..

Input
5 6
......
.w....
......
..w...
......

Output
......
+w+...
+.+...
++w...
......

Input
2 4
....
.w..

Output
....
.w..

Input
2 6
w..w.w
...w..

Output
-1



-----Note-----

In the first sample the required size of the optimal frame equals 4. In the second sample the size of the optimal frame equals 3. In the third sample, the size of the optimal frame is 1. In the fourth sample, the required frame doesn't exist.
user: Vasya has n burles. One bottle of Ber-Cola costs a burles and one Bars bar costs b burles. He can buy any non-negative integer number of bottles of Ber-Cola and any non-negative integer number of Bars bars.

Find out if it's possible to buy some amount of bottles of Ber-Cola and Bars bars and spend exactly n burles.

In other words, you should find two non-negative integers x and y such that Vasya can buy x bottles of Ber-Cola and y Bars bars and x·a + y·b = n or tell that it's impossible.


-----Input-----

First line contains single integer n (1 ≤ n ≤ 10 000 000) — amount of money, that Vasya has.

Second line contains single integer a (1 ≤ a ≤ 10 000 000) — cost of one bottle of Ber-Cola.

Third line contains single integer b (1 ≤ b ≤ 10 000 000) — cost of one Bars bar.


-----Output-----

If Vasya can't buy Bars and Ber-Cola in such a way to spend exactly n burles print «NO» (without quotes).

Otherwise in first line print «YES» (without quotes). In second line print two non-negative integers x and y — number of bottles of Ber-Cola and number of Bars bars Vasya should buy in order to spend exactly n burles, i.e. x·a + y·b = n. If there are multiple answers print any of them.

Any of numbers x and y can be equal 0.


-----Examples-----
Input
7
2
3

Output
YES
2 1

Input
100
25
10

Output
YES
0 10

Input
15
4
8

Output
NO

Input
9960594
2551
2557

Output
YES
1951 1949



-----Note-----

In first example Vasya can buy two bottles of Ber-Cola and one Bars bar. He will spend exactly 2·2 + 1·3 = 7 burles.

In second example Vasya can spend exactly n burles multiple ways:   buy two bottles of Ber-Cola and five Bars bars;  buy four bottles of Ber-Cola and don't buy Bars bars;  don't buy Ber-Cola and buy 10 Bars bars. 

In third example it's impossible to but Ber-Cola and Bars bars in order to spend exactly n burles.
user: Today Tavas got his test result as an integer score and he wants to share it with his girlfriend, Nafas.

His phone operating system is Tavdroid, and its keyboard doesn't have any digits! He wants to share his score with Nafas via text, so he has no choice but to send this number using words. [Image] 

He ate coffee mix without water again, so right now he's really messed up and can't think.

Your task is to help him by telling him what to type.


-----Input-----

The first and only line of input contains an integer s (0 ≤ s ≤ 99), Tavas's score. 


-----Output-----

In the first and only line of output, print a single string consisting only from English lowercase letters and hyphens ('-'). Do not use spaces.


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

Output
six

Input
99

Output
ninety-nine

Input
20

Output
twenty



-----Note-----

You can find all you need to know about English numerals in http://en.wikipedia.org/wiki/English_numerals .
user: JATC and his friend Giraffe are currently in their room, solving some problems. Giraffe has written on the board an array $a_1$, $a_2$, ..., $a_n$ of integers, such that $1 \le a_1 < a_2 < \ldots < a_n \le 10^3$, and then went to the bathroom.

JATC decided to prank his friend by erasing some consecutive elements in the array. Since he doesn't want for the prank to go too far, he will only erase in a way, such that Giraffe can still restore the array using the information from the remaining elements. Because Giraffe has created the array, he's also aware that it's an increasing array and all the elements are integers in the range $[1, 10^3]$.

JATC wonders what is the greatest number of elements he can erase?


-----Input-----

The first line of the input contains a single integer $n$ ($1 \le n \le 100$) — the number of elements in the array.

The second line of the input contains $n$ integers $a_i$ ($1 \le a_1<a_2<\dots<a_n \le 10^3$) — the array written by Giraffe.


-----Output-----

Print a single integer — the maximum number of consecutive elements in the array that JATC can erase.

If it is impossible to erase even a single element, print $0$.


-----Examples-----
Input
6
1 3 4 5 6 9

Output
2
Input
3
998 999 1000

Output
2
Input
5
1 2 3 4 5

Output
4


-----Note-----

In the first example, JATC can erase the third and fourth elements, leaving the array $[1, 3, \_, \_, 6, 9]$. As you can see, there is only one way to fill in the blanks.

In the second example, JATC can erase the second and the third elements. The array will become $[998, \_, \_]$. Because all the elements are less than or equal to $1000$, the array is still can be restored. Note, that he can't erase the first $2$ elements.

In the third example, JATC can erase the first $4$ elements. Since all the elements are greater than or equal to $1$, Giraffe can still restore the array. Note, that he can't erase the last $4$ elements.
user: Polycarp has created his own training plan to prepare for the programming contests. He will train for $n$ days, all days are numbered from $1$ to $n$, beginning from the first.

On the $i$-th day Polycarp will necessarily solve $a_i$ problems. One evening Polycarp plans to celebrate the equator. He will celebrate it on the first evening of such a day that from the beginning of the training and to this day inclusive he will solve half or more of all the problems.

Determine the index of day when Polycarp will celebrate the equator.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 200\,000$) — the number of days to prepare for the programming contests.

The second line contains a sequence $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10\,000$), where $a_i$ equals to the number of problems, which Polycarp will solve on the $i$-th day.


-----Output-----

Print the index of the day when Polycarp will celebrate the equator.


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

Output
2

Input
6
2 2 2 2 2 2

Output
3



-----Note-----

In the first example Polycarp will celebrate the equator on the evening of the second day, because up to this day (inclusive) he will solve $4$ out of $7$ scheduled problems on four days of the training.

In the second example Polycarp will celebrate the equator on the evening of the third day, because up to this day (inclusive) he will solve $6$ out of $12$ scheduled problems on six days of the training.
user: You stumbled upon a new kind of chess puzzles. The chessboard you are given is not necesserily $8 \times 8$, but it still is $N \times N$. Each square has some number written on it, all the numbers are from $1$ to $N^2$ and all the numbers are pairwise distinct. The $j$-th square in the $i$-th row has a number $A_{ij}$ written on it.

In your chess set you have only three pieces: a knight, a bishop and a rook. At first, you put one of them on the square with the number $1$ (you can choose which one). Then you want to reach square $2$ (possibly passing through some other squares in process), then square $3$ and so on until you reach square $N^2$. In one step you are allowed to either make a valid move with the current piece or replace it with some other piece. Each square can be visited arbitrary number of times.

A knight can move to a square that is two squares away horizontally and one square vertically, or two squares vertically and one square horizontally. A bishop moves diagonally. A rook moves horizontally or vertically. The move should be performed to a different square from the one a piece is currently standing on.

You want to minimize the number of steps of the whole traversal. Among all the paths to have the same number of steps you want to choose the one with the lowest number of piece replacements.

What is the path you should take to satisfy all conditions?


-----Input-----

The first line contains a single integer $N$ ($3 \le N \le 10$) — the size of the chessboard.

Each of the next $N$ lines contains $N$ integers $A_{i1}, A_{i2}, \dots, A_{iN}$ ($1 \le A_{ij} \le N^2$) — the numbers written on the squares of the $i$-th row of the board.

It is guaranteed that all $A_{ij}$ are pairwise distinct.


-----Output-----

The only line should contain two integers — the number of steps in the best answer and the number of replacement moves in it.


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

Output
12 1



-----Note-----

Here are the steps for the first example (the starting piece is a knight):  Move to $(3, 2)$  Move to $(1, 3)$  Move to $(3, 2)$  Replace the knight with a rook  Move to $(3, 1)$  Move to $(3, 3)$  Move to $(3, 2)$  Move to $(2, 2)$  Move to $(2, 3)$  Move to $(2, 1)$  Move to $(1, 1)$  Move to $(1, 2)$
user: Есть n-подъездный дом, в каждом подъезде по m этажей, и на каждом этаже каждого подъезда ровно k квартир. Таким образом, в доме всего n·m·k квартир. Они пронумерованы естественным образом от 1 до n·m·k, то есть первая квартира на первом этаже в первом подъезде имеет номер 1, первая квартира на втором этаже первого подъезда имеет номер k + 1 и так далее. Особенность этого дома состоит в том, что он круглый. То есть если обходить его по часовой стрелке, то после подъезда номер 1 следует подъезд номер 2, затем подъезд номер 3 и так далее до подъезда номер n. После подъезда номер n снова идёт подъезд номер 1.

Эдвард живёт в квартире номер a, а Наташа — в квартире номер b. Переход на 1 этаж вверх или вниз по лестнице занимает 5 секунд, переход от двери подъезда к двери соседнего подъезда — 15 секунд, а переход в пределах одного этажа одного подъезда происходит мгновенно. Также в каждом подъезде дома есть лифт. Он устроен следующим образом: он всегда приезжает ровно через 10 секунд после вызова, а чтобы переместить пассажира на один этаж вверх или вниз, лифт тратит ровно 1 секунду. Посадка и высадка происходят мгновенно.

Помогите Эдварду найти минимальное время, за которое он сможет добраться до квартиры Наташи. Считайте, что Эдвард может выйти из подъезда только с первого этажа соответствующего подъезда (это происходит мгновенно). Если Эдвард стоит перед дверью какого-то подъезда, он может зайти в него и сразу окажется на первом этаже этого подъезда (это также происходит мгновенно). Эдвард может выбирать, в каком направлении идти вокруг дома.


-----Входные данные-----

В первой строке входных данных следуют три числа n, m, k (1 ≤ n, m, k ≤ 1000) — количество подъездов в доме, количество этажей в каждом подъезде и количество квартир на каждом этаже каждого подъезда соответственно.

Во второй строке входных данных записаны два числа a и b (1 ≤ a, b ≤ n·m·k) — номера квартир, в которых живут Эдвард и Наташа, соответственно. Гарантируется, что эти номера различны. 


-----Выходные данные-----

Выведите единственное целое число — минимальное время (в секундах), за которое Эдвард сможет добраться от своей квартиры до квартиры Наташи.


-----Примеры-----
Входные данные
4 10 5
200 6

Выходные данные
39

Входные данные
3 1 5
7 2

Выходные данные
15



-----Примечание-----

В первом тестовом примере Эдвард находится в 4 подъезде на 10 этаже, а Наташа находится в 1 подъезде на 2 этаже. Поэтому Эдварду выгодно сначала спуститься на лифте на первый этаж (на это он потратит 19 секунд, из которых 10 — на ожидание и 9 — на поездку на лифте), затем обойти дом против часовой стрелки до подъезда номер 1 (на это он потратит 15 секунд), и наконец подняться по лестнице на этаж номер 2 (на это он потратит 5 секунд). Таким образом, ответ равен 19 + 15 + 5 = 39.

Во втором тестовом примере Эдвард живёт в подъезде 2 на этаже 1, а Наташа находится в подъезде 1 на этаже 1. Поэтому Эдварду выгодно просто обойти дом по часовой стрелке до подъезда 1, на это он потратит 15 секунд.
user: Top-model Izabella participates in the competition. She wants to impress judges and show her mathematical skills.

Her problem is following: for given string, consisting of only 0 and 1, tell if it's possible to remove some digits in such a way, that remaining number is a representation of some positive integer, divisible by 64, in the binary numerical system.


-----Input-----

In the only line given a non-empty binary string s with length up to 100.


-----Output-----

Print «yes» (without quotes) if it's possible to remove digits required way and «no» otherwise.


-----Examples-----
Input
100010001

Output
yes
Input
100

Output
no


-----Note-----

In the first test case, you can get string 1 000 000 after removing two ones which is a representation of number 64 in the binary numerical system.

You can read more about binary numeral system representation here: https://en.wikipedia.org/wiki/Binary_system
user: You are given a string s consisting of |s| small english letters.

In one move you can replace any character of this string to the next character in alphabetical order (a will be replaced with b, s will be replaced with t, etc.). You cannot replace letter z with any other letter.

Your target is to make some number of moves (not necessary minimal) to get string abcdefghijklmnopqrstuvwxyz (english alphabet) as a subsequence. Subsequence of the string is the string that is obtained by deleting characters at some positions. You need to print the string that will be obtained from the given string and will be contain english alphabet as a subsequence or say that it is impossible.


-----Input-----

The only one line of the input consisting of the string s consisting of |s| (1 ≤ |s| ≤ 10^5) small english letters.


-----Output-----

If you can get a string that can be obtained from the given string and will contain english alphabet as a subsequence, print it. Otherwise print «-1» (without quotes).


-----Examples-----
Input
aacceeggiikkmmooqqssuuwwyy

Output
abcdefghijklmnopqrstuvwxyz

Input
thereisnoanswer

Output
-1
user: While Grisha was celebrating New Year with Ded Moroz, Misha gifted Sasha a small rectangular pond of size n × m, divided into cells of size 1 × 1, inhabited by tiny evil fishes (no more than one fish per cell, otherwise they'll strife!).

The gift bundle also includes a square scoop of size r × r, designed for fishing. If the lower-left corner of the scoop-net is located at cell (x, y), all fishes inside the square (x, y)...(x + r - 1, y + r - 1) get caught. Note that the scoop-net should lie completely inside the pond when used.

Unfortunately, Sasha is not that skilled in fishing and hence throws the scoop randomly. In order to not frustrate Sasha, Misha decided to release k fishes into the empty pond in such a way that the expected value of the number of caught fishes is as high as possible. Help Misha! In other words, put k fishes in the pond into distinct cells in such a way that when the scoop-net is placed into a random position among (n - r + 1)·(m - r + 1) possible positions, the average number of caught fishes is as high as possible.


-----Input-----

The only line contains four integers n, m, r, k (1 ≤ n, m ≤ 10^5, 1 ≤ r ≤ min(n, m), 1 ≤ k ≤ min(n·m, 10^5)).


-----Output-----

Print a single number — the maximum possible expected number of caught fishes.

You answer is considered correct, is its absolute or relative error does not exceed 10^{ - 9}. Namely, let your answer be a, and the jury's answer be b. Your answer is considered correct, if $\frac{|a - b|}{\operatorname{max}(1,|b|)} \leq 10^{-9}$.


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

Output
2.0000000000

Input
12 17 9 40

Output
32.8333333333



-----Note-----

In the first example you can put the fishes in cells (2, 1), (2, 2), (2, 3). In this case, for any of four possible positions of the scoop-net (highlighted with light green), the number of fishes inside is equal to two, and so is the expected value. [Image]
user: Nick had received an awesome array of integers $a=[a_1, a_2, \dots, a_n]$ as a gift for his $5$ birthday from his mother. He was already going to explore its various properties but after unpacking he was disappointed a lot because the product $a_1 \cdot a_2 \cdot \dots a_n$ of its elements seemed to him not large enough.

He was ready to throw out the array, but his mother reassured him. She told him, that array would not be spoiled after the following operation: choose any index $i$ ($1 \le i \le n$) and do $a_i := -a_i - 1$.

For example, he can change array $[3, -1, -4, 1]$ to an array $[-4, -1, 3, 1]$ after applying this operation to elements with indices $i=1$ and $i=3$. 

Kolya had immediately understood that sometimes it's possible to increase the product of integers of the array a lot. Now he has decided that he wants to get an array with the maximal possible product of integers using only this operation with its elements (possibly zero, one or more times, as many as he wants), it is not forbidden to do this operation several times for the same index. 

Help Kolya and print the array with the maximal possible product of elements $a_1 \cdot a_2 \cdot \dots a_n$ which can be received using only this operation in some order.

If there are multiple answers, print any of them.


-----Input-----

The first line contains integer $n$ ($1 \leq n \leq 10^{5}$) — number of integers in the array.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^{6} \leq a_i \leq 10^{6}$) — elements of the array


-----Output-----

Print $n$ numbers — elements of the array with the maximal possible product of elements which can be received using only this operation in some order from the given array.

If there are multiple answers, print any of them.


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

Output
-3 -3 -3 -3 
Input
1
0

Output
0 
Input
3
-3 -3 2

Output
-3 -3 2
user: You are given two integers n and k. Find k-th smallest divisor of n, or report that it doesn't exist.

Divisor of n is any such natural number, that n can be divided by it without remainder.


-----Input-----

The first line contains two integers n and k (1 ≤ n ≤ 10^15, 1 ≤ k ≤ 10^9).


-----Output-----

If n has less than k divisors, output -1.

Otherwise, output the k-th smallest divisor of n.


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

Output
2

Input
5 3

Output
-1

Input
12 5

Output
6



-----Note-----

In the first example, number 4 has three divisors: 1, 2 and 4. The second one is 2.

In the second example, number 5 has only two divisors: 1 and 5. The third divisor doesn't exist, so the answer is -1.
user: Absent-minded Masha got set of n cubes for her birthday.

At each of 6 faces of each cube, there is exactly one digit from 0 to 9. Masha became interested what is the largest natural x such she can make using her new cubes all integers from 1 to x.

To make a number Masha can rotate her cubes and put them in a row. After that, she looks at upper faces of cubes from left to right and reads the number.

The number can't contain leading zeros. It's not required to use all cubes to build a number.

Pay attention: Masha can't make digit 6 from digit 9 and vice-versa using cube rotations.


-----Input-----

In first line integer n is given (1 ≤ n ≤ 3) — the number of cubes, Masha got for her birthday.

Each of next n lines contains 6 integers a_{i}_{j} (0 ≤ a_{i}_{j} ≤ 9) — number on j-th face of i-th cube.


-----Output-----

Print single integer — maximum number x such Masha can make any integers from 1 to x using her cubes or 0 if Masha can't make even 1.


-----Examples-----
Input
3
0 1 2 3 4 5
6 7 8 9 0 1
2 3 4 5 6 7

Output
87
Input
3
0 1 3 5 6 8
1 2 4 5 7 8
2 3 4 6 7 9

Output
98


-----Note-----

In the first test case, Masha can build all numbers from 1 to 87, but she can't make 88 because there are no two cubes with digit 8.
user: For a given positive integer n denote its k-rounding as the minimum positive integer x, such that x ends with k or more zeros in base 10 and is divisible by n.

For example, 4-rounding of 375 is 375·80 = 30000. 30000 is the minimum integer such that it ends with 4 or more zeros and is divisible by 375.

Write a program that will perform the k-rounding of n.


-----Input-----

The only line contains two integers n and k (1 ≤ n ≤ 10^9, 0 ≤ k ≤ 8).


-----Output-----

Print the k-rounding of n.


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

Output
30000

Input
10000 1

Output
10000

Input
38101 0

Output
38101

Input
123456789 8

Output
12345678900000000