vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Another Codeforces Round has just finished! It has gathered $n$ participants, and according to the results, the expected rating change of participant $i$ is $a_i$. These rating changes are perfectly balanced — their sum is equal to $0$.

Unfortunately, due to minor technical glitches, the round is declared semi-rated. It means that all rating changes must be divided by two.

There are two conditions though:   For each participant $i$, their modified rating change $b_i$ must be integer, and as close to $\frac{a_i}{2}$ as possible. It means that either $b_i = \lfloor \frac{a_i}{2} \rfloor$ or $b_i = \lceil \frac{a_i}{2} \rceil$. In particular, if $a_i$ is even, $b_i = \frac{a_i}{2}$. Here $\lfloor x \rfloor$ denotes rounding down to the largest integer not greater than $x$, and $\lceil x \rceil$ denotes rounding up to the smallest integer not smaller than $x$.  The modified rating changes must be perfectly balanced — their sum must be equal to $0$. 

Can you help with that?


-----Input-----

The first line contains a single integer $n$ ($2 \le n \le 13\,845$), denoting the number of participants.

Each of the next $n$ lines contains a single integer $a_i$ ($-336 \le a_i \le 1164$), denoting the rating change of the $i$-th participant.

The sum of all $a_i$ is equal to $0$.


-----Output-----

Output $n$ integers $b_i$, each denoting the modified rating change of the $i$-th participant in order of input.

For any $i$, it must be true that either $b_i = \lfloor \frac{a_i}{2} \rfloor$ or $b_i = \lceil \frac{a_i}{2} \rceil$. The sum of all $b_i$ must be equal to $0$.

If there are multiple solutions, print any. We can show that a solution exists for any valid input.


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

Output
5
-2
-3

Input
7
-7
-29
0
3
24
-29
38

Output
-3
-15
0
2
12
-15
19



-----Note-----

In the first example, $b_1 = 5$, $b_2 = -3$ and $b_3 = -2$ is another correct solution.

In the second example there are $6$ possible solutions, one of them is shown in the example output.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Rajat is the newly appointed principal of the prestigious FALTU college. As a principal, he has the responsibility to ensure proper functioning of the college.
For this, he need to select some student representatives for the Students Welfare Council. There are N students in the college, numbered from 1 to N.
Also, there exist M direct friendships between a pair of students in the college. If A and B are direct friends, such a friendship will denoted by (A, B).
The friendship is Symmetric. This means that if A is a friend of B then B is a friend of  A as well.
Besides, friendship is Transitive. This means that if A is a friend of B AND B is a friend of C, then A and C are also friends. Lets call such friends the indirect friends
Also B is said to be true friend of A if A and B are direct friends i.e. there exist a pair (A,B).
Being an experienced principal and a wise diplomat, he don't wants to select representatives in a way such that two friends(direct or indirect), become the representative simultaneously.
Also he wants the maximum number of representatives to be selected for the Council. 
In order to avoid conflict among friends, he wants to select the student having the maximum number of true friends as the representative. 
Your task is to help him find the maximum number of representatives that can be selected and the id of the selected representatives.
If multiple solutions are possible, print the one having minimum ids of representatives selected.

Input Format:
Input will begin by 2 integer N and C, representing the number of students in college and the number of friendship pairs.
The following C lines contain 2 integers A and B separated by a space, denoting A is a friend of B.

Output Format: 
Print a single integer R, the number of representatives, in the first line.
Print R integers, representing each representative, in the next line separated by single space.(Sort these integers before printing).

Scoring Criteria:
30 Points: 2 ≤ N<100 and 1 ≤ A,B ≤ N and 1 ≤ C ≤ 5000
50 Points: 2 ≤ N ≤ 100000 and 1 ≤ A,B ≤ N and 1 ≤ C ≤ 1000000

SAMPLE INPUT
8 7
1 2
5 6
6 7
1 3
2 3
3 4
5 7

SAMPLE OUTPUT
3
3 5 8

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The median of $\mbox{M}$ numbers is defined as the middle number after sorting them in order if $\mbox{M}$ is odd. Or it is the average of the middle two numbers if $\mbox{M}$ is even. You start with an empty number list. Then, you can add numbers to the list, or remove existing numbers from it. After each add or remove operation, output the median.

