meetforever/GRPO_CL huggingface dataset:
user: Congratulations! You are now the judge of a programming contest! You’ve been put in charge of a problem, and since your problem may not have unique correct output, you’ve got to write an output checker for it.

Your problem is called “Good as Goldbach”, and it’s based on the Goldbach Conjecture (that any positive even integer greater than $3$ can be expressed as the sum of two primes). A solving program’s output should have three numbers separated by whitespace: First, a positive even integer greater than $3$ and less than or equal to $10^9$, and then two (positive) prime numbers which sum to the even number.

You must write a checker for this problem. Your checker should take the output of a contestant’s program, and determine whether or not it could possibly be correct. That is, determine if the contestant’s output consists only of three tokens separated by whitespace, the first of which is a positive even integer greater than $3$ and less than or equal to $10^9$, and the next two are positive prime integers which sum to the first. The integers should be in base ten, with no signs or leading zeros. Any amount of white space anywhere except within an integer, including blank lines, is OK. Any other output, extra characters, missing numbers, etc. should be considered incorrect.

-----Input-----
The input will consist of from $0$ to $1000$ lines. Each line consists of from $0$ to $100$ printable ASCII characters (with codes 32 through 126), or tabs.

-----Output-----
Output a single integer, which is $1$ if the input could possibly be a correct output for the “Good as Goldbach” problem, or $0$ if the input could not possibly be a correct output for the “Good as Goldbach” problem.

-----Examples-----
Sample Input 1:
10 3 7
Sample Output 1:
1

Sample Input 2:
10   3   7
Sample Output 2:
1

Sample Input 3:
314
159 265
358
Sample Output 3:
0

Sample Input 4:
22 19 3
Sample Output 4:
1

Sample Input 5:

   60
  
  29
  
      31
          
          
          
          
Sample Output 5:
1
user: For a positive integer n, let us define f(n) as the number of digits in base 10.
You are given an integer S.
Count the number of the pairs of positive integers (l, r) (l \leq r) such that f(l) + f(l + 1) + ... + f(r) = S, and find the count modulo 10^9 + 7.

-----Constraints-----
 - 1 \leq S \leq 10^8

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

-----Output-----
Print the answer.

-----Sample Input-----
1

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

There are nine pairs (l, r) that satisfies the condition: (1, 1), (2, 2), ..., (9, 9).
user: You are given $n$ integer numbers $a_1, a_2, \dots, a_n$. Consider graph on $n$ nodes, in which nodes $i$, $j$ ($i\neq j$) are connected if and only if, $a_i$ AND $a_j\neq 0$, where AND denotes the bitwise AND operation.

Find the length of the shortest cycle in this graph or determine that it doesn't have cycles at all.


-----Input-----

The first line contains one integer $n$ $(1 \le n \le 10^5)$ — number of numbers.

The second line contains $n$ integer numbers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^{18}$).


-----Output-----

If the graph doesn't have any cycles, output $-1$. Else output the length of the shortest cycle.


-----Examples-----
Input
4
3 6 28 9

Output
4
Input
5
5 12 9 16 48

Output
3
Input
4
1 2 4 8

Output
-1


-----Note-----

In the first example, the shortest cycle is $(9, 3, 6, 28)$.

In the second example, the shortest cycle is $(5, 12, 9)$.

The graph has no cycles in the third example.
user: Vadim loves decorating the Christmas tree, so he got a beautiful garland as a present. It consists of $n$ light bulbs in a single row. Each bulb has a number from $1$ to $n$ (in arbitrary order), such that all the numbers are distinct. While Vadim was solving problems, his home Carp removed some light bulbs from the garland. Now Vadim wants to put them back on.[Image]

Vadim wants to put all bulb back on the garland. Vadim defines complexity of a garland to be the number of pairs of adjacent bulbs with numbers with different parity (remainder of the division by $2$). For example, the complexity of 1 4 2 3 5 is $2$ and the complexity of 1 3 5 7 6 4 2 is $1$.

