meetforever/GRPO_CL huggingface dataset:
user: Not to be confused with chessboard.

 [Image] 


-----Input-----

The first line of input contains a single integer N (1 ≤ N ≤ 100) — the number of cheeses you have.

The next N lines describe the cheeses you have. Each line contains two space-separated strings: the name of the cheese and its type. The name is a string of lowercase English letters between 1 and 10 characters long. The type is either "soft" or "hard. All cheese names are distinct.


-----Output-----

Output a single number.


-----Examples-----
Input
9
brie soft
camembert soft
feta soft
goat soft
muenster soft
asiago hard
cheddar hard
gouda hard
swiss hard

Output
3

Input
6
parmesan hard
emmental hard
edam hard
colby hard
gruyere hard
asiago hard

Output
4
user: You are given two arrays $a$ and $b$, both of length $n$. All elements of both arrays are from $0$ to $n-1$.

You can reorder elements of the array $b$ (if you want, you may leave the order of elements as it is). After that, let array $c$ be the array of length $n$, the $i$-th element of this array is $c_i = (a_i + b_i) \% n$, where $x \% y$ is $x$ modulo $y$.

Your task is to reorder elements of the array $b$ to obtain the lexicographically minimum possible array $c$.

Array $x$ of length $n$ is lexicographically less than array $y$ of length $n$, if there exists such $i$ ($1 \le i \le n$), that $x_i < y_i$, and for any $j$ ($1 \le j < i$) $x_j = y_j$.


-----Input-----

The first line of the input contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of elements in $a$, $b$ and $c$.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i < n$), where $a_i$ is the $i$-th element of $a$.

The third line of the input contains $n$ integers $b_1, b_2, \dots, b_n$ ($0 \le b_i < n$), where $b_i$ is the $i$-th element of $b$.


-----Output-----

Print the lexicographically minimum possible array $c$. Recall that your task is to reorder elements of the array $b$ and obtain the lexicographically minimum possible array $c$, where the $i$-th element of $c$ is $c_i = (a_i + b_i) \% n$.


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

Output
1 0 0 2 

Input
7
2 5 1 5 3 4 3
2 4 3 5 6 5 1

Output
0 0 0 1 0 2 4
user: [Image] 


-----Input-----

The input consists of four lines, each line containing a single digit 0 or 1.


-----Output-----

Output a single digit, 0 or 1.


-----Example-----
Input
0
1
1
0

Output
0
user: Takahashi is meeting up with Aoki.
They have planned to meet at a place that is D meters away from Takahashi's house in T minutes from now.
Takahashi will leave his house now and go straight to the place at a speed of S meters per minute.
Will he arrive in time?

-----Constraints-----
 - 1 \leq D \leq 10000
 - 1 \leq T \leq 10000
 - 1 \leq S \leq 10000
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
D T S

-----Output-----
If Takahashi will reach the place in time, print Yes; otherwise, print No.

-----Sample Input-----
1000 15 80

-----Sample Output-----
Yes

It takes 12.5 minutes to go 1000 meters to the place at a speed of 80 meters per minute. They have planned to meet in 15 minutes so he will arrive in time.
user: We have a bingo card with a 3\times3 grid. The square at the i-th row from the top and the j-th column from the left contains the number A_{i, j}.
The MC will choose N numbers, b_1, b_2, \cdots, b_N. If our bingo sheet contains some of those numbers, we will mark them on our sheet.
Determine whether we will have a bingo when the N numbers are chosen, that is, the sheet will contain three marked numbers in a row, column, or diagonal.

-----Constraints-----
 - All values in input are integers.
 - 1 \leq A_{i, j} \leq 100
 - A_{i_1, j_1} \neq A_{i_2, j_2} ((i_1, j_1) \neq (i_2, j_2))
 - 1 \leq N \leq 10
 - 1 \leq b_i \leq 100
 - b_i \neq b_j (i \neq j)