Example: 

For a set of $M=5$ numbers $9,2,8,4,1$ the median is the third number in the sorted set $1,2,4,8,9$, which is $\begin{array}{c}4\end{array}$. Similarly, for a set of $M=4$ numbers, $5,2,10,4$, the median is the average of the second and the third element in the sorted set $2,4,5,10$, which is $(4+5)/2=4.5$.  

Input: 

The first line is an integer, $N$, that indicates the number of operations. Each of the next $N$ lines is either a x or r x. a x indicates that $\boldsymbol{x}$ is added to the set, and r x indicates that $\boldsymbol{x}$ is removed from the set.

Output: 

For each operation: If the operation is add, output the median after adding $\boldsymbol{x}$ in a single line. If the operation is remove and the number $\boldsymbol{x}$ is not in the list, output Wrong! in a single line. If the operation is remove and the number $\boldsymbol{x}$ is in the list, output the median after deleting $\boldsymbol{x}$ in a single line. (If the result is an integer DO NOT output decimal point. And if the result is a real number, DO NOT output trailing 0s.)

Note 

If your median is 3.0, print only 3. And if your median is 3.50, print only 3.5. Whenever you need to print the median and the list is empty, print Wrong!

Constraints: 

$0<N\leq10^5$


For each a x or r x, $\boldsymbol{x}$ will always be a signed integer (which will fit in 32 bits).

Sample Input:  

7  
r 1  
a 1  
a 2  
a 1  
r 1  
r 2  
r 1  

Sample Output:  

Wrong!  
1  
1.5  
1  
1.5  
1  
Wrong!

Note: As evident from the last line of the input, if after remove operation the list becomes empty, you have to print Wrong!.
$$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an integer N. Integers A and B are chosen randomly in the range [1..N]. Calculate the probability that the Greatest Common Divisor(GCD) of A and B equals to B.

-----Input-----
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. Each test case consists of a single integer N on a separate line.

-----Output-----
For each test case, output a single line containing probability as an irreducible fraction. 

-----Example-----
Input:
3
1
2
3

Output:
1/1
3/4
5/9

-----Constraints-----

1<=T<=103

1<=N<=109

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Raj was to move up through a pattern of stairs of a given number **(n)**. Help him to get to the    top using the function **stairs**.

##Keep in mind :
  * If **n<1** then return ' ' .
  * There are a lot of spaces before the stair starts except for **pattern(1)**


##Examples :
  pattern(1)

          1 1

  pattern(6)

                          1 1
                      1 2 2 1  
                  1 2 3 3 2 1
              1 2 3 4 4 3 2 1
          1 2 3 4 5 5 4 3 2 1
      1 2 3 4 5 6 6 5 4 3 2 1

pattern(12)

                                                  1 1
                                              1 2 2 1
                                          1 2 3 3 2 1
                                      1 2 3 4 4 3 2 1
                                  1 2 3 4 5 5 4 3 2 1
                              1 2 3 4 5 6 6 5 4 3 2 1
                          1 2 3 4 5 6 7 7 6 5 4 3 2 1
                      1 2 3 4 5 6 7 8 8 7 6 5 4 3 2 1
                  1 2 3 4 5 6 7 8 9 9 8 7 6 5 4 3 2 1
              1 2 3 4 5 6 7 8 9 0 0 9 8 7 6 5 4 3 2 1
          1 2 3 4 5 6 7 8 9 0 1 1 0 9 8 7 6 5 4 3 2 1
      1 2 3 4 5 6 7 8 9 0 1 2 2 1 0 9 8 7 6 5 4 3 2 1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Inna loves digit 9 very much. That's why she asked Dima to write a small number consisting of nines. But Dima must have misunderstood her and he wrote a very large number a, consisting of digits from 1 to 9.

Inna wants to slightly alter the number Dima wrote so that in the end the number contained as many digits nine as possible. In one move, Inna can choose two adjacent digits in a number which sum equals 9 and replace them by a single digit 9.

For instance, Inna can alter number 14545181 like this: 14545181 → 1945181 → 194519 → 19919. Also, she can use this method to transform number 14545181 into number 19991. Inna will not transform it into 149591 as she can get numbers 19919 and 19991 which contain more digits nine.

