meetforever/GRPO_CL huggingface dataset:
user: Hooray! Polycarp turned $n$ years old! The Technocup Team sincerely congratulates Polycarp!

Polycarp celebrated all of his $n$ birthdays: from the $1$-th to the $n$-th. At the moment, he is wondering: how many times he turned beautiful number of years?

According to Polycarp, a positive integer is beautiful if it consists of only one digit repeated one or more times. For example, the following numbers are beautiful: $1$, $77$, $777$, $44$ and $999999$. The following numbers are not beautiful: $12$, $11110$, $6969$ and $987654321$.

Of course, Polycarpus uses the decimal numeral system (i.e. radix is 10).

Help Polycarpus to find the number of numbers from $1$ to $n$ (inclusive) that are beautiful.


-----Input-----

The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the input. Then $t$ test cases follow.

Each test case consists of one line, which contains a positive integer $n$ ($1 \le n \le 10^9$) — how many years Polycarp has turned.


-----Output-----

Print $t$ integers — the answers to the given test cases in the order they are written in the test. Each answer is an integer: the number of beautiful years between $1$ and $n$, inclusive.


-----Example-----
Input
6
18
1
9
100500
33
1000000000

Output
10
1
9
45
12
81



-----Note-----

In the first test case of the example beautiful years are $1$, $2$, $3$, $4$, $5$, $6$, $7$, $8$, $9$ and $11$.
user: Ashish and Vivek play a game on a matrix consisting of $n$ rows and $m$ columns, where they take turns claiming cells. Unclaimed cells are represented by $0$, while claimed cells are represented by $1$. The initial state of the matrix is given. There can be some claimed cells in the initial state.

In each turn, a player must claim a cell. A cell may be claimed if it is unclaimed and does not share a row or column with any other already claimed cells. When a player is unable to make a move, he loses and the game ends.

If Ashish and Vivek take turns to move and Ashish goes first, determine the winner of the game if both of them are playing optimally.

Optimal play between two players means that both players choose the best possible strategy to achieve the best possible outcome for themselves.


-----Input-----

The first line consists of a single integer $t$ $(1 \le t \le 50)$ — the number of test cases. The description of the test cases follows.

The first line of each test case consists of two space-separated integers $n$, $m$ $(1 \le n, m \le 50)$ — the number of rows and columns in the matrix.

The following $n$ lines consist of $m$ integers each, the $j$-th integer on the $i$-th line denoting $a_{i,j}$ $(a_{i,j} \in \{0, 1\})$.


-----Output-----

For each test case if Ashish wins the game print "Ashish" otherwise print "Vivek" (without quotes).


-----Example-----
Input
4
2 2
0 0
0 0
2 2
0 0
0 1
2 3
1 0 1
1 1 0
3 3
1 0 0
0 0 0
1 0 0

Output
Vivek
Ashish
Vivek
Ashish



-----Note-----

For the first case: One possible scenario could be: Ashish claims cell $(1, 1)$, Vivek then claims cell $(2, 2)$. Ashish can neither claim cell $(1, 2)$, nor cell $(2, 1)$ as cells $(1, 1)$ and $(2, 2)$ are already claimed. Thus Ashish loses. It can be shown that no matter what Ashish plays in this case, Vivek will win. 

For the second case: Ashish claims cell $(1, 1)$, the only cell that can be claimed in the first move. After that Vivek has no moves left.

For the third case: Ashish cannot make a move, so Vivek wins.

For the fourth case: If Ashish claims cell $(2, 3)$, Vivek will have no moves left.
user: You are given a colored permutation $p_1, p_2, \dots, p_n$. The $i$-th element of the permutation has color $c_i$.

Let's define an infinite path as infinite sequence $i, p[i], p[p[i]], p[p[p[i]]] \dots$ where all elements have same color ($c[i] = c[p[i]] = c[p[p[i]]] = \dots$).

We can also define a multiplication of permutations $a$ and $b$ as permutation $c = a \times b$ where $c[i] = b[a[i]]$. Moreover, we can define a power $k$ of permutation $p$ as $p^k=\underbrace{p \times p \times \dots \times p}_{k \text{ times}}$.

Find the minimum $k > 0$ such that $p^k$ has at least one infinite path (i.e. there is a position $i$ in $p^k$ such that the sequence starting from $i$ is an infinite path).