No one likes complexity, so Vadim wants to minimize the number of such pairs. Find the way to put all bulbs back on the garland, such that the complexity is as small as possible.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 100$) — the number of light bulbs on the garland.

The second line contains $n$ integers $p_1,\ p_2,\ \ldots,\ p_n$ ($0 \le p_i \le n$) — the number on the $i$-th bulb, or $0$ if it was removed.


-----Output-----

Output a single number — the minimum complexity of the garland.


-----Examples-----
Input
5
0 5 0 2 3

Output
2

Input
7
1 0 0 5 0 0 2

Output
1



-----Note-----

In the first example, one should place light bulbs as 1 5 4 2 3. In that case, the complexity would be equal to 2, because only $(5, 4)$ and $(2, 3)$ are the pairs of adjacent bulbs that have different parity.

In the second case, one of the correct answers is 1 7 3 5 6 4 2.
user: Ujan has been lazy lately, but now has decided to bring his yard to good shape. First, he decided to paint the path from his house to the gate.

The path consists of $n$ consecutive tiles, numbered from $1$ to $n$. Ujan will paint each tile in some color. He will consider the path aesthetic if for any two different tiles with numbers $i$ and $j$, such that $|j - i|$ is a divisor of $n$ greater than $1$, they have the same color. Formally, the colors of two tiles with numbers $i$ and $j$ should be the same if $|i-j| > 1$ and $n \bmod |i-j| = 0$ (where $x \bmod y$ is the remainder when dividing $x$ by $y$).

Ujan wants to brighten up space. What is the maximum number of different colors that Ujan can use, so that the path is aesthetic?


-----Input-----

The first line of input contains a single integer $n$ ($1 \leq n \leq 10^{12}$), the length of the path.


-----Output-----

Output a single integer, the maximum possible number of colors that the path can be painted in.


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

Output
2

Input
5

Output
5



-----Note-----

In the first sample, two colors is the maximum number. Tiles $1$ and $3$ should have the same color since $4 \bmod |3-1| = 0$. Also, tiles $2$ and $4$ should have the same color since $4 \bmod |4-2| = 0$.

In the second sample, all five colors can be used. [Image]
user: There are n students at Berland State University. Every student has two skills, each measured as a number: a_{i} — the programming skill and b_{i} — the sports skill.

It is announced that an Olympiad in programming and sports will be held soon. That's why Berland State University should choose two teams: one to take part in the programming track and one to take part in the sports track.

There should be exactly p students in the programming team and exactly s students in the sports team. A student can't be a member of both teams.

The university management considers that the strength of the university on the Olympiad is equal to the sum of two values: the programming team strength and the sports team strength. The strength of a team is the sum of skills of its members in the corresponding area, so the strength of the programming team is the sum of all a_{i} and the strength of the sports team is the sum of all b_{i} over corresponding team members.

Help Berland State University to compose two teams to maximize the total strength of the university on the Olympiad.


-----Input-----

The first line contains three positive integer numbers n, p and s (2 ≤ n ≤ 3000, p + s ≤ n) — the number of students, the size of the programming team and the size of the sports team.

The second line contains n positive integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 3000), where a_{i} is the programming skill of the i-th student.

The third line contains n positive integers b_1, b_2, ..., b_{n} (1 ≤ b_{i} ≤ 3000), where b_{i} is the sports skill of the i-th student.


-----Output-----

In the first line, print the the maximum strength of the university on the Olympiad. In the second line, print p numbers — the members of the programming team. In the third line, print s numbers — the members of the sports team.

The students are numbered from 1 to n as they are given in the input. All numbers printed in the second and in the third lines should be distinct and can be printed in arbitrary order.

If there are multiple solutions, print any of them.


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

Output
18
3 4 
1 5 

Input
4 2 2
10 8 8 3
10 7 9 4

Output
31
1 2 
3 4 

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

