vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Spongebob and Joke

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
While Patrick was gone shopping, Spongebob decided to play a little trick on his friend. The naughty Sponge browsed through Patrick's personal stuff and found a sequence *a*1,<=*a*2,<=...,<=*a**m* of length *m*, consisting of integers from 1 to *n*, not necessarily distinct. Then he picked some sequence *f*1,<=*f*2,<=...,<=*f**n* of length *n* and for each number *a**i* got number *b**i*<==<=*f**a**i*. To finish the prank he erased the initial sequence *a**i*.

It's hard to express how sad Patrick was when he returned home from shopping! We will just say that Spongebob immediately got really sorry about what he has done and he is now trying to restore the original sequence. Help him do this or determine that this is impossible.

Input Specification:
The first line of the input contains two integers *n* and *m* (1<=≤<=*n*,<=*m*<=≤<=100<=000) — the lengths of sequences *f**i* and *b**i* respectively.

The second line contains *n* integers, determining sequence *f*1,<=*f*2,<=...,<=*f**n* (1<=≤<=*f**i*<=≤<=*n*).

The last line contains *m* integers, determining sequence *b*1,<=*b*2,<=...,<=*b**m* (1<=≤<=*b**i*<=≤<=*n*).

Output Specification:
Print "Possible" if there is exactly one sequence *a**i*, such that *b**i*<==<=*f**a**i* for all *i* from 1 to *m*. Then print *m* integers *a*1,<=*a*2,<=...,<=*a**m*.

If there are multiple suitable sequences *a**i*, print "Ambiguity".

If Spongebob has made a mistake in his calculations and no suitable sequence *a**i* exists, print "Impossible".

Demo Input:
['3 3\n3 2 1\n1 2 3\n', '3 3\n1 1 1\n1 1 1\n', '3 3\n1 2 1\n3 3 3\n']

Demo Output:
['Possible\n3 2 1 \n', 'Ambiguity\n', 'Impossible\n']

Note:
In the first sample 3 is replaced by 1 and vice versa, while 2 never changes. The answer exists and is unique.

In the second sample all numbers are replaced by 1, so it is impossible to unambiguously restore the original sequence.

In the third sample *f*<sub class="lower-index">*i*</sub> ≠ 3 for all *i*, so no sequence *a*<sub class="lower-index">*i*</sub> transforms into such *b*<sub class="lower-index">*i*</sub> and we can say for sure that Spongebob has made a mistake.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Chef has been kidnapped by aliens ( they want to utilize his excellent cooking skills :P ) and has been transported to the alien planet "ZX532". Interestingly, "ZX532" uses a different time scale which has Y AlienHours on the face of a clock (instead of the 12 hours that we have).  They also have 'X*Y' AlienMinutes (instead of the 60 that we have).  X is defined as the number of minute divisions between each hour (the earth clock has X=5).
The Chef has been forced to cook a lot of dishes by the aliens. He is short of ingredients and hence needs to go out to the market to get them. However when he returns, he makes an interesting observation. The hands of AlienClock have exactly swapped position from the time he left (the big hand and the little hand have switched)!
Given the times between which The Chef might have left and the times between which The Chef may have returned, you are supposed to find out the actual time when he left.  If there is more than one possibility, print the one that maximizes the amount of time that The Chef is out.Details of the Clock
The AlienClock is circular and has exactly 2 hands : the hour hand and the minute hand. The whole circumference of the AlienClock is divided into Y divisions , each of which is further divided into X subdivisions [ X and Y are both positive integers ]. The clock is not discrete but continuous (the hands move continuously instead of moving at certain intervals such as every second, etc.... ).

-----Input-----
First line of input contains t (1≤ t ≤ 100) - the number of test cases. Each test case contains 2 lines each. The first line contains 2 space separated integers , X and Y (same as those specified in the problem statement; X ≤ 109 and Y ≤ 109 ).
The next line contains 8 space separated integers (a,b,c,d,e,f,g,h; 0 ≤ a ≤ c < Y; 0 ≤ e ≤ g < Y; a ≤ e; 0 ≤ b,d,f,h < X*Y ): specifying the times between which The Chef might have left (a:b => a hours and b minutes TO c:d => c hours and d minutes) and the times between which The Chef may have returned (The Chef returns sometime between e:f and g:h).
The interval at which The Chef re-enters the kitchen will never start prior to the interval at which he first leaves the kitchen to purchase the ingredients.

