meetforever/GRPO_CL huggingface dataset:
user: Some people leave the lights at their workplaces on when they leave that is a waste of resources. As a hausmeister of DHBW, Sagheer waits till all students and professors leave the university building, then goes and turns all the lights off.

The building consists of n floors with stairs at the left and the right sides. Each floor has m rooms on the same line with a corridor that connects the left and right stairs passing by all the rooms. In other words, the building can be represented as a rectangle with n rows and m + 2 columns, where the first and the last columns represent the stairs, and the m columns in the middle represent rooms.

Sagheer is standing at the ground floor at the left stairs. He wants to turn all the lights off in such a way that he will not go upstairs until all lights in the floor he is standing at are off. Of course, Sagheer must visit a room to turn the light there off. It takes one minute for Sagheer to go to the next floor using stairs or to move from the current room/stairs to a neighboring room/stairs on the same floor. It takes no time for him to switch the light off in the room he is currently standing in. Help Sagheer find the minimum total time to turn off all the lights.

Note that Sagheer does not have to go back to his starting position, and he does not have to visit rooms where the light is already switched off.


-----Input-----

The first line contains two integers n and m (1 ≤ n ≤ 15 and 1 ≤ m ≤ 100) — the number of floors and the number of rooms in each floor, respectively.

The next n lines contains the building description. Each line contains a binary string of length m + 2 representing a floor (the left stairs, then m rooms, then the right stairs) where 0 indicates that the light is off and 1 indicates that the light is on. The floors are listed from top to bottom, so that the last line represents the ground floor.

The first and last characters of each string represent the left and the right stairs, respectively, so they are always 0.


-----Output-----

Print a single integer — the minimum total time needed to turn off all the lights.


-----Examples-----
Input
2 2
0010
0100

Output
5

Input
3 4
001000
000010
000010

Output
12

Input
4 3
01110
01110
01110
01110

Output
18



-----Note-----

In the first example, Sagheer will go to room 1 in the ground floor, then he will go to room 2 in the second floor using the left or right stairs.

In the second example, he will go to the fourth room in the ground floor, use right stairs, go to the fourth room in the second floor, use right stairs again, then go to the second room in the last floor.

In the third example, he will walk through the whole corridor alternating between the left and right stairs at each floor.
user: Medicine faculty of Berland State University has just finished their admission campaign. As usual, about $80\%$ of applicants are girls and majority of them are going to live in the university dormitory for the next $4$ (hopefully) years.

The dormitory consists of $n$ rooms and a single mouse! Girls decided to set mouse traps in some rooms to get rid of the horrible monster. Setting a trap in room number $i$ costs $c_i$ burles. Rooms are numbered from $1$ to $n$.

Mouse doesn't sit in place all the time, it constantly runs. If it is in room $i$ in second $t$ then it will run to room $a_i$ in second $t + 1$ without visiting any other rooms inbetween ($i = a_i$ means that mouse won't leave room $i$). It's second $0$ in the start. If the mouse is in some room with a mouse trap in it, then the mouse get caught into this trap.

That would have been so easy if the girls actually knew where the mouse at. Unfortunately, that's not the case, mouse can be in any room from $1$ to $n$ at second $0$.

What it the minimal total amount of burles girls can spend to set the traps in order to guarantee that the mouse will eventually be caught no matter the room it started from?


-----Input-----

The first line contains as single integers $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of rooms in the dormitory.

The second line contains $n$ integers $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^4$) — $c_i$ is the cost of setting the trap in room number $i$.

The third line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) — $a_i$ is the room the mouse will run to the next second after being in room $i$.


-----Output-----

Print a single integer — the minimal total amount of burles girls can spend to set the traps in order to guarantee that the mouse will eventually be caught no matter the room it started from.


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

Output
3

Input
4
1 10 2 10
2 4 2 2

Output
10

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

Output
2



-----Note-----

In the first example it is enough to set mouse trap in rooms $1$ and $4$. If mouse starts in room $1$ then it gets caught immideately. If mouse starts in any other room then it eventually comes to room $4$.

In the second example it is enough to set mouse trap in room $2$. If mouse starts in room $2$ then it gets caught immideately. If mouse starts in any other room then it runs to room $2$ in second $1$.