Output
23
1 3 5 
4
user: One day student Vasya was sitting on a lecture and mentioned a string s_1s_2... s_{n}, consisting of letters "a", "b" and "c" that was written on his desk. As the lecture was boring, Vasya decided to complete the picture by composing a graph G with the following properties:   G has exactly n vertices, numbered from 1 to n.  For all pairs of vertices i and j, where i ≠ j, there is an edge connecting them if and only if characters s_{i} and s_{j} are either equal or neighbouring in the alphabet. That is, letters in pairs "a"-"b" and "b"-"c" are neighbouring, while letters "a"-"c" are not. 

Vasya painted the resulting graph near the string and then erased the string. Next day Vasya's friend Petya came to a lecture and found some graph at his desk. He had heard of Vasya's adventure and now he wants to find out whether it could be the original graph G, painted by Vasya. In order to verify this, Petya needs to know whether there exists a string s, such that if Vasya used this s he would produce the given graph G.


-----Input-----

The first line of the input contains two integers n and m $(1 \leq n \leq 500,0 \leq m \leq \frac{n(n - 1)}{2})$ — the number of vertices and edges in the graph found by Petya, respectively.

Each of the next m lines contains two integers u_{i} and v_{i} (1 ≤ u_{i}, v_{i} ≤ n, u_{i} ≠ v_{i}) — the edges of the graph G. It is guaranteed, that there are no multiple edges, that is any pair of vertexes appear in this list no more than once.


-----Output-----

In the first line print "Yes" (without the quotes), if the string s Petya is interested in really exists and "No" (without the quotes) otherwise.

If the string s exists, then print it on the second line of the output. The length of s must be exactly n, it must consist of only letters "a", "b" and "c" only, and the graph built using this string must coincide with G. If there are multiple possible answers, you may print any of them.


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

Output
Yes
aa

Input
4 3
1 2
1 3
1 4

Output
No



-----Note-----

In the first sample you are given a graph made of two vertices with an edge between them. So, these vertices can correspond to both the same and adjacent letters. Any of the following strings "aa", "ab", "ba", "bb", "bc", "cb", "cc" meets the graph's conditions. 

In the second sample the first vertex is connected to all three other vertices, but these three vertices are not connected with each other. That means that they must correspond to distinct letters that are not adjacent, but that is impossible as there are only two such letters: a and c.
user: The Tower of Hanoi is a well-known mathematical puzzle. It consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.

The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:   Only one disk can be moved at a time.  Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.  No disk may be placed on top of a smaller disk. 

With three disks, the puzzle can be solved in seven moves. The minimum number of moves required to solve a Tower of Hanoi puzzle is 2^{n} - 1, where n is the number of disks. (c) Wikipedia.

SmallY's puzzle is very similar to the famous Tower of Hanoi. In the Tower of Hanoi puzzle you need to solve a puzzle in minimum number of moves, in SmallY's puzzle each move costs some money and you need to solve the same puzzle but for minimal cost. At the beginning of SmallY's puzzle all n disks are on the first rod. Moving a disk from rod i to rod j (1 ≤ i, j ≤ 3) costs t_{ij} units of money. The goal of the puzzle is to move all the disks to the third rod.

In the problem you are given matrix t and an integer n. You need to count the minimal cost of solving SmallY's puzzle, consisting of n disks.


-----Input-----

Each of the first three lines contains three integers — matrix t. The j-th integer in the i-th line is t_{ij} (1 ≤ t_{ij} ≤ 10000; i ≠ j). The following line contains a single integer n (1 ≤ n ≤ 40) — the number of disks.

It is guaranteed that for all i (1 ≤ i ≤ 3), t_{ii} = 0.


-----Output-----

Print a single integer — the minimum cost of solving SmallY's puzzle.


-----Examples-----
Input
0 1 1
1 0 1
1 1 0
3

Output
7

Input
0 2 2
1 0 100
1 2 0
3

Output
19

Input
0 2 1
1 0 100
1 2 0
5

Output
87
user: Bash wants to become a Pokemon master one day. Although he liked a lot of Pokemon, he has always been fascinated by Bulbasaur the most. Soon, things started getting serious and his fascination turned into an obsession. Since he is too young to go out and catch Bulbasaur, he came up with his own way of catching a Bulbasaur.