-----Input-----
Input is given from Standard Input in the following format:
A_{1, 1} A_{1, 2} A_{1, 3}
A_{2, 1} A_{2, 2} A_{2, 3}
A_{3, 1} A_{3, 2} A_{3, 3}
N
b_1
\vdots
b_N

-----Output-----
If we will have a bingo, print Yes; otherwise, print No.

-----Sample Input-----
84 97 66
79 89 11
61 59 7
7
89
7
87
79
24
84
30

-----Sample Output-----
Yes

We will mark A_{1, 1}, A_{2, 1}, A_{2, 2}, A_{3, 3}, and complete the diagonal from the top-left to the bottom-right.
user: Takahashi has N days of summer vacation.
His teacher gave him M summer assignments. It will take A_i days for him to do the i-th assignment.
He cannot do multiple assignments on the same day, or hang out on a day he does an assignment.
What is the maximum number of days Takahashi can hang out during the vacation if he finishes all the assignments during this vacation?
If Takahashi cannot finish all the assignments during the vacation, print -1 instead.

-----Constraints-----
 - 1 \leq N \leq 10^6
 - 1 \leq M \leq 10^4
 - 1 \leq A_i \leq 10^4

-----Input-----
Input is given from Standard Input in the following format:
N M
A_1 ... A_M

-----Output-----
Print the maximum number of days Takahashi can hang out during the vacation, or -1.

-----Sample Input-----
41 2
5 6

-----Sample Output-----
30

For example, he can do the first assignment on the first 5 days, hang out on the next 30 days, and do the second assignment on the last 6 days of the vacation. In this way, he can safely spend 30 days hanging out.
user: Today, the memorable AtCoder Beginner Contest 100 takes place. On this occasion, Takahashi would like to give an integer to Ringo.

As the name of the contest is AtCoder Beginner Contest 100, Ringo would be happy if he is given a positive integer that can be divided by 100 exactly D times.
Find the N-th smallest integer that would make Ringo happy.

-----Constraints-----
 - D is 0, 1 or 2.
 - N is an integer between 1 and 100 (inclusive).

-----Input-----
Input is given from Standard Input in the following format:
D N

-----Output-----
Print the N-th smallest integer that can be divided by 100 exactly D times.

-----Sample Input-----
0 5

-----Sample Output-----
5

The integers that can be divided by 100 exactly 0 times (that is, not divisible by 100) are as follows: 1, 2, 3, 4, 5, 6, 7, ...

Thus, the 5-th smallest integer that would make Ringo happy is 5.
user: There are N integers, A_1, A_2, ..., A_N, written on the blackboard.
You will choose one of them and replace it with an integer of your choice between 1 and 10^9 (inclusive), possibly the same as the integer originally written.
Find the maximum possible greatest common divisor of the N integers on the blackboard after your move.

-----Constraints-----
 - All values in input are integers.
 - 2 \leq N \leq 10^5
 - 1 \leq A_i \leq 10^9

-----Output-----
Input is given from Standard Input in the following format:
N
A_1 A_2 ... A_N

-----Output-----
Print the maximum possible greatest common divisor of the N integers on the blackboard after your move.

-----Sample Input-----
3
7 6 8

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

If we replace 7 with 4, the greatest common divisor of the three integers on the blackboard will be 2, which is the maximum possible value.
user: Takahashi is a teacher responsible for a class of N students.
The students are given distinct student numbers from 1 to N.
Today, all the students entered the classroom at different times.
According to Takahashi's record, there were A_i students in the classroom when student number i entered the classroom (including student number i).
From these records, reconstruct the order in which the students entered the classroom.

-----Constraints-----
 -  1 \le N \le 10^5 
 -  1 \le A_i \le N 
 -  A_i \neq A_j  (i \neq j)
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N
A_1 A_2 \ldots A_N

-----Output-----
Print the student numbers of the students in the order the students entered the classroom.

