meetforever/GRPO_CL huggingface dataset:
user: Polycarpus likes giving presents to Paraskevi. He has bought two chocolate bars, each of them has the shape of a segmented rectangle. The first bar is a_1 × b_1 segments large and the second one is a_2 × b_2 segments large.

Polycarpus wants to give Paraskevi one of the bars at the lunch break and eat the other one himself. Besides, he wants to show that Polycarpus's mind and Paraskevi's beauty are equally matched, so the two bars must have the same number of squares.

To make the bars have the same number of squares, Polycarpus eats a little piece of chocolate each minute. Each minute he does the following:  he either breaks one bar exactly in half (vertically or horizontally) and eats exactly a half of the bar,  or he chips of exactly one third of a bar (vertically or horizontally) and eats exactly a third of the bar. 

In the first case he is left with a half, of the bar and in the second case he is left with two thirds of the bar.

Both variants aren't always possible, and sometimes Polycarpus cannot chip off a half nor a third. For example, if the bar is 16 × 23, then Polycarpus can chip off a half, but not a third. If the bar is 20 × 18, then Polycarpus can chip off both a half and a third. If the bar is 5 × 7, then Polycarpus cannot chip off a half nor a third.

What is the minimum number of minutes Polycarpus needs to make two bars consist of the same number of squares? Find not only the required minimum number of minutes, but also the possible sizes of the bars after the process.


-----Input-----

The first line of the input contains integers a_1, b_1 (1 ≤ a_1, b_1 ≤ 10^9) — the initial sizes of the first chocolate bar. The second line of the input contains integers a_2, b_2 (1 ≤ a_2, b_2 ≤ 10^9) — the initial sizes of the second bar.

You can use the data of type int64 (in Pascal), long long (in С++), long (in Java) to process large integers (exceeding 2^31 - 1).


-----Output-----

In the first line print m — the sought minimum number of minutes. In the second and third line print the possible sizes of the bars after they are leveled in m minutes. Print the sizes using the format identical to the input format. Print the sizes (the numbers in the printed pairs) in any order. The second line must correspond to the first bar and the third line must correspond to the second bar. If there are multiple solutions, print any of them.

If there is no solution, print a single line with integer -1.


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

Output
1
1 6
2 3

Input
36 5
10 16

Output
3
16 5
5 16

Input
3 5
2 1

Output
-1
user: Polycarp and Vasiliy love simple logical games. Today they play a game with infinite chessboard and one pawn for each player. Polycarp and Vasiliy move in turns, Polycarp starts. In each turn Polycarp can move his pawn from cell (x, y) to (x - 1, y) or (x, y - 1). Vasiliy can move his pawn from (x, y) to one of cells: (x - 1, y), (x - 1, y - 1) and (x, y - 1). Both players are also allowed to skip move. 

There are some additional restrictions — a player is forbidden to move his pawn to a cell with negative x-coordinate or y-coordinate or to the cell containing opponent's pawn The winner is the first person to reach cell (0, 0). 

You are given the starting coordinates of both pawns. Determine who will win if both of them play optimally well.


-----Input-----

The first line contains four integers: x_{p}, y_{p}, x_{v}, y_{v} (0 ≤ x_{p}, y_{p}, x_{v}, y_{v} ≤ 10^5) — Polycarp's and Vasiliy's starting coordinates.

It is guaranteed that in the beginning the pawns are in different cells and none of them is in the cell (0, 0).


-----Output-----

Output the name of the winner: "Polycarp" or "Vasiliy".


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

Output
Polycarp

Input
4 7 7 4

Output
Vasiliy



-----Note-----

In the first sample test Polycarp starts in (2, 1) and will move to (1, 1) in the first turn. No matter what his opponent is doing, in the second turn Polycarp can move to (1, 0) and finally to (0, 0) in the third turn.
user: Petr wants to make a calendar for current month. For this purpose he draws a table in which columns correspond to weeks (a week is seven consequent days from Monday to Sunday), rows correspond to weekdays, and cells contain dates. For example, a calendar for January 2017 should look like on the picture: $\left. \begin{array}{|r|r|r|r|r|r|} \hline & {2} & {9} & {16} & {23} & {30} \\ \hline & {3} & {10} & {17} & {24} & {31} \\ \hline & {4} & {11} & {18} & {25} & {} \\ \hline & {5} & {12} & {19} & {26} & {} \\ \hline & {6} & {13} & {20} & {27} & {} \\ \hline & {7} & {14} & {21} & {28} & {} \\ \hline 1 & {8} & {15} & {22} & {29} & {} \\ \hline \end{array} \right.$ 