Each day, he takes the front page of the newspaper. He cuts out the letters one at a time, from anywhere on the front page of the newspaper to form the word "Bulbasaur" (without quotes) and sticks it on his wall. Bash is very particular about case — the first letter of "Bulbasaur" must be upper case and the rest must be lower case. By doing this he thinks he has caught one Bulbasaur. He then repeats this step on the left over part of the newspaper. He keeps doing this until it is not possible to form the word "Bulbasaur" from the newspaper.

Given the text on the front page of the newspaper, can you tell how many Bulbasaurs he will catch today?

Note: uppercase and lowercase letters are considered different.


-----Input-----

Input contains a single line containing a string s (1  ≤  |s|  ≤  10^5) — the text on the front page of the newspaper without spaces and punctuation marks. |s| is the length of the string s.

The string s contains lowercase and uppercase English letters, i.e. $s_{i} \in \{a, b, \ldots, z, A, B, \ldots, Z \}$.


-----Output-----

Output a single integer, the answer to the problem.


-----Examples-----
Input
Bulbbasaur

Output
1

Input
F

Output
0

Input
aBddulbasaurrgndgbualdBdsagaurrgndbb

Output
2



-----Note-----

In the first case, you could pick: Bulbbasaur.

In the second case, there is no way to pick even a single Bulbasaur.

In the third case, you can rearrange the string to BulbasaurBulbasauraddrgndgddgargndbb to get two words "Bulbasaur".
user: There is an H \times W grid (H vertical, W horizontal), where each square contains a lowercase English letter.
Specifically, the letter in the square at the i-th row and j-th column is equal to the j-th character in the string S_i.
Snuke can apply the following operation to this grid any number of times:
 - Choose two different rows and swap them. Or, choose two different columns and swap them.
Snuke wants this grid to be symmetric.
That is, for any 1 \leq i \leq H and 1 \leq j \leq W, the letter in the square at the i-th row and j-th column and the letter in the square at the (H + 1 - i)-th row and (W + 1 - j)-th column should be equal.
Determine if Snuke can achieve this objective.

-----Constraints-----
 - 1 \leq H \leq 12
 - 1 \leq W \leq 12
 - |S_i| = W
 - S_i consists of lowercase English letters.

-----Input-----
Input is given from Standard Input in the following format:
H W
S_1
S_2
:
S_H

-----Output-----
If Snuke can make the grid symmetric, print YES; if he cannot, print NO.

-----Sample Input-----
2 3
arc
rac

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

If the second and third columns from the left are swapped, the grid becomes symmetric, as shown in the image below:
user: There are N non-negative integers written on a blackboard. The i-th integer is A_i.
Takahashi can perform the following two kinds of operations any number of times in any order:
 - Select one integer written on the board (let this integer be X). Write 2X on the board, without erasing the selected integer.
 - Select two integers, possibly the same, written on the board (let these integers be X and Y). Write X XOR Y (XOR stands for bitwise xor) on the blackboard, without erasing the selected integers.
How many different integers not exceeding X can be written on the blackboard? We will also count the integers that are initially written on the board.
Since the answer can be extremely large, find the count modulo 998244353.

-----Constraints-----
 - 1 \leq N \leq 6
 - 1 \leq X < 2^{4000}
 - 1 \leq A_i < 2^{4000}(1\leq i\leq N)
 - All input values are integers.
 - X and A_i(1\leq i\leq N) are given in binary notation, with the most significant digit in each of them being 1.

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

-----Output-----
Print the number of different integers not exceeding X that can be written on the blackboard.

-----Sample Input-----
3 111
1111
10111
10010

-----Sample Output-----
4

Initially, 15, 23 and 18 are written on the blackboard. Among the integers not exceeding 7, four integers, 0, 3, 5 and 6, can be written.
For example, 6 can be written as follows:
 - Double 15 to write 30.
 - Take XOR of 30 and 18 to write 12.
 - Double 12 to write 24.
 - Take XOR of 30 and 24 to write 6.