Here are the paths of the mouse from different starts from the third example:

  $1 \rightarrow 2 \rightarrow 2 \rightarrow \dots$;  $2 \rightarrow 2 \rightarrow \dots$;  $3 \rightarrow 2 \rightarrow 2 \rightarrow \dots$;  $4 \rightarrow 3 \rightarrow 2 \rightarrow 2 \rightarrow \dots$;  $5 \rightarrow 6 \rightarrow 7 \rightarrow 6 \rightarrow \dots$;  $6 \rightarrow 7 \rightarrow 6 \rightarrow \dots$;  $7 \rightarrow 6 \rightarrow 7 \rightarrow \dots$; 

So it's enough to set traps in rooms $2$ and $6$.
user: Vasya lives in a round building, whose entrances are numbered sequentially by integers from 1 to n. Entrance n and entrance 1 are adjacent.

Today Vasya got bored and decided to take a walk in the yard. Vasya lives in entrance a and he decided that during his walk he will move around the house b entrances in the direction of increasing numbers (in this order entrance n should be followed by entrance 1). The negative value of b corresponds to moving |b| entrances in the order of decreasing numbers (in this order entrance 1 is followed by entrance n). If b = 0, then Vasya prefers to walk beside his entrance. [Image] Illustration for n = 6, a = 2, b =  - 5. 

Help Vasya to determine the number of the entrance, near which he will be at the end of his walk.


-----Input-----

The single line of the input contains three space-separated integers n, a and b (1 ≤ n ≤ 100, 1 ≤ a ≤ n,  - 100 ≤ b ≤ 100) — the number of entrances at Vasya's place, the number of his entrance and the length of his walk, respectively.


-----Output-----

Print a single integer k (1 ≤ k ≤ n) — the number of the entrance where Vasya will be at the end of his walk.


-----Examples-----
Input
6 2 -5

Output
3

Input
5 1 3

Output
4

Input
3 2 7

Output
3



-----Note-----

The first example is illustrated by the picture in the statements.
user: Polycarpus develops an interesting theory about the interrelation of arithmetic progressions with just everything in the world. His current idea is that the population of the capital of Berland changes over time like an arithmetic progression. Well, or like multiple arithmetic progressions.

Polycarpus believes that if he writes out the population of the capital for several consecutive years in the sequence a_1, a_2, ..., a_{n}, then it is convenient to consider the array as several arithmetic progressions, written one after the other. For example, sequence (8, 6, 4, 2, 1, 4, 7, 10, 2) can be considered as a sequence of three arithmetic progressions (8, 6, 4, 2), (1, 4, 7, 10) and (2), which are written one after another.