Petr wants to know how many columns his table should have given the month and the weekday of the first date of that month? Assume that the year is non-leap.


-----Input-----

The only line contain two integers m and d (1 ≤ m ≤ 12, 1 ≤ d ≤ 7) — the number of month (January is the first month, December is the twelfth) and the weekday of the first date of this month (1 is Monday, 7 is Sunday).


-----Output-----

Print single integer: the number of columns the table should have.


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

Output
6

Input
1 1

Output
5

Input
11 6

Output
5



-----Note-----

The first example corresponds to the January 2017 shown on the picture in the statements.

In the second example 1-st January is Monday, so the whole month fits into 5 columns.

In the third example 1-st November is Saturday and 5 columns is enough.
user: The year 2015 is almost over.

Limak is a little polar bear. He has recently learnt about the binary system. He noticed that the passing year has exactly one zero in its representation in the binary system — 2015_10 = 11111011111_2. Note that he doesn't care about the number of zeros in the decimal representation.

Limak chose some interval of years. He is going to count all years from this interval that have exactly one zero in the binary representation. Can you do it faster?

Assume that all positive integers are always written without leading zeros.


-----Input-----

The only line of the input contains two integers a and b (1 ≤ a ≤ b ≤ 10^18) — the first year and the last year in Limak's interval respectively.


-----Output-----

Print one integer – the number of years Limak will count in his chosen interval.


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

Output
2

Input
2015 2015

Output
1

Input
100 105

Output
0

Input
72057594000000000 72057595000000000

Output
26



-----Note-----

In the first sample Limak's interval contains numbers 5_10 = 101_2, 6_10 = 110_2, 7_10 = 111_2, 8_10 = 1000_2, 9_10 = 1001_2 and 10_10 = 1010_2. Two of them (101_2 and 110_2) have the described property.
user: You are given an integer N. Consider all possible segments on the coordinate axis with endpoints at integer points with coordinates between 0 and N, inclusive; there will be $\frac{n(n + 1)}{2}$ of them.

You want to draw these segments in several layers so that in each layer the segments don't overlap (they might touch at the endpoints though). You can not move the segments to a different location on the coordinate axis. 

Find the minimal number of layers you have to use for the given N.


-----Input-----

The only input line contains a single integer N (1 ≤ N ≤ 100).


-----Output-----

Output a single integer - the minimal number of layers required to draw the segments for the given N.


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

Output
2

Input
3

Output
4

Input
4

Output
6



-----Note-----

As an example, here are the segments and their optimal arrangement into layers for N = 4. [Image]
user: Anya loves to fold and stick. Today she decided to do just that.

Anya has n cubes lying in a line and numbered from 1 to n from left to right, with natural numbers written on them. She also has k stickers with exclamation marks. We know that the number of stickers does not exceed the number of cubes.

Anya can stick an exclamation mark on the cube and get the factorial of the number written on the cube. For example, if a cube reads 5, then after the sticking it reads 5!, which equals 120.

You need to help Anya count how many ways there are to choose some of the cubes and stick on some of the chosen cubes at most k exclamation marks so that the sum of the numbers written on the chosen cubes after the sticking becomes equal to S. Anya can stick at most one exclamation mark on each cube. Can you do it?

Two ways are considered the same if they have the same set of chosen cubes and the same set of cubes with exclamation marks.


-----Input-----

The first line of the input contains three space-separated integers n, k and S (1 ≤ n ≤ 25, 0 ≤ k ≤ n, 1 ≤ S ≤ 10^16) — the number of cubes and the number of stickers that Anya has, and the sum that she needs to get. 

The second line contains n positive integers a_{i} (1 ≤ a_{i} ≤ 10^9) — the numbers, written on the cubes. The cubes in the input are described in the order from left to right, starting from the first one. 

Multiple cubes can contain the same numbers.


-----Output-----

Output the number of ways to choose some number of cubes and stick exclamation marks on some of them so that the sum of the numbers became equal to the given number S.


-----Examples-----
Input
2 2 30
4 3

Output
1

Input
2 2 7
4 3

Output
1

Input
3 1 1
1 1 1

Output
6



-----Note-----

In the first sample the only way is to choose both cubes and stick an exclamation mark on each of them.

In the second sample the only way is to choose both cubes but don't stick an exclamation mark on any of them.

In the third sample it is possible to choose any of the cubes in three ways, and also we may choose to stick or not to stick the exclamation mark on it. So, the total number of ways is six.
user: Suppose you are performing the following algorithm. There is an array $v_1, v_2, \dots, v_n$ filled with zeroes at start. The following operation is applied to the array several times — at $i$-th step ($0$-indexed) you can:   either choose position $pos$ ($1 \le pos \le n$) and increase $v_{pos}$ by $k^i$;  or not choose any position and skip this step. 