-----Output-----
The output should contain one line for each test case specifying the time when The Chef left the kitchen. This should be in the form (h:m => h hours and m minutes). h will be an integer, and m should be rounded to 2 decimal places. In case, there is no solution possible, output -1 for that test case.

-----Example-----
Input:
3
5 12
1 0 2 0 4 0 5 0
5 12
3 30 4 0 5 0 6 0
5 12
3 0 4 0 5 0 6 0

Output:
1:20.56
-1
3:26.43

Note: Be careful with precision.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Alfi asked Roy to go for shopping with her. Witty Roy came up with a condition. He said, for each product of MRP (Maximum Retail Price) R, she'll have to pay minimum of all the prime factors of R and he himself will pay rest of the amount. Without giving it a second thought Alfi agreed. 

Now they bought N number of products. You're to find how much money did Roy had to pay for each product.

Input:

First line will contain integer N, number of products they bought.

Next N lines each will contain R, MRP of each product.

Output:

Print single integer in a new line, the amount of money Roy had to pay for each product.

Constraints:

2 ≤ N,R ≤ 1000000

Warning:
Large I/O. Be careful with certain languages.

SAMPLE INPUT
2
5
10

SAMPLE OUTPUT
0
8

Explanation

Test Case #1: Only 1 prime factor of 5 is 5 itself, so Alfi will pay all the money and hence Roy has to pay 0.

Test Case #2: Prime Factors of 10 are 2 and 5, minimum of these is 2, so Alfi pays 2 and hence Roy has to pay the rest, which is 8.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
=====Problem Statement=====
The provided code stub reads and integer, n, from STDIN. For all non-negative integers i < n, print i^2.

=====Example=====
The list of non-negative integers that are less than n = 3 is [0,1,2]. Print the square of each number on a separate line.
0
1
4

=====Input Format=====
The first and only line contains the integer, n.

=====Constraints=====
1≤n≤20

=====Output Format=====
Print lines, one corresponding to each i.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
## Task:

You have to write a function `pattern` which returns the following Pattern(See Examples) upto n number of rows. 

* Note:```Returning``` the pattern is not the same as ```Printing``` the pattern.

### Rules/Note:

* The pattern should be created using only unit digits.
* If `n < 1` then it should return "" i.e. empty string.
* `The length of each line is same`, and is equal to the number of characters in a line i.e `n`.
* Range of Parameters (for the sake of CW Compiler) :
  + `n ∈ (-50,150]`
   
### Examples:

 + pattern(8):

       88888888
       87777777
       87666666
       87655555
       87654444
       87654333
       87654322
       87654321
       
 + pattern(17):
   
       77777777777777777
       76666666666666666
       76555555555555555
       76544444444444444
       76543333333333333
       76543222222222222
       76543211111111111
       76543210000000000
       76543210999999999
       76543210988888888
       76543210987777777
       76543210987666666
       76543210987655555
       76543210987654444
       76543210987654333
       76543210987654322
       76543210987654321


[List of all my katas]("http://www.codewars.com/users/curious_db97/authored")

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Smart Beaver decided to be not only smart, but also a healthy beaver! And so he began to attend physical education classes at school X. In this school, physical education has a very creative teacher. One of his favorite warm-up exercises is throwing balls. Students line up. Each one gets a single ball in the beginning. The balls are numbered from 1 to n (by the demand of the inventory commission). [Image]  Figure 1. The initial position for n = 5.  

After receiving the balls the students perform the warm-up exercise. The exercise takes place in a few throws. For each throw the teacher chooses any two arbitrary different students who will participate in it. The selected students throw their balls to each other. Thus, after each throw the students remain in their positions, and the two balls are swapped. [Image]  Figure 2. The example of a throw.  

In this case there was a throw between the students, who were holding the 2-nd and the 4-th balls. Since the warm-up has many exercises, each of them can only continue for little time. Therefore, for each student we know the maximum number of throws he can participate in. For this lessons maximum number of throws will be 1 or 2.