Dima is a programmer so he wants to find out how many distinct numbers containing as many digits nine as possible Inna can get from the written number. Help him with this challenging task.


-----Input-----

The first line of the input contains integer a (1 ≤ a ≤ 10^100000). Number a doesn't have any zeroes.


-----Output-----

In a single line print a single integer — the answer to the problem. It is guaranteed that the answer to the problem doesn't exceed 2^63 - 1.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.


-----Examples-----
Input
369727

Output
2

Input
123456789987654321

Output
1

Input
1

Output
1



-----Note-----

Notes to the samples

In the first sample Inna can get the following numbers: 369727 → 99727 → 9997, 369727 → 99727 → 9979.

In the second sample, Inna can act like this: 123456789987654321 → 12396789987654321 → 1239678998769321.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This version of the problem differs from the next one only in the constraint on n.

Note that the memory limit in this problem is lower than in others.

You have a vertical strip with n cells, numbered consecutively from 1 to n from top to bottom.

You also have a token that is initially placed in cell n. You will move the token up until it arrives at cell 1.

Let the token be in cell x > 1 at some moment. One shift of the token can have either of the following kinds: 

  * Subtraction: you choose an integer y between 1 and x-1, inclusive, and move the token from cell x to cell x - y. 
  * Floored division: you choose an integer z between 2 and x, inclusive, and move the token from cell x to cell ⌊ x/z ⌋ (x divided by z rounded down). 



Find the number of ways to move the token from cell n to cell 1 using one or more shifts, and print it modulo m. Note that if there are several ways to move the token from one cell to another in one shift, all these ways are considered distinct (check example explanation for a better understanding).

Input

The only line contains two integers n and m (2 ≤ n ≤ 2 ⋅ 10^5; 10^8 < m < 10^9; m is a prime number) — the length of the strip and the modulo.

Output

Print the number of ways to move the token from cell n to cell 1, modulo m.

Examples

Input


3 998244353


Output


5


Input


5 998244353


Output


25


Input


42 998244353


Output


793019428

Note

In the first test, there are three ways to move the token from cell 3 to cell 1 in one shift: using subtraction of y = 2, or using division by z = 2 or z = 3.

There are also two ways to move the token from cell 3 to cell 1 via cell 2: first subtract y = 1, and then either subtract y = 1 again or divide by z = 2.

Therefore, there are five ways in total.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
"We have a holiday tomorrow, its Ambedkar Jayanti" says Chotu.
"I will sleep and eat whole day!!" exclaims Motu.
"Also we don't have to attend the two class of B.S.S :p" says Chotu cheerfully.
Chotu and Motu have no idea that their chat has been overheard by a third year senior. As they love troubling the first years. They made a plan to ruin their holiday.
The plan is very naive - just take a class the next day, also they decide that the class will start at 03:00 PM so that the first years have to face the scorching heat on 
their way to class.

Yes they are pretty evil :p
 

Late night the first years receives a mail with the subject "Regarding Competitive Coding Classes". An urgent meeting has been arranged to counter this evil move of the seniors.

"After that boring lecture on Heaps who will attend the lectures" shouts someone 
"No it's a new topic we should go"
The students were confused whether to attend the class or not.
Chotu has been observing all this chaos and comes forward to explain his plan, so that each student can independently decide whether to attend the lecture or not.
"Just calculate your Willingness factor (W), it will help you decide" says Chotu. 
Everyone agrees with Chotu's plan.
Now Willingness factor is pretty hard to calculate so only a good programmar can calculate it. 
Hence you are given the responsiblility to calculate the Willingness factor for each of the student.

Each of the T student has following three attributes.
1) Energy denoted by  N.
2) Patience denoted by M.
3) Current Codechef rating K.

Let W(N, M, K) be the willingness factor.

W(N, M, K) = (Numerator / Denominator) % K 
Numerator = Fac(N + M) * Fac(N + M + 1) 
Denominator = Fac(N) * Fac(N + 1) * Fac(M) * Fac(M + 1)

Note - W(N, M, K) will always be integral i.e, (Numerator % Denominator = 0) .
Note - Fac(X) = X! = 1 * 2 * 3 * 4 * 5 .. . .. . .* X. 
Can you calculate the Willingness factor for each student.