You can choose how the algorithm would behave on each step and when to stop it. The question is: can you make array $v$ equal to the given array $a$ ($v_j = a_j$ for each $j$) after some step?


-----Input-----

The first line contains one integer $T$ ($1 \le T \le 1000$) — the number of test cases. Next $2T$ lines contain test cases — two lines per test case.

The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 30$, $2 \le k \le 100$) — the size of arrays $v$ and $a$ and value $k$ used in the algorithm.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^{16}$) — the array you'd like to achieve.


-----Output-----

For each test case print YES (case insensitive) if you can achieve the array $a$ after some step or NO (case insensitive) otherwise.


-----Example-----
Input
5
4 100
0 0 0 0
1 2
1
3 4
1 4 1
3 2
0 1 3
3 9
0 59049 810

Output
YES
YES
NO
NO
YES



-----Note-----

In the first test case, you can stop the algorithm before the $0$-th step, or don't choose any position several times and stop the algorithm.

In the second test case, you can add $k^0$ to $v_1$ and stop the algorithm.

In the third test case, you can't make two $1$ in the array $v$.

In the fifth test case, you can skip $9^0$ and $9^1$, then add $9^2$ and $9^3$ to $v_3$, skip $9^4$ and finally, add $9^5$ to $v_2$.
user: Let's denote d(n) as the number of divisors of a positive integer n. You are given three integers a, b and c. Your task is to calculate the following sum:

$\sum_{i = 1}^{a} \sum_{j = 1}^{b} \sum_{k = 1}^{c} d(i \cdot j \cdot k)$

Find the sum modulo 1073741824 (2^30).


-----Input-----

The first line contains three space-separated integers a, b and c (1 ≤ a, b, c ≤ 100).


-----Output-----

Print a single integer — the required sum modulo 1073741824 (2^30).


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

Output
20

Input
5 6 7

Output
1520



-----Note-----

For the first example.

  d(1·1·1) = d(1) = 1;  d(1·1·2) = d(2) = 2;  d(1·2·1) = d(2) = 2;  d(1·2·2) = d(4) = 3;  d(2·1·1) = d(2) = 2;  d(2·1·2) = d(4) = 3;  d(2·2·1) = d(4) = 3;  d(2·2·2) = d(8) = 4. 

So the result is 1 + 2 + 2 + 3 + 2 + 3 + 3 + 4 = 20.
user: Bessie the cow and her best friend Elsie each received a sliding puzzle on Pi Day. Their puzzles consist of a 2 × 2 grid and three tiles labeled 'A', 'B', and 'C'. The three tiles sit on top of the grid, leaving one grid cell empty. To make a move, Bessie or Elsie can slide a tile adjacent to the empty cell into the empty cell as shown below: $\rightarrow$ 

In order to determine if they are truly Best Friends For Life (BFFLs), Bessie and Elsie would like to know if there exists a sequence of moves that takes their puzzles to the same configuration (moves can be performed in both puzzles). Two puzzles are considered to be in the same configuration if each tile is on top of the same grid cell in both puzzles. Since the tiles are labeled with letters, rotations and reflections are not allowed.


-----Input-----

The first two lines of the input consist of a 2 × 2 grid describing the initial configuration of Bessie's puzzle. The next two lines contain a 2 × 2 grid describing the initial configuration of Elsie's puzzle. The positions of the tiles are labeled 'A', 'B', and 'C', while the empty cell is labeled 'X'. It's guaranteed that both puzzles contain exactly one tile with each letter and exactly one empty position.


-----Output-----

Output "YES"(without quotes) if the puzzles can reach the same configuration (and Bessie and Elsie are truly BFFLs). Otherwise, print "NO" (without quotes).


-----Examples-----
Input
AB
XC
XB
AC

Output
YES

Input
AB
XC
AC
BX

Output
NO



-----Note-----

The solution to the first sample is described by the image. All Bessie needs to do is slide her 'A' tile down.

In the second sample, the two puzzles can never be in the same configuration. Perhaps Bessie and Elsie are not meant to be friends after all...
user: Alexander is learning how to convert numbers from the decimal system to any other, however, he doesn't know English letters, so he writes any number only as a decimal number, it means that instead of the letter A he will write the number 10. Thus, by converting the number 475 from decimal to hexadecimal system, he gets 11311 (475 = 1·16^2 + 13·16^1 + 11·16^0). Alexander lived calmly until he tried to convert the number back to the decimal number system.