It can be proved that the answer always exists.


-----Input-----

The first line contains single integer $T$ ($1 \le T \le 10^4$) — the number of test cases.

Next $3T$ lines contain test cases — one per three lines. The first line contains single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the size of the permutation.

The second line contains $n$ integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$, $p_i \neq p_j$ for $i \neq j$) — the permutation $p$.

The third line contains $n$ integers $c_1, c_2, \dots, c_n$ ($1 \le c_i \le n$) — the colors of elements of the permutation.

It is guaranteed that the total sum of $n$ doesn't exceed $2 \cdot 10^5$.


-----Output-----

Print $T$ integers — one per test case. For each test case print minimum $k > 0$ such that $p^k$ has at least one infinite path.


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

Output
1
5
2



-----Note-----

In the first test case, $p^1 = p = [1, 3, 4, 2]$ and the sequence starting from $1$: $1, p[1] = 1, \dots$ is an infinite path.

In the second test case, $p^5 = [1, 2, 3, 4, 5]$ and it obviously contains several infinite paths.

In the third test case, $p^2 = [3, 6, 1, 8, 7, 2, 5, 4]$ and the sequence starting from $4$: $4, p^2[4]=8, p^2[8]=4, \dots$ is an infinite path since $c_4 = c_8 = 4$.
user: — Hey folks, how do you like this problem?

— That'll do it. 

BThero is a powerful magician. He has got $n$ piles of candies, the $i$-th pile initially contains $a_i$ candies. BThero can cast a copy-paste spell as follows:   He chooses two piles $(i, j)$ such that $1 \le i, j \le n$ and $i \ne j$.  All candies from pile $i$ are copied into pile $j$. Formally, the operation $a_j := a_j + a_i$ is performed. 

BThero can cast this spell any number of times he wants to — but unfortunately, if some pile contains strictly more than $k$ candies, he loses his magic power. What is the maximum number of times BThero can cast the spell without losing his power?


-----Input-----

The first line contains one integer $T$ ($1 \le T \le 500$) — the number of test cases.

Each test case consists of two lines:   the first line contains two integers $n$ and $k$ ($2 \le n \le 1000$, $2 \le k \le 10^4$);  the second line contains $n$ integers $a_1$, $a_2$, ..., $a_n$ ($1 \le a_i \le k$). 

It is guaranteed that the sum of $n$ over all test cases does not exceed $1000$, and the sum of $k$ over all test cases does not exceed $10^4$.


-----Output-----

For each test case, print one integer — the maximum number of times BThero can cast the spell without losing his magic power.


-----Example-----
Input
3
2 2
1 1
3 5
1 2 3
3 7
3 2 2

Output
1
5
4



-----Note-----

In the first test case we get either $a = [1, 2]$ or $a = [2, 1]$ after casting the spell for the first time, and it is impossible to cast it again.
user: There are $n$ segments $[l_i, r_i]$ for $1 \le i \le n$. You should divide all segments into two non-empty groups in such way that there is no pair of segments from different groups which have at least one common point, or say that it's impossible to do it. Each segment should belong to exactly one group.

To optimize testing process you will be given multitest.


-----Input-----

The first line contains one integer $T$ ($1 \le T \le 50000$) — the number of queries. Each query contains description of the set of segments. Queries are independent.

First line of each query contains single integer $n$ ($2 \le n \le 10^5$) — number of segments. It is guaranteed that $\sum{n}$ over all queries does not exceed $10^5$.

The next $n$ lines contains two integers $l_i$, $r_i$ per line ($1 \le l_i \le r_i \le 2 \cdot 10^5$) — the $i$-th segment.


-----Output-----

For each query print $n$ integers $t_1, t_2, \dots, t_n$ ($t_i \in \{1, 2\}$) — for each segment (in the same order as in the input) $t_i$ equals $1$ if the $i$-th segment will belongs to the first group and $2$ otherwise.

If there are multiple answers, you can print any of them. If there is no answer, print $-1$.


-----Example-----
Input
3
2
5 5
2 3
3
3 5
2 3
2 3
3
3 3
4 4
5 5

Output
2 1 
-1
1 1 2 



-----Note-----

In the first query the first and the second segments should be in different groups, but exact numbers don't matter.

In the second query the third segment intersects with the first and the second segments, so they should be in the same group, but then the other group becomes empty, so answer is $-1$.