-----Sample Input-----
3
2 3 1

-----Sample Output-----
3 1 2

First, student number 3 entered the classroom.
Then, student number 1 entered the classroom.
Finally, student number 2 entered the classroom.
user: Takahashi has come to an integer shop to buy an integer.
The shop sells the integers from 1 through 10^9. The integer N is sold for A \times N + B \times d(N) yen (the currency of Japan), where d(N) is the number of digits in the decimal notation of N.
Find the largest integer that Takahashi can buy when he has X yen. If no integer can be bought, print 0.

-----Constraints-----
 - All values in input are integers.
 - 1 \leq A \leq 10^9
 - 1 \leq B \leq 10^9
 - 1 \leq X \leq 10^{18}

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

-----Output-----
Print the greatest integer that Takahashi can buy. If no integer can be bought, print 0.

-----Sample Input-----
10 7 100

-----Sample Output-----
9

The integer 9 is sold for 10 \times 9 + 7 \times 1 = 97 yen, and this is the greatest integer that can be bought.
Some of the other integers are sold for the following prices:
 - 10: 10 \times 10 + 7 \times 2 = 114 yen
 - 100: 10 \times 100 + 7 \times 3 = 1021 yen
 - 12345: 10 \times 12345 + 7 \times 5 = 123485 yen
user: N friends of Takahashi has come to a theme park.
To ride the most popular roller coaster in the park, you must be at least K centimeters tall.
The i-th friend is h_i centimeters tall.
How many of the Takahashi's friends can ride the roller coaster?

-----Constraints-----
 -  1 \le N \le 10^5 
 -  1 \le K \le 500 
 -  1 \le h_i \le 500
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N K
h_1 h_2 \ldots h_N

-----Output-----
Print the number of people among the Takahashi's friends who can ride the roller coaster.

-----Sample Input-----
4 150
150 140 100 200

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

Two of them can ride the roller coaster: the first and fourth friends.
user: We have held a popularity poll for N items on sale. Item i received A_i votes.
From these N items, we will select M as popular items. However, we cannot select an item with less than \dfrac{1}{4M} of the total number of votes.
If M popular items can be selected, print Yes; otherwise, print No.

-----Constraints-----
 - 1 \leq M \leq N \leq 100
 - 1 \leq A_i \leq 1000
 - A_i are distinct.
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
N M
A_1 ... A_N

-----Output-----
If M popular items can be selected, print Yes; otherwise, print No.

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

-----Sample Output-----
Yes

There were 12 votes in total. The most popular item received 5 votes, and we can select it.
user: We have a grid of H rows and W columns of squares. The color of the square at the i-th row from the top and the j-th column from the left (1 \leq i \leq H, 1 \leq j \leq W) is given to you as a character c_{i,j}: the square is white if c_{i,j} is ., and black if c_{i,j} is #.
Consider doing the following operation:
 - Choose some number of rows (possibly zero), and some number of columns (possibly zero). Then, paint red all squares in the chosen rows and all squares in the chosen columns.
You are given a positive integer K. How many choices of rows and columns result in exactly K black squares remaining after the operation? Here, we consider two choices different when there is a row or column chosen in only one of those choices.

-----Constraints-----
 - 1 \leq H, W \leq 6
 - 1 \leq K \leq HW
 - c_{i,j} is . or #.

-----Input-----
Input is given from Standard Input in the following format:
H W K
c_{1,1}c_{1,2}...c_{1,W}
c_{2,1}c_{2,2}...c_{2,W}
:
c_{H,1}c_{H,2}...c_{H,W}

-----Output-----
Print an integer representing the number of choices of rows and columns satisfying the condition.

-----Sample Input-----
2 3 2
..#
###

-----Sample Output-----
5

Five choices below satisfy the condition.
 - The 1-st row and 1-st column
 - The 1-st row and 2-nd column
 - The 1-st row and 3-rd column
 - The 1-st and 2-nd column
 - The 3-rd column