Unfortunately, Polycarpus may not have all the data for the n consecutive years (a census of the population doesn't occur every year, after all). For this reason, some values of a_{i} ​​may be unknown. Such values are represented by number -1.

For a given sequence a = (a_1, a_2, ..., a_{n}), which consists of positive integers and values ​​-1, find the minimum number of arithmetic progressions Polycarpus needs to get a. To get a, the progressions need to be written down one after the other. Values ​​-1 may correspond to an arbitrary positive integer and the values a_{i} > 0 must be equal to the corresponding elements of sought consecutive record of the progressions.

Let us remind you that a finite sequence c is called an arithmetic progression if the difference c_{i} + 1 - c_{i} of any two consecutive elements in it is constant. By definition, any sequence of length 1 is an arithmetic progression.


-----Input-----

The first line of the input contains integer n (1 ≤ n ≤ 2·10^5) — the number of elements in the sequence. The second line contains integer values a_1, a_2, ..., a_{n} separated by a space (1 ≤ a_{i} ≤ 10^9 or a_{i} =  - 1).


-----Output-----

Print the minimum number of arithmetic progressions that you need to write one after another to get sequence a. The positions marked as -1 in a can be represented by any positive integers.


-----Examples-----
Input
9
8 6 4 2 1 4 7 10 2

Output
3

Input
9
-1 6 -1 2 -1 4 7 -1 2

Output
3

Input
5
-1 -1 -1 -1 -1

Output
1

Input
7
-1 -1 4 5 1 2 3

Output
2
user: High school student Vasya got a string of length n as a birthday present. This string consists of letters 'a' and 'b' only. Vasya denotes beauty of the string as the maximum length of a substring (consecutive subsequence) consisting of equal letters.

Vasya can change no more than k characters of the original string. What is the maximum beauty of the string he can achieve?


-----Input-----

The first line of the input contains two integers n and k (1 ≤ n ≤ 100 000, 0 ≤ k ≤ n) — the length of the string and the maximum number of characters to change.

The second line contains the string, consisting of letters 'a' and 'b' only.


-----Output-----

Print the only integer — the maximum beauty of the string Vasya can achieve by changing no more than k characters.


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

Output
4

Input
8 1
aabaabaa

Output
5



-----Note-----

In the first sample, Vasya can obtain both strings "aaaa" and "bbbb".

In the second sample, the optimal answer is obtained with the string "aaaaabaa" or with the string "aabaaaaa".
user: 3R2 - Standby for Action

Our dear Cafe's owner, JOE Miller, will soon take part in a new game TV-show "1 vs. $n$"!

The game goes in rounds, where in each round the host asks JOE and his opponents a common question. All participants failing to answer are eliminated. The show ends when only JOE remains (we assume that JOE never answers a question wrong!).

For each question JOE answers, if there are $s$ ($s > 0$) opponents remaining and $t$ ($0 \le t \le s$) of them make a mistake on it, JOE receives $\displaystyle\frac{t}{s}$ dollars, and consequently there will be $s - t$ opponents left for the next question.

JOE wonders what is the maximum possible reward he can receive in the best possible scenario. Yet he has little time before show starts, so can you help him answering it instead?


-----Input-----

The first and single line contains a single integer $n$ ($1 \le n \le 10^5$), denoting the number of JOE's opponents in the show.


-----Output-----

Print a number denoting the maximum prize (in dollars) JOE could have.

Your answer will be considered correct if it's absolute or relative error won't exceed $10^{-4}$. In other words, if your answer is $a$ and the jury answer is $b$, then it must hold that $\frac{|a - b|}{max(1, b)} \le 10^{-4}$.


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

Output
1.000000000000

Input
2

Output
1.500000000000



-----Note-----

In the second example, the best scenario would be: one contestant fails at the first question, the other fails at the next one. The total reward will be $\displaystyle \frac{1}{2} + \frac{1}{1} = 1.5$ dollars.
user: Santa Claus has n candies, he dreams to give them as gifts to children.

What is the maximal number of children for whose he can give candies if Santa Claus want each kid should get distinct positive integer number of candies. Santa Class wants to give all n candies he has.


-----Input-----

The only line contains positive integer number n (1 ≤ n ≤ 1000) — number of candies Santa Claus has.


-----Output-----

Print to the first line integer number k — maximal number of kids which can get candies.

Print to the second line k distinct integer numbers: number of candies for each of k kid. The sum of k printed numbers should be exactly n.

If there are many solutions, print any of them.


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

Output
2
2 3

Input
9

Output
3
3 5 1

Input
2

Output
1
2
user: The following problem is well-known: given integers n and m, calculate $2^{n} \operatorname{mod} m$, 

where 2^{n} = 2·2·...·2 (n factors), and $x \operatorname{mod} y$ denotes the remainder of division of x by y.

You are asked to solve the "reverse" problem. Given integers n and m, calculate $m \operatorname{mod} 2^{n}$. 


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 10^8).

The second line contains a single integer m (1 ≤ m ≤ 10^8).


-----Output-----

Output a single integer — the value of $m \operatorname{mod} 2^{n}$.


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

Output
10

Input
1
58

Output
0

Input
98765432
23456789

Output
23456789



-----Note-----

In the first example, the remainder of division of 42 by 2^4 = 16 is equal to 10.

In the second example, 58 is divisible by 2^1 = 2 without remainder, and the answer is 0.
user: Victor tries to write his own text editor, with word correction included. However, the rules of word correction are really strange.

Victor thinks that if a word contains two consecutive vowels, then it's kinda weird and it needs to be replaced. So the word corrector works in such a way: as long as there are two consecutive vowels in the word, it deletes the first vowel in a word such that there is another vowel right before it. If there are no two consecutive vowels in the word, it is considered to be correct.

You are given a word s. Can you predict what will it become after correction?

In this problem letters a, e, i, o, u and y are considered to be vowels.


-----Input-----

The first line contains one integer n (1 ≤ n ≤ 100) — the number of letters in word s before the correction.