In the third query we can distribute segments in any way that makes groups non-empty, so any answer of $6$ possible is correct.
user: You're given an array $a_1, \ldots, a_n$ of $n$ non-negative integers.

Let's call it sharpened if and only if there exists an integer $1 \le k \le n$ such that $a_1 < a_2 < \ldots < a_k$ and $a_k > a_{k+1} > \ldots > a_n$. In particular, any strictly increasing or strictly decreasing array is sharpened. For example:  The arrays $[4]$, $[0, 1]$, $[12, 10, 8]$ and $[3, 11, 15, 9, 7, 4]$ are sharpened;  The arrays $[2, 8, 2, 8, 6, 5]$, $[0, 1, 1, 0]$ and $[2, 5, 6, 9, 8, 8]$ are not sharpened. 

You can do the following operation as many times as you want: choose any strictly positive element of the array, and decrease it by one. Formally, you can choose any $i$ ($1 \le i \le n$) such that $a_i>0$ and assign $a_i := a_i - 1$.

Tell if it's possible to make the given array sharpened using some number (possibly zero) of these operations.


-----Input-----

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 15\ 000$)  — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 3 \cdot 10^5$).

The second line of each test case contains a sequence of $n$ non-negative integers $a_1, \ldots, a_n$ ($0 \le a_i \le 10^9$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $3 \cdot 10^5$.


-----Output-----

For each test case, output a single line containing "Yes" (without quotes) if it's possible to make the given array sharpened using the described operations, or "No" (without quotes) otherwise.


-----Example-----
Input
10
1
248618
3
12 10 8
6
100 11 15 9 7 8
4
0 1 1 0
2
0 0
2
0 1
2
1 0
2
1 1
3
0 1 0
3
1 0 1

Output
Yes
Yes
Yes
No
No
Yes
Yes
Yes
Yes
No



-----Note-----

In the first and the second test case of the first test, the given array is already sharpened.

In the third test case of the first test, we can transform the array into $[3, 11, 15, 9, 7, 4]$ (decrease the first element $97$ times and decrease the last element $4$ times). It is sharpened because $3 < 11 < 15$ and $15 > 9 > 7 > 4$.

In the fourth test case of the first test, it's impossible to make the given array sharpened.
user: You have a bag of size $n$. Also you have $m$ boxes. The size of $i$-th box is $a_i$, where each $a_i$ is an integer non-negative power of two.

You can divide boxes into two parts of equal size. Your goal is to fill the bag completely.

For example, if $n = 10$ and $a = [1, 1, 32]$ then you have to divide the box of size $32$ into two parts of size $16$, and then divide the box of size $16$. So you can fill the bag with boxes of size $1$, $1$ and $8$.

Calculate the minimum number of divisions required to fill the bag of size $n$.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 1000$) — the number of test cases.

The first line of each test case contains two integers $n$ and $m$ ($1 \le n \le 10^{18}, 1 \le m \le 10^5$) — the size of bag and the number of boxes, respectively.

The second line of each test case contains $m$ integers $a_1, a_2, \dots , a_m$ ($1 \le a_i \le 10^9$) — the sizes of boxes. It is guaranteed that each $a_i$ is a power of two.

It is also guaranteed that sum of all $m$ over all test cases does not exceed $10^5$.


-----Output-----

For each test case print one integer — the minimum number of divisions required to fill the bag of size $n$ (or $-1$, if it is impossible).


-----Example-----
Input
3
10 3
1 32 1
23 4
16 1 4 1
20 5
2 1 16 1 8

Output
2
-1
0
user: You are given an image, that can be represented with a 2-d n by m grid of pixels. Each pixel of the image is either on or off, denoted by the characters "0" or "1", respectively. You would like to compress this image. You want to choose an integer k > 1 and split the image into k by k blocks. If n and m are not divisible by k, the image is padded with only zeros on the right and bottom so that they are divisible by k. Each pixel in each individual block must have the same value. The given image may not be compressible in its current state. Find the minimum number of pixels you need to toggle (after padding) in order for the image to be compressible for some k. More specifically, the steps are to first choose k, then the image is padded with zeros, then, we can toggle the pixels so it is compressible for this k. The image must be compressible in that state.


-----Input-----

The first line of input will contain two integers n, m (2 ≤ n, m ≤ 2 500), the dimensions of the image.