user: You are given two non-negative integers L and R.
We will choose two integers i and j such that L \leq i < j \leq R.
Find the minimum possible value of (i \times j) \mbox{ mod } 2019.

-----Constraints-----
 - All values in input are integers.
 - 0 \leq L < R \leq 2 \times 10^9

-----Input-----
Input is given from Standard Input in the following format:
L R

-----Output-----
Print the minimum possible value of (i \times j) \mbox{ mod } 2019 when i and j are chosen under the given condition.

-----Sample Input-----
2020 2040

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

When (i, j) = (2020, 2021), (i \times j) \mbox{ mod } 2019  = 2.
user: You are given a string S. Each character of S is uppercase or lowercase English letter.
Determine if S satisfies all of the following conditions:
 - The initial character of S is an uppercase A.
 - There is exactly one occurrence of C between the third character from the beginning and the second to last character (inclusive).
 - All letters except the A and C mentioned above are lowercase.

-----Constraints-----
 - 4 ≤ |S| ≤ 10 (|S| is the length of the string S.)
 - Each character of S is uppercase or lowercase English letter.

-----Input-----
Input is given from Standard Input in the following format:
S

-----Output-----
If S satisfies all of the conditions in the problem statement, print AC; otherwise, print WA.

-----Sample Input-----
AtCoder

-----Sample Output-----
AC

The first letter is A, the third letter is C and the remaining letters are all lowercase, so all the conditions are satisfied.
user: Mr. Infinity has a string S consisting of digits from 1 to 9. Each time the date changes, this string changes as follows:
 - Each occurrence of 2 in S is replaced with 22. Similarly, each 3 becomes 333, 4 becomes 4444, 5 becomes 55555, 6 becomes 666666, 7 becomes 7777777, 8 becomes 88888888 and 9 becomes 999999999. 1 remains as 1.
For example, if S is 1324, it becomes 1333224444 the next day, and it becomes 133333333322224444444444444444 the day after next.
You are interested in what the string looks like after 5 \times 10^{15} days. What is the K-th character from the left in the string after 5 \times 10^{15} days?

-----Constraints-----
 - S is a string of length between 1 and 100 (inclusive).
 - K is an integer between 1 and 10^{18} (inclusive).
 - The length of the string after 5 \times 10^{15} days is at least K.

-----Input-----
Input is given from Standard Input in the following format:
S
K

-----Output-----
Print the K-th character from the left in Mr. Infinity's string after 5 \times 10^{15} days.

-----Sample Input-----
1214
4

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

The string S changes as follows:  
 - Now: 1214
 - After one day: 12214444
 - After two days: 1222214444444444444444
 - After three days: 12222222214444444444444444444444444444444444444444444444444444444444444444
The first five characters in the string after 5 \times 10^{15} days is 12222. As K=4, we should print the fourth character, 2.
user: We have a sequence p = {p_1,\ p_2,\ ...,\ p_N} which is a permutation of {1,\ 2,\ ...,\ N}.
You can perform the following operation at most once: choose integers i and j (1 \leq i < j \leq N), and swap p_i and p_j. Note that you can also choose not to perform it.
Print YES if you can sort p in ascending order in this way, and NO otherwise.

-----Constraints-----
 - All values in input are integers.
 - 2 \leq N \leq 50
 - p is a permutation of {1,\ 2,\ ...,\ N}.

-----Input-----
Input is given from Standard Input in the following format:
N
p_1 p_2 ... p_N

-----Output-----
Print YES if you can sort p in ascending order in the way stated in the problem statement, and NO otherwise.

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

-----Sample Output-----
YES

You can sort p in ascending order by swapping p_1 and p_5.
user: Polycarp likes numbers that are divisible by 3.