INPUT
First line of input contains T the number of the first year students.
Next T lines contain 3 integers each N, M, K, denoting the energy, patience and the ranking of the student.
OUTPUT
For each student print the willingness factor W.

CONSTRAINTS
1 ≤ T ≤ 20
1 ≤ N ≤ M ≤ 10^5 
1 ≤ K ≤ 10^9 + 7 

SAMPLE INPUT
5
3 3 1000000007
3 3 5
5 5 12
5 5 87
5 5 95

SAMPLE OUTPUT
175
0
0
3
24

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Little Elephant loves Furik and Rubik, who he met in a small city Kremenchug.

The Little Elephant has two strings of equal length a and b, consisting only of uppercase English letters. The Little Elephant selects a pair of substrings of equal length — the first one from string a, the second one from string b. The choice is equiprobable among all possible pairs. Let's denote the substring of a as x, and the substring of b — as y. The Little Elephant gives string x to Furik and string y — to Rubik.

Let's assume that f(x, y) is the number of such positions of i (1 ≤ i ≤ |x|), that xi = yi (where |x| is the length of lines x and y, and xi, yi are the i-th characters of strings x and y, correspondingly). Help Furik and Rubik find the expected value of f(x, y).

Input

The first line contains a single integer n (1 ≤ n ≤ 2·105) — the length of strings a and b. The second line contains string a, the third line contains string b. The strings consist of uppercase English letters only. The length of both strings equals n.

Output

On a single line print a real number — the answer to the problem. The answer will be considered correct if its relative or absolute error does not exceed 10 - 6.

Examples

Input

2
AB
BA


Output

0.400000000


Input

3
AAB
CAA


Output

0.642857143

Note

Let's assume that we are given string a = a1a2... a|a|, then let's denote the string's length as |a|, and its i-th character — as ai.

A substring a[l... r] (1 ≤ l ≤ r ≤ |a|) of string a is string alal + 1... ar.

String a is a substring of string b, if there exists such pair of integers l and r (1 ≤ l ≤ r ≤ |b|), that b[l... r] = a.

Let's consider the first test sample. The first sample has 5 possible substring pairs: ("A", "B"), ("A", "A"), ("B", "B"), ("B", "A"), ("AB", "BA"). For the second and third pair value f(x, y) equals 1, for the rest it equals 0. The probability of choosing each pair equals <image>, that's why the answer is <image> · 0 +  <image> · 1 +  <image> · 1 +  <image> · 0 +  <image> · 0 =  <image> =  0.4.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a long electrical wire of length $\ell $ centimetres between two poles where birds like to sit. After a long day at work you like to watch the birds on the wire from your balcony. Some time ago you noticed that they don’t like to sit closer than $d$ centimetres from each other. In addition, they cannot sit closer than 6 centimetres to any of the poles, since there are spikes attached to the pole to keep it clean from faeces that would otherwise damage and weaken it. You start wondering how many more birds can possibly sit on the wire.

-----Task-----
Given numbers $\ell $ and $d$, how many additional birds can sit on the wire given the positions of the birds already on the wire? For the purposes of this problem we assume that the birds have zero width.

-----Input-----
The first line contains three space separated integers: the length of the wire $\ell $, distance $d$ and number of birds $n$ already sitting on the wire. The next $n$ lines contain the positions of the birds in any order. All number are integers, $1\leq \ell , d\leq 1000000000$ and $0\leq n\leq 20000$. (If you have objections to the physical plausibility of fitting that many birds on a line hanging between two poles, you may either imagine that the height of the line is 0 cm above ground level, or that the birds are ants instead.) You can assume that the birds already sitting on the wire are at least 6 cm from the poles and at least $d$ centimetres apart from each other.

-----Output-----
Output one line with one integer – the maximal number of additional birds that can possibly sit on the wire.

-----Examples-----
Sample Input:
22 2 2
11
9
Sample Output:
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In this Kata, you will be given an array of integers and your task is to return the number of arithmetic progressions of size `3` that are possible from that list. In each progression, the differences between the elements must be the same.