The second line contains a string s consisting of exactly n lowercase Latin letters — the word before the correction.


-----Output-----

Output the word s after the correction.


-----Examples-----
Input
5
weird

Output
werd

Input
4
word

Output
word

Input
5
aaeaa

Output
a



-----Note-----

Explanations of the examples:  There is only one replace: weird $\rightarrow$ werd; No replace needed since there are no two consecutive vowels; aaeaa $\rightarrow$ aeaa $\rightarrow$ aaa $\rightarrow$ aa $\rightarrow$ a.
user: There are $n$ consecutive seat places in a railway carriage. Each place is either empty or occupied by a passenger.

The university team for the Olympiad consists of $a$ student-programmers and $b$ student-athletes. Determine the largest number of students from all $a+b$ students, which you can put in the railway carriage so that:  no student-programmer is sitting next to the student-programmer;  and no student-athlete is sitting next to the student-athlete. 

In the other words, there should not be two consecutive (adjacent) places where two student-athletes or two student-programmers are sitting.

Consider that initially occupied seat places are occupied by jury members (who obviously are not students at all).


-----Input-----

The first line contain three integers $n$, $a$ and $b$ ($1 \le n \le 2\cdot10^{5}$, $0 \le a, b \le 2\cdot10^{5}$, $a + b > 0$) — total number of seat places in the railway carriage, the number of student-programmers and the number of student-athletes.

The second line contains a string with length $n$, consisting of characters "." and "*". The dot means that the corresponding place is empty. The asterisk means that the corresponding place is occupied by the jury member.


-----Output-----

Print the largest number of students, which you can put in the railway carriage so that no student-programmer is sitting next to a student-programmer and no student-athlete is sitting next to a student-athlete.


-----Examples-----
Input
5 1 1
*...*

Output
2

Input
6 2 3
*...*.

Output
4

Input
11 3 10
.*....**.*.

Output
7

Input
3 2 3
***

Output
0



-----Note-----

In the first example you can put all student, for example, in the following way: *.AB*

In the second example you can put four students, for example, in the following way: *BAB*B

In the third example you can put seven students, for example, in the following way: B*ABAB**A*B

The letter A means a student-programmer, and the letter B — student-athlete.
user: Melody Pond was stolen from her parents as a newborn baby by Madame Kovarian, to become a weapon of the Silence in their crusade against the Doctor. Madame Kovarian changed Melody's name to River Song, giving her a new identity that allowed her to kill the Eleventh Doctor.

Heidi figured out that Madame Kovarian uses a very complicated hashing function in order to change the names of the babies she steals. In order to prevent this from happening to future Doctors, Heidi decided to prepare herself by learning some basic hashing techniques.

The first hashing function she designed is as follows.

Given two positive integers $(x, y)$ she defines $H(x,y):=x^2+2xy+x+1$.

Now, Heidi wonders if the function is reversible. That is, given a positive integer $r$, can you find a pair $(x, y)$ (of positive integers) such that $H(x, y) = r$?

If multiple such pairs exist, output the one with smallest possible $x$. If there is no such pair, output "NO".


-----Input-----

The first and only line contains an integer $r$ ($1 \le r \le 10^{12}$).


-----Output-----

Output integers $x, y$ such that $H(x,y) = r$ and $x$ is smallest possible, or "NO" if no such pair exists.


-----Examples-----
Input
19

Output
1 8

Input
16

Output
NO
user: There are quite a lot of ways to have fun with inflatable balloons. For example, you can fill them with water and see what happens.

Grigory and Andrew have the same opinion. So, once upon a time, they went to the shop and bought $n$ packets with inflatable balloons, where $i$-th of them has exactly $a_i$ balloons inside.

They want to divide the balloons among themselves. In addition, there are several conditions to hold:

  Do not rip the packets (both Grigory and Andrew should get unbroken packets);  Distribute all packets (every packet should be given to someone);  Give both Grigory and Andrew at least one packet;  To provide more fun, the total number of balloons in Grigory's packets should not be equal to the total number of balloons in Andrew's packets. 

Help them to divide the balloons or determine that it's impossible under these conditions.


-----Input-----

The first line of input contains a single integer $n$ ($1 \le n \le 10$) — the number of packets with balloons.

The second line contains $n$ integers: $a_1$, $a_2$, $\ldots$, $a_n$ ($1 \le a_i \le 1000$) — the number of balloons inside the corresponding packet.