Note that after all phases of the considered exercise any ball can end up with any student. Smart Beaver decided to formalize it and introduced the concept of the "ball order". The ball order is a sequence of n numbers that correspond to the order of balls in the line. The first number will match the number of the ball of the first from the left student in the line, the second number will match the ball of the second student, and so on. For example, in figure 2 the order of the balls was (1, 2, 3, 4, 5), and after the throw it was (1, 4, 3, 2, 5). Smart beaver knows the number of students and for each student he knows the maximum number of throws in which he can participate. And now he is wondering: what is the number of distinct ways of ball orders by the end of the exercise.


-----Input-----

The first line contains a single number n — the number of students in the line and the number of balls. The next line contains exactly n space-separated integers. Each number corresponds to a student in the line (the i-th number corresponds to the i-th from the left student in the line) and shows the number of throws he can participate in.

The input limits for scoring 30 points are (subproblem D1):   1 ≤ n ≤ 10. 

The input limits for scoring 70 points are (subproblems D1+D2):   1 ≤ n ≤ 500. 

The input limits for scoring 100 points are (subproblems D1+D2+D3):   1 ≤ n ≤ 1000000. 


-----Output-----

The output should contain a single integer — the number of variants of ball orders after the warm up exercise is complete. As the number can be rather large, print it modulo 1000000007 (10^9 + 7).


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

Output
120

Input
8
1 2 2 1 2 1 1 2