Alexander remembers that he worked with little numbers so he asks to find the minimum decimal number so that by converting it to the system with the base n he will get the number k.


-----Input-----

The first line contains the integer n (2 ≤ n ≤ 10^9). The second line contains the integer k (0 ≤ k < 10^60), it is guaranteed that the number k contains no more than 60 symbols. All digits in the second line are strictly less than n.

Alexander guarantees that the answer exists and does not exceed 10^18.

The number k doesn't contain leading zeros.


-----Output-----

Print the number x (0 ≤ x ≤ 10^18) — the answer to the problem.


-----Examples-----
Input
13
12

Output
12
Input
16
11311

Output
475
Input
20
999

Output
3789
Input
17
2016

Output
594


-----Note-----

In the first example 12 could be obtained by converting two numbers to the system with base 13: 12 = 12·13^0 or 15 = 1·13^1 + 2·13^0.
user: Array of integers is unimodal, if:

  it is strictly increasing in the beginning;  after that it is constant;  after that it is strictly decreasing. 

The first block (increasing) and the last block (decreasing) may be absent. It is allowed that both of this blocks are absent.

For example, the following three arrays are unimodal: [5, 7, 11, 11, 2, 1], [4, 4, 2], [7], but the following three are not unimodal: [5, 5, 6, 6, 1], [1, 2, 1, 2], [4, 5, 5, 6].

Write a program that checks if an array is unimodal.


-----Input-----

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

The second line contains n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 1 000) — the elements of the array.


-----Output-----

Print "YES" if the given array is unimodal. Otherwise, print "NO".

You can output each letter in any case (upper or lower).


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

Output
YES

Input
5
10 20 30 20 10

Output
YES

Input
4
1 2 1 2

Output
NO

Input
7
3 3 3 3 3 3 3

Output
YES



-----Note-----

In the first example the array is unimodal, because it is strictly increasing in the beginning (from position 1 to position 2, inclusively), that it is constant (from position 2 to position 4, inclusively) and then it is strictly decreasing (from position 4 to position 6, inclusively).
user: At first, let's define function $f(x)$ as follows: $$ \begin{matrix} f(x) & = & \left\{ \begin{matrix} \frac{x}{2} & \mbox{if } x \text{ is even} \\ x - 1 & \mbox{otherwise } \end{matrix} \right. \end{matrix} $$

We can see that if we choose some value $v$ and will apply function $f$ to it, then apply $f$ to $f(v)$, and so on, we'll eventually get $1$. Let's write down all values we get in this process in a list and denote this list as $path(v)$. For example, $path(1) = [1]$, $path(15) = [15, 14, 7, 6, 3, 2, 1]$, $path(32) = [32, 16, 8, 4, 2, 1]$.

Let's write all lists $path(x)$ for every $x$ from $1$ to $n$. The question is next: what is the maximum value $y$ such that $y$ is contained in at least $k$ different lists $path(x)$?

Formally speaking, you need to find maximum $y$ such that $\left| \{ x ~|~ 1 \le x \le n, y \in path(x) \} \right| \ge k$.


-----Input-----

The first line contains two integers $n$ and $k$ ($1 \le k \le n \le 10^{18}$).


-----Output-----

Print the only integer — the maximum value that is contained in at least $k$ paths.


-----Examples-----
Input
11 3

Output
5

Input
11 6

Output
4

Input
20 20

Output
1

Input
14 5

Output
6

Input
1000000 100

Output
31248



-----Note-----

In the first example, the answer is $5$, since $5$ occurs in $path(5)$, $path(10)$ and $path(11)$.

In the second example, the answer is $4$, since $4$ occurs in $path(4)$, $path(5)$, $path(8)$, $path(9)$, $path(10)$ and $path(11)$.

In the third example $n = k$, so the answer is $1$, since $1$ is the only number occuring in all paths for integers from $1$ to $20$.
user: Consider a billiard table of rectangular size $n \times m$ with four pockets. Let's introduce a coordinate system with the origin at the lower left corner (see the picture).  [Image] 

There is one ball at the point $(x, y)$ currently. Max comes to the table and strikes the ball. The ball starts moving along a line that is parallel to one of the axes or that makes a $45^{\circ}$ angle with them. We will assume that:   the angles between the directions of the ball before and after a collision with a side are equal,  the ball moves indefinitely long, it only stops when it falls into a pocket,  the ball can be considered as a point, it falls into a pocket if and only if its coordinates coincide with one of the pockets,  initially the ball is not in a pocket. 

Note that the ball can move along some side, in this case the ball will just fall into the pocket at the end of the side.