The next n lines of input will contain a binary string with exactly m characters, representing the image.


-----Output-----

Print a single integer, the minimum number of pixels needed to toggle to make the image compressible.


-----Example-----
Input
3 5
00100
10110
11001

Output
5



-----Note-----

We first choose k = 2.

The image is padded as follows: 

001000

101100

110010

000000



We can toggle the image to look as follows: 

001100

001100

000000

000000



We can see that this image is compressible for k = 2.
user: Now that Heidi has made sure her Zombie Contamination level checker works, it's time to strike! This time, the zombie lair is a strictly convex polygon on the lattice. Each vertex of the polygon occupies a point on the lattice. For each cell of the lattice, Heidi knows the level of Zombie Contamination – the number of corners of the cell that are inside or on the border of the lair.

Given this information, Heidi wants to know the exact shape of the lair to rain destruction on the zombies. Help her!

[Image]


-----Input-----

The input contains multiple test cases.

The first line of each test case contains one integer N, the size of the lattice grid (5 ≤ N ≤ 500). The next N lines each contain N characters, describing the level of Zombie Contamination of each cell in the lattice. Every character of every line is a digit between 0 and 4. 

Cells are given in the same order as they are shown in the picture above: rows go in the decreasing value of y coordinate, and in one row cells go in the order of increasing x coordinate. This means that the first row corresponds to cells with coordinates (1, N), ..., (N, N) and the last row corresponds to cells with coordinates (1, 1), ..., (N, 1).

The last line of the file contains a zero. This line should not be treated as a test case. The sum of the N values for all tests in one file will not exceed 5000.


-----Output-----

For each test case, give the following output:

The first line of the output should contain one integer V, the number of vertices of the polygon that is the secret lair. The next V lines each should contain two integers, denoting the vertices of the polygon in the clockwise order, starting from the lexicographically smallest vertex.


-----Examples-----
Input
8
00000000
00000110
00012210
01234200
02444200
01223200
00001100
00000000
5
00000
01210
02420
01210
00000
7
0000000
0122100
0134200
0013200
0002200
0001100
0000000
0

Output
4
2 3
2 4
6 6
5 2
4
2 2
2 3
3 3
3 2
3
2 5
4 5
4 2



-----Note-----

It is guaranteed that the solution always exists and is unique. It is guaranteed that in the correct solution the coordinates of the polygon vertices are between 2 and N - 2. A vertex (x_1, y_1) is lexicographically smaller than vertex (x_2, y_2) if x_1 < x_2 or $x_{1} = x_{2} \wedge y_{1} < y_{2}$.
user: Bob watches TV every day. He always sets the volume of his TV to $b$. However, today he is angry to find out someone has changed the volume to $a$. Of course, Bob has a remote control that can change the volume.

There are six buttons ($-5, -2, -1, +1, +2, +5$) on the control, which in one press can either increase or decrease the current volume by $1$, $2$, or $5$. The volume can be arbitrarily large, but can never be negative. In other words, Bob cannot press the button if it causes the volume to be lower than $0$.

As Bob is so angry, he wants to change the volume to $b$ using as few button presses as possible. However, he forgets how to do such simple calculations, so he asks you for help. Write a program that given $a$ and $b$, finds the minimum number of presses to change the TV volume from $a$ to $b$.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $T$ ($1 \le T \le 1\,000$). Then the descriptions of the test cases follow.

Each test case consists of one line containing two integers $a$ and $b$ ($0 \le a, b \le 10^{9}$) — the current volume and Bob's desired volume, respectively.


-----Output-----

For each test case, output a single integer — the minimum number of presses to change the TV volume from $a$ to $b$. If Bob does not need to change the volume (i.e. $a=b$), then print $0$.


-----Example-----
Input
3
4 0
5 14
3 9

Output
2
3
2



-----Note-----

In the first example, Bob can press the $-2$ button twice to reach $0$. Note that Bob can not press $-5$ when the volume is $4$ since it will make the volume negative. 

In the second example, one of the optimal ways for Bob is to press the $+5$ twice, then press $-1$ once.

In the last example, Bob can press the $+5$ once, then press $+1$.
user: You play a computer game. In this game, you lead a party of $m$ heroes, and you have to clear a dungeon with $n$ monsters. Each monster is characterized by its power $a_i$. Each hero is characterized by his power $p_i$ and endurance $s_i$.