He has a huge number $s$. Polycarp wants to cut from it the maximum number of numbers that are divisible by $3$. To do this, he makes an arbitrary number of vertical cuts between pairs of adjacent digits. As a result, after $m$ such cuts, there will be $m+1$ parts in total. Polycarp analyzes each of the obtained numbers and finds the number of those that are divisible by $3$.

For example, if the original number is $s=3121$, then Polycarp can cut it into three parts with two cuts: $3|1|21$. As a result, he will get two numbers that are divisible by $3$.

Polycarp can make an arbitrary number of vertical cuts, where each cut is made between a pair of adjacent digits. The resulting numbers cannot contain extra leading zeroes (that is, the number can begin with 0 if and only if this number is exactly one character '0'). For example, 007, 01 and 00099 are not valid numbers, but 90, 0 and 10001 are valid.

What is the maximum number of numbers divisible by $3$ that Polycarp can obtain?


-----Input-----

The first line of the input contains a positive integer $s$. The number of digits of the number $s$ is between $1$ and $2\cdot10^5$, inclusive. The first (leftmost) digit is not equal to 0.


-----Output-----

Print the maximum number of numbers divisible by $3$ that Polycarp can get by making vertical cuts in the given number $s$.


-----Examples-----
Input
3121

Output
2

Input
6

Output
1

Input
1000000000000000000000000000000000

Output
33

Input
201920181

Output
4



-----Note-----

In the first example, an example set of optimal cuts on the number is 3|1|21.

In the second example, you do not need to make any cuts. The specified number 6 forms one number that is divisible by $3$.

In the third example, cuts must be made between each pair of digits. As a result, Polycarp gets one digit 1 and $33$ digits 0. Each of the $33$ digits 0 forms a number that is divisible by $3$.

In the fourth example, an example set of optimal cuts is 2|0|1|9|201|81. The numbers $0$, $9$, $201$ and $81$ are divisible by $3$.
user: You are given two arrays $a$ and $b$, each contains $n$ integers.

You want to create a new array $c$ as follows: choose some real (i.e. not necessarily integer) number $d$, and then for every $i \in [1, n]$ let $c_i := d \cdot a_i + b_i$.

Your goal is to maximize the number of zeroes in array $c$. What is the largest possible answer, if you choose $d$ optimally?


-----Input-----

The first line contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of elements in both arrays.

The second line contains $n$ integers $a_1$, $a_2$, ..., $a_n$ ($-10^9 \le a_i \le 10^9$).

The third line contains $n$ integers $b_1$, $b_2$, ..., $b_n$ ($-10^9 \le b_i \le 10^9$).


-----Output-----

Print one integer — the maximum number of zeroes in array $c$, if you choose $d$ optimally.


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

Output
2

Input
3
13 37 39
1 2 3

Output
2

Input
4
0 0 0 0
1 2 3 4

Output
0

Input
3
1 2 -1
-6 -12 6

Output
3



-----Note-----

In the first example, we may choose $d = -2$.

In the second example, we may choose $d = -\frac{1}{13}$.

In the third example, we cannot obtain any zero in array $c$, no matter which $d$ we choose.

In the fourth example, we may choose $d = 6$.
user: There are $n$ left boots and $n$ right boots. Each boot has a color which is denoted as a lowercase Latin letter or a question mark ('?'). Thus, you are given two strings $l$ and $r$, both of length $n$. The character $l_i$ stands for the color of the $i$-th left boot and the character $r_i$ stands for the color of the $i$-th right boot.

A lowercase Latin letter denotes a specific color, but the question mark ('?') denotes an indefinite color. Two specific colors are compatible if they are exactly the same. An indefinite color is compatible with any (specific or indefinite) color.

For example, the following pairs of colors are compatible: ('f', 'f'), ('?', 'z'), ('a', '?') and ('?', '?'). The following pairs of colors are not compatible: ('f', 'g') and ('a', 'z').