```
[1, 2, 3, 5, 7, 9] ==> 5
// [1, 2, 3], [1, 3, 5], [1, 5, 9], [3, 5, 7], and [5, 7, 9]
```

All inputs will be sorted. More examples in test cases. 

Good luck!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A girl named Xenia has a cupboard that looks like an arc from ahead. The arc is made of a semicircle with radius r (the cupboard's top) and two walls of height h (the cupboard's sides). The cupboard's depth is r, that is, it looks like a rectangle with base r and height h + r from the sides. The figure below shows what the cupboard looks like (the front view is on the left, the side view is on the right). [Image] 

Xenia got lots of balloons for her birthday. The girl hates the mess, so she wants to store the balloons in the cupboard. Luckily, each balloon is a sphere with radius $\frac{r}{2}$. Help Xenia calculate the maximum number of balloons she can put in her cupboard. 

You can say that a balloon is in the cupboard if you can't see any part of the balloon on the left or right view. The balloons in the cupboard can touch each other. It is not allowed to squeeze the balloons or deform them in any way. You can assume that the cupboard's walls are negligibly thin.


-----Input-----

The single line contains two integers r, h (1 ≤ r, h ≤ 10^7).


-----Output-----

Print a single integer — the maximum number of balloons Xenia can put in the cupboard.


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

Output
3

Input
1 2

Output
5

Input
2 1

Output
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mirko has chosen four integers which form an arithmetic progression. In other words, when the four numbers are sorted, then the difference between each pair of adjacent elements is constant.

As has become usual, Mirko lost one of the numbers and also is not sure whether the remaining three are in the correct (sorted) order.

Write a program that, given the three remaining numbers, finds the fourth number.

-----Input-----
The input contains 3 integers between $-100$ and $100$ on a single line, separated by single spaces.

Note: the input data will guarantee that a solution, although not necessarily unique, will always exist.

-----Output-----
Output any number which could have been the fourth number in the sequence.

-----Examples-----
Sample Input:
4 6 8
Sample Output:
10

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Anshal and his friends love watching TV series together,but Anshal has a habit of giving spoilers.In order to tackle this his friends anagrammed the list of the shows they were planning to watch.Somehow Anshal got hold of this list and started guessing the shows.Determine whether Anshal made a correct guess or not.

INPUT

The input consists of two strings S1 and S2  (the anagrammed show name and Anshal's guess).
An anagram of a string is a string obtained by permuting the letters of a string. For Example FSRDIEN and FRIENDS are anagrams of one another while KKERLOSS and SHERLOCK are not.

OUTPUT

You have to print "CORRECT" (without quotes) if S1 and S2 are anagrams or "WRONG"(without quotes) otherwise.

CONSTRAINTS
1 ≤ len(S1) , len(S2)  ≤ 10^6
The strings would consist of only letters 'A'-'Z'.

SAMPLE INPUT
FSRDIEN 
FRIENDS

SAMPLE OUTPUT
CORRECT

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N towns on a line running east-west.
The towns are numbered 1 through N, in order from west to east.
Each point on the line has a one-dimensional coordinate, and a point that is farther east has a greater coordinate value.
The coordinate of town i is X_i.
You are now at town 1, and you want to visit all the other towns.
You have two ways to travel:
 - Walk on the line.
Your fatigue level increases by A each time you travel a distance of 1, regardless of direction.
 - Teleport to any location of your choice.
Your fatigue level increases by B, regardless of the distance covered.
Find the minimum possible total increase of your fatigue level when you visit all the towns in these two ways.

-----Constraints-----
 - All input values are integers.
 - 2≤N≤10^5
 - 1≤X_i≤10^9
 - For all i(1≤i≤N-1), X_i<X_{i+1}.
 - 1≤A≤10^9
 - 1≤B≤10^9

-----Input-----
The input is given from Standard Input in the following format:
N A B
X_1 X_2 ... X_N

-----Output-----
Print the minimum possible total increase of your fatigue level when you visit all the towns.

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

-----Sample Output-----
11

From town 1, walk a distance of 1 to town 2, then teleport to town 3, then walk a distance of 2 to town 4.
The total increase of your fatigue level in this case is 2×1+5+2×2=11, which is the minimum possible value.

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