-----Output-----

If it's impossible to divide the balloons satisfying the conditions above, print $-1$.

Otherwise, print an integer $k$ — the number of packets to give to Grigory followed by $k$ distinct integers from $1$ to $n$ — the indices of those. The order of packets doesn't matter.

If there are multiple ways to divide balloons, output any of them.


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

Output
2
1 2

Input
2
5 5

Output
-1

Input
1
10

Output
-1



-----Note-----

In the first test Grigory gets $3$ balloons in total while Andrey gets $1$.

In the second test there's only one way to divide the packets which leads to equal numbers of balloons.

In the third test one of the boys won't get a packet at all.
user: Vasya has his favourite number $n$. He wants to split it to some non-zero digits. It means, that he wants to choose some digits $d_1, d_2, \ldots, d_k$, such that $1 \leq d_i \leq 9$ for all $i$ and $d_1 + d_2 + \ldots + d_k = n$.

Vasya likes beauty in everything, so he wants to find any solution with the minimal possible number of different digits among $d_1, d_2, \ldots, d_k$. Help him!


-----Input-----

The first line contains a single integer $n$ — the number that Vasya wants to split ($1 \leq n \leq 1000$).


-----Output-----

In the first line print one integer $k$ — the number of digits in the partition. Note that $k$ must satisfy the inequality $1 \leq k \leq n$. In the next line print $k$ digits $d_1, d_2, \ldots, d_k$ separated by spaces. All digits must satisfy the inequalities $1 \leq d_i \leq 9$.

You should find a partition of $n$ in which the number of different digits among $d_1, d_2, \ldots, d_k$ will be minimal possible among all partitions of $n$ into non-zero digits. Among such partitions, it is allowed to find any. It is guaranteed that there exists at least one partition of the number $n$ into digits.


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

Output
1
1 
Input
4

Output
2
2 2

Input
27

Output
3
9 9 9



-----Note-----

In the first test, the number $1$ can be divided into $1$ digit equal to $1$.

In the second test, there are $3$ partitions of the number $4$ into digits in which the number of different digits is $1$. This partitions are $[1, 1, 1, 1]$, $[2, 2]$ and $[4]$. Any of these partitions can be found. And, for example, dividing the number $4$ to the digits $[1, 1, 2]$ isn't an answer, because it has $2$ different digits, that isn't the minimum possible number.
user: A tuple of positive integers {x_1, x_2, ..., x_{k}} is called simple if for all pairs of positive integers (i,  j) (1  ≤ i  <  j ≤ k), x_{i}  +  x_{j} is a prime.

You are given an array a with n positive integers a_1,  a_2,  ...,  a_{n} (not necessary distinct). You want to find a simple subset of the array a with the maximum size.

A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.

Let's define a subset of the array a as a tuple that can be obtained from a by removing some (possibly all) elements of it.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 1000) — the number of integers in the array a.

The second line contains n integers a_{i} (1 ≤ a_{i} ≤ 10^6) — the elements of the array a.


-----Output-----

On the first line print integer m — the maximum possible size of simple subset of a.

On the second line print m integers b_{l} — the elements of the simple subset of the array a with the maximum size.

If there is more than one solution you can print any of them. You can print the elements of the subset in any order.


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

Output
2
3 2

Input
2
2 2

Output
1
2

Input
3
2 1 1

Output
3
1 1 2

Input
2
83 14

Output
2
14 83
user: Recently Luba learned about a special kind of numbers that she calls beautiful numbers. The number is called beautiful iff its binary representation consists of k + 1 consecutive ones, and then k consecutive zeroes.

Some examples of beautiful numbers:   1_2 (1_10);  110_2 (6_10);  1111000_2 (120_10);  111110000_2 (496_10). 

More formally, the number is beautiful iff there exists some positive integer k such that the number is equal to (2^{k} - 1) * (2^{k} - 1).

Luba has got an integer number n, and she wants to find its greatest beautiful divisor. Help her to find it!


-----Input-----

The only line of input contains one number n (1 ≤ n ≤ 10^5) — the number Luba has got.


-----Output-----

Output one number — the greatest beautiful divisor of Luba's number. It is obvious that the answer always exists.


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

Output
1

Input
992

Output
496