user: Misha and Vanya have played several table tennis sets. Each set consists of several serves, each serve is won by one of the players, he receives one point and the loser receives nothing. Once one of the players scores exactly k points, the score is reset and a new set begins.

Across all the sets Misha scored a points in total, and Vanya scored b points. Given this information, determine the maximum number of sets they could have played, or that the situation is impossible.

Note that the game consisted of several complete sets.


-----Input-----

The first line contains three space-separated integers k, a and b (1 ≤ k ≤ 10^9, 0 ≤ a, b ≤ 10^9, a + b > 0).


-----Output-----

If the situation is impossible, print a single number -1. Otherwise, print the maximum possible number of sets.


-----Examples-----
Input
11 11 5

Output
1

Input
11 2 3

Output
-1



-----Note-----

Note that the rules of the game in this problem differ from the real table tennis game, for example, the rule of "balance" (the winning player has to be at least two points ahead to win a set) has no power within the present problem.
user: Kostya likes Codeforces contests very much. However, he is very disappointed that his solutions are frequently hacked. That's why he decided to obfuscate (intentionally make less readable) his code before upcoming contest.

To obfuscate the code, Kostya first looks at the first variable name used in his program and replaces all its occurrences with a single symbol a, then he looks at the second variable name that has not been replaced yet, and replaces all its occurrences with b, and so on. Kostya is well-mannered, so he doesn't use any one-letter names before obfuscation. Moreover, there are at most 26 unique identifiers in his programs.

You are given a list of identifiers of some program with removed spaces and line breaks. Check if this program can be a result of Kostya's obfuscation.


-----Input-----

In the only line of input there is a string S of lowercase English letters (1 ≤ |S| ≤ 500) — the identifiers of a program with removed whitespace characters.


-----Output-----

If this program can be a result of Kostya's obfuscation, print "YES" (without quotes), otherwise print "NO".


-----Examples-----
Input
abacaba

Output
YES

Input
jinotega

Output
NO



-----Note-----

In the first sample case, one possible list of identifiers would be "number string number character number string number". Here how Kostya would obfuscate the program:



 replace all occurences of number with a, the result would be "a string a character a string a",

 replace all occurences of string with b, the result would be "a b a character a b a",

 replace all occurences of character with c, the result would be "a b a c a b a",

 all identifiers have been replaced, thus the obfuscation is finished.
user: Julia is going to cook a chicken in the kitchen of her dormitory. To save energy, the stove in the kitchen automatically turns off after k minutes after turning on.

During cooking, Julia goes to the kitchen every d minutes and turns on the stove if it is turned off. While the cooker is turned off, it stays warm. The stove switches on and off instantly.

It is known that the chicken needs t minutes to be cooked on the stove, if it is turned on, and 2t minutes, if it is turned off. You need to find out, how much time will Julia have to cook the chicken, if it is considered that the chicken is cooked evenly, with constant speed when the stove is turned on and at a constant speed when it is turned off.


-----Input-----

The single line contains three integers k, d and t (1 ≤ k, d, t ≤ 10^18).


-----Output-----

Print a single number, the total time of cooking in minutes. The relative or absolute error must not exceed 10^{ - 9}.

Namely, let's assume that your answer is x and the answer of the jury is y. The checker program will consider your answer correct if $\frac{|x - y|}{\operatorname{max}(1, y)} \leq 10^{-9}$.


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

Output
6.5

Input
4 2 20

Output
20.0



-----Note-----

In the first example, the chicken will be cooked for 3 minutes on the turned on stove, after this it will be cooked for $\frac{3}{6}$. Then the chicken will be cooked for one minute on a turned off stove, it will be cooked for $\frac{1}{12}$. Thus, after four minutes the chicken will be cooked for $\frac{3}{6} + \frac{1}{12} = \frac{7}{12}$. Before the fifth minute Julia will turn on the stove and after 2.5 minutes the chicken will be ready $\frac{7}{12} + \frac{2.5}{6} = 1$.

In the second example, when the stove is turned off, Julia will immediately turn it on, so the stove will always be turned on and the chicken will be cooked in 20 minutes.