The heroes clear the dungeon day by day. In the beginning of each day, you choose a hero (exactly one) who is going to enter the dungeon this day.

When the hero enters the dungeon, he is challenged by the first monster which was not defeated during the previous days (so, if the heroes have already defeated $k$ monsters, the hero fights with the monster $k + 1$). When the hero fights the monster, there are two possible outcomes:

  if the monster's power is strictly greater than the hero's power, the hero retreats from the dungeon. The current day ends;  otherwise, the monster is defeated. 

After defeating a monster, the hero either continues fighting with the next monster or leaves the dungeon. He leaves the dungeon either if he has already defeated the number of monsters equal to his endurance during this day (so, the $i$-th hero cannot defeat more than $s_i$ monsters during each day), or if all monsters are defeated — otherwise, he fights with the next monster. When the hero leaves the dungeon, the current day ends.

Your goal is to defeat the last monster. What is the minimum number of days that you need to achieve your goal? Each day you have to use exactly one hero; it is possible that some heroes don't fight the monsters at all. Each hero can be used arbitrary number of times.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 10^5$) — the number of test cases. Then the test cases follow.

The first line of each test case contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of monsters in the dungeon.

The second line contains $n$ integers $a_1$, $a_2$, ..., $a_n$ ($1 \le a_i \le 10^9$), where $a_i$ is the power of the $i$-th monster.

The third line contains one integer $m$ ($1 \le m \le 2 \cdot 10^5$) — the number of heroes in your party.

Then $m$ lines follow, each describing a hero. Each line contains two integers $p_i$ and $s_i$ ($1 \le p_i \le 10^9$, $1 \le s_i \le n$) — the power and the endurance of the $i$-th hero.

It is guaranteed that the sum of $n + m$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case print one integer — the minimum number of days you have to spend to defeat all of the monsters (or $-1$ if it is impossible).


-----Example-----
Input
2
6
2 3 11 14 1 8
2
3 2
100 1
5
3 5 100 2 3
2
30 5
90 1

Output
5
-1
user: Polycarp plays a computer game (yet again). In this game, he fights monsters using magic spells.

There are two types of spells: fire spell of power $x$ deals $x$ damage to the monster, and lightning spell of power $y$ deals $y$ damage to the monster and doubles the damage of the next spell Polycarp casts. Each spell can be cast only once per battle, but Polycarp can cast them in any order.

For example, suppose that Polycarp knows three spells: a fire spell of power $5$, a lightning spell of power $1$, and a lightning spell of power $8$. There are $6$ ways to choose the order in which he casts the spells:

  first, second, third. This order deals $5 + 1 + 2 \cdot 8 = 22$ damage;  first, third, second. This order deals $5 + 8 + 2 \cdot 1 = 15$ damage;  second, first, third. This order deals $1 + 2 \cdot 5 + 8 = 19$ damage;  second, third, first. This order deals $1 + 2 \cdot 8 + 2 \cdot 5 = 27$ damage;  third, first, second. This order deals $8 + 2 \cdot 5 + 1 = 19$ damage;  third, second, first. This order deals $8 + 2 \cdot 1 + 2 \cdot 5 = 20$ damage. 

Initially, Polycarp knows $0$ spells. His spell set changes $n$ times, each time he either learns a new spell or forgets an already known one. After each change, calculate the maximum possible damage Polycarp may deal using the spells he knows.


-----Input-----

The first line contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of changes to the spell set.

Each of the next $n$ lines contains two integers $tp$ and $d$ ($0 \le tp_i \le 1$; $-10^9 \le d \le 10^9$; $d_i \neq 0$) — the description of the change. If $tp_i$ if equal to $0$, then Polycarp learns (or forgets) a fire spell, otherwise he learns (or forgets) a lightning spell.

If $d_i > 0$, then Polycarp learns a spell of power $d_i$. Otherwise, Polycarp forgets a spell with power $-d_i$, and it is guaranteed that he knew that spell before the change.

It is guaranteed that the powers of all spells Polycarp knows after each change are different (Polycarp never knows two spells with the same power).


-----Output-----

After each change, print the maximum damage Polycarp can deal with his current set of spells.


-----Example-----
Input
6
1 5
0 10
1 -5
0 5
1 11
0 -10

Output
5
25
10
15
36
21