Output
16800

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A [Power Law](https://en.wikipedia.org/wiki/Power_law) distribution occurs whenever "a relative change in one quantity results in a proportional relative change in the other quantity." For example, if *y* = 120 when *x* = 1 and *y* = 60 when *x* = 2 (i.e. *y* halves whenever *x* doubles) then when *x* = 4, *y* = 30 and when *x* = 8, *y* = 15.


Therefore, if I give you any pair of co-ordinates (x1,y1) and (x2,y2) in a power law distribution, you can plot the entire rest of the distribution and tell me the value of *y* for any other value of *x*. 

Given a pair of co-ordinates (x1,y1) and (x2,y2) and another x co-ordinate *x3*, return the value of *y3*

```
powerLaw(x1y1, x2y2, x3)
e.g. powerLaw([1,120], [2,60], 4)
- when x = 1, y = 120
- when x = 2, y = 60
- therefore whenever x doubles, y halves
- therefore when x = 4, y = 60 * 0.5
- therfore solution = 30
```

(x1,y1) and (x2,y2) will be given as arrays. Answer should be to the nearest integer, but random tests will give you leeway of 1% of the reference solution to account for possible discrepancies from different methods.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are M chairs arranged in a line. The coordinate of the i-th chair (1 ≤ i ≤ M) is i.
N people of the Takahashi clan played too much games, and they are all suffering from backaches. They need to sit in chairs and rest, but they are particular about which chairs they sit in. Specifically, the i-th person wishes to sit in a chair whose coordinate is not greater than L_i, or not less than R_i. Naturally, only one person can sit in the same chair.
It may not be possible for all of them to sit in their favorite chairs, if nothing is done.
Aoki, who cares for the health of the people of the Takahashi clan, decides to provide additional chairs so that all of them can sit in chairs at their favorite positions.
Additional chairs can be placed at arbitrary real coordinates. Find the minimum required number of additional chairs.

-----Constraints-----
 - 1 ≤ N,M ≤ 2 × 10^5
 - 0 ≤ L_i < R_i ≤ M + 1(1 ≤ i ≤ N)
 - All input values are integers.

-----Input-----
Input is given from Standard Input in the following format:
N M
L_1 R_1
:
L_N R_N

-----Output-----
Print the minimum required number of additional chairs.

-----Sample Input-----
4 4
0 3
2 3
1 3
3 4

-----Sample Output-----
0

The four people can sit in chairs at the coordinates 3, 2, 1 and 4, respectively, and no more chair is needed.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n integers b_1, b_2, ..., b_{n} written in a row. For all i from 1 to n, values a_{i} are defined by the crows performing the following procedure:

  The crow sets a_{i} initially 0.  The crow then adds b_{i} to a_{i}, subtracts b_{i} + 1, adds the b_{i} + 2 number, and so on until the n'th number. Thus, a_{i} = b_{i} - b_{i} + 1 + b_{i} + 2 - b_{i} + 3.... 

Memory gives you the values a_1, a_2, ..., a_{n}, and he now wants you to find the initial numbers b_1, b_2, ..., b_{n} written in the row? Can you do it?


-----Input-----

The first line of the input contains a single integer n (2 ≤ n ≤ 100 000) — the number of integers written in the row.

The next line contains n, the i'th of which is a_{i} ( - 10^9 ≤ a_{i} ≤ 10^9) — the value of the i'th number.


-----Output-----

Print n integers corresponding to the sequence b_1, b_2, ..., b_{n}. It's guaranteed that the answer is unique and fits in 32-bit integer type.


-----Examples-----
Input
5
6 -4 8 -2 3

Output
2 4 6 1 3 

Input
5
3 -2 -1 5 6

Output
1 -3 4 11 6 



-----Note-----

In the first sample test, the crows report the numbers 6, - 4, 8, - 2, and 3 when he starts at indices 1, 2, 3, 4 and 5 respectively. It is easy to check that the sequence 2 4 6 1 3 satisfies the reports. For example, 6 = 2 - 4 + 6 - 1 + 3, and  - 4 = 4 - 6 + 1 - 3.

In the second sample test, the sequence 1,  - 3, 4, 11, 6 satisfies the reports. For example, 5 = 11 - 6 and 6 = 6.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
problem

N students from JOI High School are lined up in a row from east to west. The i-th student from the western end of the column is student i. Each student has a bib with one integer. Initially, the integer Ai is written on the number of student i.

There are M batons, and the batons are numbered from 1 to M. For k = 1, 2, ..., M, perform the following operations. The operation related to baton k (2 ≤ k ≤ M) is performed after the operation related to baton k -1 is completed.

1. The teacher gives the baton k to student 1.
2. Students who receive the baton pass the baton according to the following rules.
* Rule: Suppose student i receives the baton k.
* 1 ≤ i ≤ N-1: When the remainder of the integer of the number of student i divided by k is greater than the remainder of the integer of the number of student i + 1 divided by k, student i and student i + 1 exchanges the number, and student i passes the baton to student i + 1. Otherwise, student i passes the baton to student i + 1 without changing the bib.
* When i = N: Student N passes the baton to the teacher.
3. When the teacher receives the baton k from student N, the operation related to the baton k is finished.



Given the integer and the number of batons M that were originally written in the student number, write a program to find the integer of each student's number after the teacher receives the baton M from student N.

input

The input consists of 1 + N lines.

The integers N and M (1 ≤ N ≤ 100, 1 ≤ M ≤ 100) are written on the first line, separated by blanks, and represent the number of students and the number of batons, respectively.

The integer Ai (1 ≤ Ai ≤ 1000) is written on the i-th line (1 ≤ i ≤ N) of the following N lines, and represents the integer Ai first written on the number of student i.

output

The output consists of N lines. On line i (1 ≤ i ≤ N), output the integer of the number of student i after the teacher receives the baton M from student N.

Input / output example

Input example 1


6 4
3
2
8
3
1
Five


Output example 1


2
3
1
8
Five
3


Input example 2


10 6
1
2
3
Four
Five
6
7
8
9
Ten


Output example 2


6
1
2
3
Ten
Four
8
7
9
Five


Input / output example 1 has 6 students. Initially, the student numbers are 3, 2, 8, 3, 1, and 5, in that order. There are four batons.

* At the end of the operation related to baton 1, the student numbers are 3, 2, 8, 3, 1, and 5, respectively.
* At the end of the operation related to baton 2, the student numbers are 2, 8, 3, 3, 1, and 5, respectively.
* At the end of the operation related to baton 3, the student numbers are 2, 3, 3, 1, 8, and 5, respectively.
* At the end of the operation related to baton 4, the student numbers are 2, 3, 1, 8, 5, and 3 in order.



Creative Commons License

Information Olympics Japan Committee work "15th Japan Information Olympics JOI 2015/2016 Qualifying Competition Tasks"





Example

Input

6 4
3
2
8
3
1
5


Output

2
3
1
8
5
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The year 2015 is almost over.

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

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

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


-----Input-----

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


-----Output-----

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


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

Output
2

Input
2015 2015

Output
1

Input
100 105

Output
0

Input
72057594000000000 72057595000000000

Output
26



-----Note-----

In the first sample Limak's interval contains numbers 5_10 = 101_2, 6_10 = 110_2, 7_10 = 111_2, 8_10 = 1000_2, 9_10 = 1001_2 and 10_10 = 1010_2. Two of them (101_2 and 110_2) have the described property.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One day Nikita found the string containing letters "a" and "b" only. 

Nikita thinks that string is beautiful if it can be cut into 3 strings (possibly empty) without changing the order of the letters, where the 1-st and the 3-rd one contain only letters "a" and the 2-nd contains only letters "b".

Nikita wants to make the string beautiful by removing some (possibly none) of its characters, but without changing their order. What is the maximum length of the string he can get?

Input

The first line contains a non-empty string of length not greater than 5 000 containing only lowercase English letters "a" and "b". 

Output

Print a single integer — the maximum possible size of beautiful string Nikita can get.

Examples

Input

abba


Output

4

Input

bab


Output

2

Note

It the first sample the string is already beautiful.

In the second sample he needs to delete one of "b" to make it beautiful.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Sereja has a string A consisting of n lower case English letters. 

Sereja calls two strings X and Y each of length n similar if they can be made equal by applying the following operation at most once in each of them.

- Chose any two position i, j in the string (i can be equal to j too). Swap the characters at position i with character at position j.

For example strings "abcd" and "acbd" are similar, strings "ab" and "ab" are similar, but strings "abcde" and "bcdea" are not similar. Note that strings  "abc" and "cab" are also similar, as you can swap 'a' and 'c' in the first string to get "cba" and 'a' and 'b' in the second string to get "cba". 

Now Sereja is interested in finding number of ordered pairs of non similar strings X and Y such that they can be constructed from a given string A by permutation of its characters. As answer could be large, please output your answer modulo  (109 + 7).

Note 

A string s (of size n) is said to be constructed from string t (also of size n) by permutation of its characters if there exists a permutation P (of length n), such that s[i] = t[P[i]] for each i from 1 to n.

-----Input-----
- First line contain integer T - number of test cases. 
- For each of the next T lines: 
	
- Each line contains a string A as defined in the problem.

-----Output-----
For each test case, output answer modulo 1000000007 (109 + 7) in separate line. 

-----Constraints-----
- 1 ≤ T ≤  10 
- 1 ≤ n ≤  10^5 

-----Constraints-----
- Subtask #1: 1 ≤ n ≤  10  (25 points)
- Subtask #2: 1 ≤ n ≤  100  (25 points)
- Subtask #3: 1 ≤ n ≤  1000  (25 points)
- Subtask #4: original constraints (25 points)

-----Example-----
Input:
2
z
abcd

Output:
0
144

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a sequence $a_1, a_2, \dots, a_n$ consisting of $n$ integers.

You can choose any non-negative integer $D$ (i.e. $D \ge 0$), and for each $a_i$ you can:

  add $D$ (only once), i. e. perform $a_i := a_i + D$, or  subtract $D$ (only once), i. e. perform $a_i := a_i - D$, or  leave the value of $a_i$ unchanged. 

It is possible that after an operation the value $a_i$ becomes negative.

Your goal is to choose such minimum non-negative integer $D$ and perform changes in such a way, that all $a_i$ are equal (i.e. $a_1=a_2=\dots=a_n$).

Print the required $D$ or, if it is impossible to choose such value $D$, print -1.

For example, for array $[2, 8]$ the value $D=3$ is minimum possible because you can obtain the array $[5, 5]$ if you will add $D$ to $2$ and subtract $D$ from $8$. And for array $[1, 4, 7, 7]$ the value $D=3$ is also minimum possible. You can add it to $1$ and subtract it from $7$ and obtain the array $[4, 4, 4, 4]$.


-----Input-----

The first line of the input contains one integer $n$ ($1 \le n \le 100$) — the number of elements in $a$.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 100$) — the sequence $a$.


-----Output-----

Print one integer — the minimum non-negative integer value $D$ such that if you add this value to some $a_i$, subtract this value from some $a_i$ and leave some $a_i$ without changes, all obtained values become equal.

If it is impossible to choose such value $D$, print -1.


-----Examples-----
Input
6
1 4 4 7 4 1

Output
3

Input
5
2 2 5 2 5

Output
3

Input
4
1 3 3 7

Output
-1

Input
2
2 8

Output
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.