Your task is to determine whether the ball will fall into a pocket eventually, and if yes, which of the four pockets it will be.


-----Input-----

The only line contains $6$ integers $n$, $m$, $x$, $y$, $v_x$, $v_y$ ($1 \leq n, m \leq 10^9$, $0 \leq x \leq n$; $0 \leq y \leq m$; $-1 \leq v_x, v_y \leq 1$; $(v_x, v_y) \neq (0, 0)$) — the width of the table, the length of the table, the $x$-coordinate of the initial position of the ball, the $y$-coordinate of the initial position of the ball, the $x$-component of its initial speed and the $y$-component of its initial speed, respectively. It is guaranteed that the ball is not initially in a pocket.


-----Output-----

Print the coordinates of the pocket the ball will fall into, or $-1$ if the ball will move indefinitely.


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

Output
0 0
Input
4 4 2 0 1 1

Output
-1
Input
10 10 10 1 -1 0

Output
-1


-----Note-----

The first sample:  [Image] 

The second sample:  [Image] 

In the third sample the ball will never change its $y$ coordinate, so the ball will never fall into a pocket.
user: Gerald bought two very rare paintings at the Sotheby's auction and he now wants to hang them on the wall. For that he bought a special board to attach it to the wall and place the paintings on the board. The board has shape of an a_1 × b_1 rectangle, the paintings have shape of a a_2 × b_2 and a_3 × b_3 rectangles.

Since the paintings are painted in the style of abstract art, it does not matter exactly how they will be rotated, but still, one side of both the board, and each of the paintings must be parallel to the floor. The paintings can touch each other and the edges of the board, but can not overlap or go beyond the edge of the board. Gerald asks whether it is possible to place the paintings on the board, or is the board he bought not large enough?


-----Input-----

The first line contains two space-separated numbers a_1 and b_1 — the sides of the board. Next two lines contain numbers a_2, b_2, a_3 and b_3 — the sides of the paintings. All numbers a_{i}, b_{i} in the input are integers and fit into the range from 1 to 1000.


-----Output-----

If the paintings can be placed on the wall, print "YES" (without the quotes), and if they cannot, print "NO" (without the quotes).


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

Output
YES

Input
5 5
3 3
3 3

Output
NO

Input
4 2
2 3
1 2

Output
YES



-----Note-----

That's how we can place the pictures in the first test:

[Image]

And that's how we can do it in the third one.

[Image]
user: Masha really loves algebra. On the last lesson, her strict teacher Dvastan gave she new exercise.

You are given geometric progression b defined by two integers b_1 and q. Remind that a geometric progression is a sequence of integers b_1, b_2, b_3, ..., where for each i > 1 the respective term satisfies the condition b_{i} = b_{i} - 1·q, where q is called the common ratio of the progression. Progressions in Uzhlyandia are unusual: both b_1 and q can equal 0. Also, Dvastan gave Masha m "bad" integers a_1, a_2, ..., a_{m}, and an integer l.

Masha writes all progression terms one by one onto the board (including repetitive) while condition |b_{i}| ≤ l is satisfied (|x| means absolute value of x). There is an exception: if a term equals one of the "bad" integers, Masha skips it (doesn't write onto the board) and moves forward to the next term.

But the lesson is going to end soon, so Masha has to calculate how many integers will be written on the board. In order not to get into depression, Masha asked you for help: help her calculate how many numbers she will write, or print "inf" in case she needs to write infinitely many integers.


-----Input-----

The first line of input contains four integers b_1, q, l, m (-10^9 ≤ b_1, q ≤ 10^9, 1 ≤ l ≤ 10^9, 1 ≤ m ≤ 10^5) — the initial term and the common ratio of progression, absolute value of maximal number that can be written on the board and the number of "bad" integers, respectively.

The second line contains m distinct integers a_1, a_2, ..., a_{m} (-10^9 ≤ a_{i} ≤ 10^9) — numbers that will never be written on the board.


-----Output-----

Print the only integer, meaning the number of progression terms that will be written on the board if it is finite, or "inf" (without quotes) otherwise.


-----Examples-----
Input
3 2 30 4
6 14 25 48

Output
3
Input
123 1 2143435 4
123 11 -5453 141245

Output
0
Input
123 1 2143435 4
54343 -13 6 124

Output
inf


-----Note-----

In the first sample case, Masha will write integers 3, 12, 24. Progression term 6 will be skipped because it is a "bad" integer. Terms bigger than 24 won't be written because they exceed l by absolute value.

In the second case, Masha won't write any number because all terms are equal 123 and this is a "bad" integer.

In the third case, Masha will write infinitely integers 123.