Compute the maximum number of pairs of boots such that there is one left and one right boot in a pair and their colors are compatible.

Print the maximum number of such pairs and the pairs themselves. A boot can be part of at most one pair.


-----Input-----

The first line contains $n$ ($1 \le n \le 150000$), denoting the number of boots for each leg (i.e. the number of left boots and the number of right boots).

The second line contains the string $l$ of length $n$. It contains only lowercase Latin letters or question marks. The $i$-th character stands for the color of the $i$-th left boot.

The third line contains the string $r$ of length $n$. It contains only lowercase Latin letters or question marks. The $i$-th character stands for the color of the $i$-th right boot.


-----Output-----

Print $k$ — the maximum number of compatible left-right pairs of boots, i.e. pairs consisting of one left and one right boot which have compatible colors.

The following $k$ lines should contain pairs $a_j, b_j$ ($1 \le a_j, b_j \le n$). The $j$-th of these lines should contain the index $a_j$ of the left boot in the $j$-th pair and index $b_j$ of the right boot in the $j$-th pair. All the numbers $a_j$ should be distinct (unique), all the numbers $b_j$ should be distinct (unique).

If there are many optimal answers, print any of them.


-----Examples-----
Input
10
codeforces
dodivthree

Output
5
7 8
4 9
2 2
9 10
3 1

Input
7
abaca?b
zabbbcc

Output
5
6 5
2 3
4 6
7 4
1 2

Input
9
bambarbia
hellocode

Output
0

Input
10
code??????
??????test

Output
10
6 2
1 6
7 3
3 5
4 8
9 7
5 1
2 4
10 9
8 10
user: This problem is given in two editions, which differ exclusively in the constraints on the number $n$.

You are given an array of integers $a[1], a[2], \dots, a[n].$ A block is a sequence of contiguous (consecutive) elements $a[l], a[l+1], \dots, a[r]$ ($1 \le l \le r \le n$). Thus, a block is defined by a pair of indices $(l, r)$.

Find a set of blocks $(l_1, r_1), (l_2, r_2), \dots, (l_k, r_k)$ such that:  They do not intersect (i.e. they are disjoint). Formally, for each pair of blocks $(l_i, r_i)$ and $(l_j, r_j$) where $i \neq j$ either $r_i < l_j$ or $r_j < l_i$.  For each block the sum of its elements is the same. Formally, $$a[l_1]+a[l_1+1]+\dots+a[r_1]=a[l_2]+a[l_2+1]+\dots+a[r_2]=$$ $$\dots =$$ $$a[l_k]+a[l_k+1]+\dots+a[r_k].$$  The number of the blocks in the set is maximum. Formally, there does not exist a set of blocks $(l_1', r_1'), (l_2', r_2'), \dots, (l_{k'}', r_{k'}')$ satisfying the above two requirements with $k' > k$.  $\left. \begin{array}{|l|l|l|l|l|l|} \hline 4 & {1} & {2} & {2} & {1} & {5} & {3} \\ \hline \end{array} \right.$ The picture corresponds to the first example. Blue boxes illustrate blocks. 

Write a program to find such a set of blocks.


-----Input-----

The first line contains integer $n$ ($1 \le n \le 1500$) — the length of the given array. The second line contains the sequence of elements $a[1], a[2], \dots, a[n]$ ($-10^5 \le a_i \le 10^5$).


-----Output-----

In the first line print the integer $k$ ($1 \le k \le n$). The following $k$ lines should contain blocks, one per line. In each line print a pair of indices $l_i, r_i$ ($1 \le l_i \le r_i \le n$) — the bounds of the $i$-th block. You can print blocks in any order. If there are multiple answers, print any of them.


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

Output
3
7 7
2 3
4 5

Input
11
-5 -4 -3 -2 -1 0 1 2 3 4 5

Output
2
3 4
1 1

Input
4
1 1 1 1

Output
4
4 4
1 1
2 2
3 3