vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Did you know that there are over 40,000 varieties of Rice in the world ? There are so many dishes that can be prepared with Rice too. A famous chef from Mumbai, Tid Gusto prepared a new dish and named it 'Tid Rice'. He posted the recipe in his newly designed blog for community voting, where a user can plus (+) or minus (-) the recipe. The final score is just the sum of all votes, where (+) and (-) are treated as +1 and -1 respectively. But, being just a chef ( and not a codechef ) he forgot to take care of multiple votes by the same user.

A user might have voted multiple times and Tid is worried that the final score shown is not the correct one. Luckily, he found the user logs, which had all the N votes in the order they arrived.  Remember that, if a user votes more than once, the user's previous vote is first nullified before the latest vote is counted ( see explanation for more clarity ). Given these records in order ( and being a codechef yourself :) ), calculate the correct final score.

------ Input ------ 

First line contains T ( number of testcases, around 20 ). T cases follow. Each test case starts with N ( total number of votes, 1 ≤ N ≤ 100 ). Each of the next N lines is of the form "userid vote" ( quotes for clarity only ), where userid is a non-empty string of lower-case alphabets ( 'a' - 'z' ) not more than 20 in length and vote is either a + or - . See the sample cases below, for more clarity.

------ Output ------ 

For each test case, output the correct final score in a new line

----- Sample Input 1 ------ 
3
4
tilak +
tilak +
tilak -
tilak +
3
ratna +
shashi -
ratna -
3
bhavani -
bhavani +
bhavani -
----- Sample Output 1 ------ 
1
-2
-1
----- explanation 1 ------ 
Case 1 : Initially score = 0. Updation of scores in the order of user tilak's votes is as follows,
( + ): +1 is added to the final score. This is the 1st vote by this user, so no previous vote to nullify. score = 1
( + ):  0 should be added ( -1 to nullify previous (+) vote, +1 to count the current (+) vote ). score = 1
( - ) : -2 should be added ( -1 to nullify previous (+) vote, -1 to count the current (-) vote ). score = -1
( + ): +2 should be added ( +1 to nullify previous (-) vote, +1 to count the current (+) vote ). score = 1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It is Professor R's last class of his teaching career. Every time Professor R taught a class, he gave a special problem for the students to solve. You being his favourite student, put your heart into solving it one last time.

You are given two polynomials $f(x) = a_0 + a_1x + \dots + a_{n-1}x^{n-1}$ and $g(x) = b_0 + b_1x + \dots + b_{m-1}x^{m-1}$, with positive integral coefficients. It is guaranteed that the cumulative GCD of the coefficients is equal to $1$ for both the given polynomials. In other words, $gcd(a_0, a_1, \dots, a_{n-1}) = gcd(b_0, b_1, \dots, b_{m-1}) = 1$. Let $h(x) = f(x)\cdot g(x)$. Suppose that $h(x) = c_0 + c_1x + \dots + c_{n+m-2}x^{n+m-2}$. 

You are also given a prime number $p$. Professor R challenges you to find any $t$ such that $c_t$ isn't divisible by $p$. He guarantees you that under these conditions such $t$ always exists. If there are several such $t$, output any of them.

As the input is quite large, please use fast input reading methods.


-----Input-----

The first line of the input contains three integers, $n$, $m$ and $p$ ($1 \leq n, m \leq 10^6, 2 \leq p \leq 10^9$),  — $n$ and $m$ are the number of terms in $f(x)$ and $g(x)$ respectively (one more than the degrees of the respective polynomials) and $p$ is the given prime number.

It is guaranteed that $p$ is prime.

The second line contains $n$ integers $a_0, a_1, \dots, a_{n-1}$ ($1 \leq a_{i} \leq 10^{9}$) — $a_i$ is the coefficient of $x^{i}$ in $f(x)$.

The third line contains $m$ integers $b_0, b_1, \dots, b_{m-1}$ ($1 \leq b_{i} \leq 10^{9}$)  — $b_i$ is the coefficient of $x^{i}$ in $g(x)$.


-----Output-----

Print a single integer $t$ ($0\le t \le n+m-2$)  — the appropriate power of $x$ in $h(x)$ whose coefficient isn't divisible by the given prime $p$. If there are multiple powers of $x$ that satisfy the condition, print any.


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

Output
1

Input
2 2 999999937
2 1
3 1

Output
2


-----Note-----

In the first test case, $f(x)$ is $2x^2 + x + 1$ and $g(x)$ is $x + 2$, their product $h(x)$ being $2x^3 + 5x^2 + 3x + 2$, so the answer can be 1 or 2 as both 3 and 5 aren't divisible by 2.

In the second test case, $f(x)$ is $x + 2$ and $g(x)$ is $x + 3$, their product $h(x)$ being $x^2 + 5x + 6$, so the answer can be any of the powers as no coefficient is divisible by the given prime.

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 **integer n**, which is the number of times that is thown a coin. You will have to return an array of string for all the possibilities (heads[H] and tails[T]). Examples:
```coin(1) should return {"H", "T"}```
```coin(2) should return {"HH", "HT", "TH", "TT"}```
```coin(3) should return {"HHH", "HHT", "HTH", "HTT", "THH", "THT", "TTH", "TTT"}```
When finished sort them alphabetically.

In C and C++ just return a ```char*``` with all elements separated by```,``` (without space):
```coin(2) should return "HH,HT,TH,TT"```
INPUT:
```0 < n < 18```
Careful with performance!! You'll have to pass 3 basic test (n = 1, n = 2, n = 3), many medium tests (3 < n <= 10) and many large tests (10 < n < 18)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
New Year is coming, and Jaehyun decided to read many books during 2015, unlike this year. He has n books numbered by integers from 1 to n. The weight of the i-th (1 ≤ i ≤ n) book is w_{i}.

As Jaehyun's house is not large enough to have a bookshelf, he keeps the n books by stacking them vertically. When he wants to read a certain book x, he follows the steps described below.  He lifts all the books above book x.  He pushes book x out of the stack.  He puts down the lifted books without changing their order.  After reading book x, he puts book x on the top of the stack. 

[Image] 

He decided to read books for m days. In the j-th (1 ≤ j ≤ m) day, he will read the book that is numbered with integer b_{j} (1 ≤ b_{j} ≤ n). To read the book, he has to use the process described in the paragraph above. It is possible that he decides to re-read the same book several times.

After making this plan, he realized that the total weight of books he should lift during m days would be too heavy. So, he decided to change the order of the stacked books before the New Year comes, and minimize the total weight. You may assume that books can be stacked in any possible order. Note that book that he is going to read on certain step isn't considered as lifted on that step. Can you help him?


-----Input-----

The first line contains two space-separated integers n (2 ≤ n ≤ 500) and m (1 ≤ m ≤ 1000) — the number of books, and the number of days for which Jaehyun would read books.

The second line contains n space-separated integers w_1, w_2, ..., w_{n} (1 ≤ w_{i} ≤ 100) — the weight of each book.

The third line contains m space separated integers b_1, b_2, ..., b_{m} (1 ≤ b_{j} ≤ n) — the order of books that he would read. Note that he can read the same book more than once.


-----Output-----

Print the minimum total weight of books he should lift, which can be achieved by rearranging the order of stacked books.


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

Output
12



-----Note-----

Here's a picture depicting the example. Each vertical column presents the stacked books. [Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Note that the only differences between easy and hard versions are the constraints on n and the time limit. You can make hacks only if all versions are solved.

Slime is interested in sequences. He defined good positive integer sequences p of length n as follows:

  * For each k>1 that presents in p, there should be at least one pair of indices i,j, such that 1 ≤ i < j ≤ n, p_i = k - 1 and p_j = k.



For the given integer n, the set of all good sequences of length n is s_n. For the fixed integer k and the sequence p, let f_p(k) be the number of times that k appears in p. For each k from 1 to n, Slime wants to know the following value:

$$$\left(∑_{p∈ s_n} f_p(k)\right)\ mod\ 998 244 353$$$

Input

The first line contains one integer n\ (1≤ n≤ 5000).

Output

Print n integers, the i-th of them should be equal to \left(∑_{p∈ s_n} f_p(i)\right)\ mod\ 998 244 353.

Examples

Input


2


Output


3 1 


Input


3


Output


10 7 1 


Input


1


Output


1 

Note

In the first example, s=\{[1,1],[1,2]\}.

In the second example, s=\{[1,1,1],[1,1,2],[1,2,1],[1,2,2],[2,1,2],[1,2,3]\}.

In the third example, s=\{[1]\}.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have found $M$ different types of jewels in a mine and each type of jewel is present in an infinite number.
There are $N$ different boxes located at position $(1 ,2 ,3 ,...N)$.
Each box can collect jewels up to a certain number ( box at position $i$ have $i$ different partitions and each partition can collect at most one jewel of any type).
Boxes at odd positions are already fully filled with jewels while boxes at even positions are completely empty.
Print the total number of different arrangements possible so that all boxes can be fully filled.
As the answer can be very large you can print it by doing modulo with 1000000007(10^9+7).

-----Input:-----
- First line will contain $T$, number of testcases. 
- Each testcase contains of a single line of input, two integers $N ,  M$. 

-----Output:-----
For each testcase, Print the total number of different arrangement.

-----Constraints-----
- $1 \leq T \leq 20000$
- $1 \leq N \leq 1e9$
- $1 \leq M \leq 1e14$

-----Sample Input:-----
2
1 10
5 2

-----Sample Output:-----
1
64

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Owl Sonya decided to become a partymaker. To train for this role she gather all her owl friends in the country house. There are m chairs located in a circle and consequently numbered with integers from 1 to m. Thus, chairs i and i + 1 are neighbouring for all i from 1 to m - 1. Chairs 1 and m are also neighbouring. Some chairs are occupied by her friends. There are n friends in total. No two friends occupy the same chair. Rules are the following:

  1. Each participant removes from the game the chair he is currently sitting on. 
  2. Each of the participants choose a direction that she will follow: clockwise (indices increase, from m goes to 1) and counter-clockwise (indices decrease, from 1 goes to m). This direction may coincide or be different for any pair of owls. 
  3. Each turn all guests move one step in the chosen directions. If some guest move to the position with a chair there, he removes this chair from the game. 
  4. Game ends if there are no more chairs left in the game. 



Owls are very busy and want to get rid of the game as soon as possible. They cooperate to pick the direction. Your goal is to find the minimum number o moves required to finish the game.

Input

The first line of the input contains a single integer m (1 ≤ m ≤ 109) — the length of the circle.

The second line contains a single integer n (1 ≤ n ≤ 100 000) — the number of friends.

Last line contains an increasing sequence of n integers ai (1 ≤ ai ≤ m) — initial positions of all owls.

Output

Print the minimum number of move required to finish the game. Note, that 0 also may be an answer.

Examples

Input

6
3
1 3 5


Output

1


Input

6
2
1 6


Output

2


Input

406
6
1 2 3 204 205 206


Output

100

Note

In the first sample, it's possible if all owls will move clockwise, i.e. in the direction of increasing indices.

In the sample, first owl has to move clockwise, while the second — counterclockwise.

In the third sample, the first and the fourth owls should move counterclockwise, while the third and the sixth — clockwise. The second and the firth may move in any direction.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The sequence of $m$ integers is called the permutation if it contains all integers from $1$ to $m$ exactly once. The number $m$ is called the length of the permutation.

Dreamoon has two permutations $p_1$ and $p_2$ of non-zero lengths $l_1$ and $l_2$.

Now Dreamoon concatenates these two permutations into another sequence $a$ of length $l_1 + l_2$. First $l_1$ elements of $a$ is the permutation $p_1$ and next $l_2$ elements of $a$ is the permutation $p_2$. 

You are given the sequence $a$, and you need to find two permutations $p_1$ and $p_2$. If there are several possible ways to restore them, you should find all of them. (Note that it is also possible that there will be no ways.)


-----Input-----

The first line contains an integer $t$ ($1 \le t \le 10\,000$) denoting the number of test cases in the input.

Each test case contains two lines. The first line contains one integer $n$ ($2 \leq n \leq 200\,000$): the length of $a$. The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq n-1$).

The total sum of $n$ is less than $200\,000$.


-----Output-----

For each test case, the first line of output should contain one integer $k$: the number of ways to divide $a$ into permutations $p_1$ and $p_2$.

Each of the next $k$ lines should contain two integers $l_1$ and $l_2$ ($1 \leq l_1, l_2 \leq n, l_1 + l_2 = n$), denoting, that it is possible to divide $a$ into two permutations of length $l_1$ and $l_2$ ($p_1$ is the first $l_1$ elements of $a$, and $p_2$ is the last $l_2$ elements of $a$). You can print solutions in any order.


-----Example-----
Input
6
5
1 4 3 2 1
6
2 4 1 3 2 1
4
2 1 1 3
4
1 3 3 1
12
2 1 3 4 5 6 7 8 9 1 10 2
3
1 1 1

Output
2
1 4
4 1
1
4 2
0
0
1
2 10
0



-----Note-----

In the first example, two possible ways to divide $a$ into permutations are $\{1\} + \{4, 3, 2, 1\}$ and $\{1,4,3,2\} + \{1\}$.

In the second example, the only way to divide $a$ into permutations is $\{2,4,1,3\} + \{2,1\}$.

In the third example, there are no possible ways.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider four numbers: $\mbox{A}$, $\mbox{B}$, $\mbox{C}$, and $\mbox{K}$. You must change at most $\mbox{K}$ bits in $\mbox{A}$ and $\mbox{B}$ to form the numbers $\mbox{A'}$ and $B^{\prime}$ satisfying the equation $A'\mid B'=C$. Here, the | symbol denotes the bitwise OR operation.

Given $Q$ sets of the numbers defined above, find and print the respective values of $\mbox{A'}$ and $B^{\prime}$ on new lines; if no such value exists, print $-1$ instead. If there are multiple solutions, make $\mbox{A'}$ as small as possible; if there are still multiple solutions, make $B^{\prime}$ as small as possible. 

Notes: 

$\mbox{A}$, $\mbox{B}$, and $\mbox{C}$ are given in Hexadecimal (base 16), and $\mbox{K}$ is given in decimal (base 10).
If the number of bits changed in $\mbox{A}$ is $k_a$ and the number of bits changed in B is $k_b$, then $k_a+k_b$ must be $\leq K$.

Input Format

The first line contains an integer, $Q$, denoting the number of queries. The subsequent lines describe each respective query as follows:

The first line contains a single integer denoting the value of $\mbox{K}$.
Each of the next $3$ lines contains a Hexadecimal (base 16) number describing the respective values of $\mbox{A}$, $\mbox{B}$, and $\mbox{C}$.

Constraints

$1\leq Q\leq5$
$0\leq K\leq5\times10^5$
$0<A,B,C<16^{5\times10^4}$

Output Format

Print two lines of output for each query:

The first line should contain a Hexadecimal (base 16) number denoting the value of $\mbox{A'}$.
The second line must contain a Hexadecimal (base 16) number denoting the value of $B^{\prime}$. 

If no valid answer exists, you must instead print one line of output with the integer $-1$.

Note: The letters in Hexadecimal numbers must be in uppercase.

Sample Input
3
8
2B
9F
58
5
B9
40
5A
2
91
BE
A8

Sample Output
8
58
18
42
-1

Explanation

Query 0: 

In this query, $K=8$. 

Change $A=(2B)_{16}$ to $A'=(8)_{16}$. $3$ bits are changed.

Change B = $(9F)_{16}$ to $B'=(58)_{16}$. $5$ bits are changed.

$A'\mid B'=(8)_{16}\mid(58)_{16}=(58)_{16}=C$

Query 1: 

In this query, $K=5$. 

Change $A=(B9)_{16}$ to $A'=(18)_{16}$. $3$ bits are changed. 

Change $B=(40)_{16}$ to $B'=(42)_{16}$. Only $1$ bit is changed.

$A'\mid B'=(18)_{16}\mid(42)_{16}=(5A)_{16}=C$

Query 2: 

There is no valid answer, so we print $-1$.

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 creates the following Pattern(See Examples) upto n(parameter) number of rows.

####Rules/Note:
* If the Argument is 0 or a Negative Integer then it should return "" i.e. empty string.
* All the lines in the pattern have same length i.e equal to the number of characters in the last line.
* Range of n is (-∞,100]

###Examples:

pattern(5):

        1    
       121   
      12321  
     1234321 
    123454321


pattern(10):

             1         
            121        
           12321       
          1234321      
         123454321     
        12345654321    
       1234567654321   
      123456787654321  
     12345678987654321 
    1234567890987654321

pattern(15):

                  1              
                 121             
                12321            
               1234321           
              123454321          
             12345654321         
            1234567654321        
           123456787654321       
          12345678987654321      
         1234567890987654321     
        123456789010987654321    
       12345678901210987654321   
      1234567890123210987654321  
     123456789012343210987654321 
    12345678901234543210987654321

pattern(20):

                       1                   
                      121                  
                     12321                 
                    1234321                
                   123454321               
                  12345654321              
                 1234567654321             
                123456787654321            
               12345678987654321           
              1234567890987654321          
             123456789010987654321         
            12345678901210987654321        
           1234567890123210987654321       
          123456789012343210987654321      
         12345678901234543210987654321     
        1234567890123456543210987654321    
       123456789012345676543210987654321   
      12345678901234567876543210987654321  
     1234567890123456789876543210987654321 
    123456789012345678909876543210987654321

###Amazing Fact: 


```Hint: Use \n in string to jump to next line```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Our Earth is so beautiful due to the various amazing colours it contains. Now on Earth day we invited Species from Mars (called Martian) Planet to celebrate it with us and to let them know our Earth. 
Martians got so much attracted with the beauty of our Earth and invited people of Earth to visit their Planet Mars.

But there is a problem People of Earth made a condition that Mars should have some of the Colours of Earth so only they will visit.

And this is not the only one problem as the Language spoken on Earth and Mars differs too.
So you have been assigned a task to help the Martians make the Mars as beautiful as Earth so we can visit there.

Your task is, you are given three Integers values of Colours Red, Green and Blue respectively. You are required to convert these values into Mars' language.

Language spoken on Mars is same as Hexadecimal Number Notation but instead of using starting letters of Alphabet they use ending letters.

For better understanding see the Sample Input and Sample Output.

INPUT:

First line contains integer T (number of Test Cases). Next T lines will contains three integers R, G & B values of Red, Green and Blue colour respectively.

OUTPUT :

Produce output for each Test Case in new line in the below depicted format as  Case x: y where x represents Test Case Number and y represents output for Test Case numbered x

CONSTRAINTS

1 ≤ T ≤ 25

0 ≤ R, G, B ≤ 255

Note :- To be Eligible for Prizes you have to register and create your home address maptag.

Click here to create your Maptag

SAMPLE INPUT
2
15 9 120
255 98 174

SAMPLE OUTPUT
Case 1: 0Z 09 78
Case 2: ZZ 62 UY

Explanation

For Case 1: R = 15 when divide by 16 gets remainder 15 which is represented by 'Z'. Note that in Hexadecimal 15 is represented by letter 'F'. 

The same process follows for all values of Case 1 & 2.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
While Grisha was celebrating New Year with Ded Moroz, Misha gifted Sasha a small rectangular pond of size *n*<=×<=*m*, divided into cells of size 1<=×<=1, inhabited by tiny evil fishes (no more than one fish per cell, otherwise they'll strife!).

The gift bundle also includes a square scoop of size *r*<=×<=*r*, designed for fishing. If the lower-left corner of the scoop-net is located at cell (*x*,<=*y*), all fishes inside the square (*x*,<=*y*)...(*x*<=+<=*r*<=-<=1,<=*y*<=+<=*r*<=-<=1) get caught. Note that the scoop-net should lie completely inside the pond when used.

Unfortunately, Sasha is not that skilled in fishing and hence throws the scoop randomly. In order to not frustrate Sasha, Misha decided to release *k* fishes into the empty pond in such a way that the expected value of the number of caught fishes is as high as possible. Help Misha! In other words, put *k* fishes in the pond into distinct cells in such a way that when the scoop-net is placed into a random position among (*n*<=-<=*r*<=+<=1)·(*m*<=-<=*r*<=+<=1) possible positions, the average number of caught fishes is as high as possible.

Input Specification:
The only line contains four integers *n*,<=*m*,<=*r*,<=*k* (1<=≤<=*n*,<=*m*<=≤<=105, 1<=≤<=*r*<=≤<=*min*(*n*,<=*m*), 1<=≤<=*k*<=≤<=*min*(*n*·*m*,<=105)).

Output Specification:
Print a single number — the maximum possible expected number of caught fishes.

You answer is considered correct, is its absolute or relative error does not exceed 10<=-<=9. Namely, let your answer be *a*, and the jury's answer be *b*. Your answer is considered correct, if .

Demo Input:
['3 3 2 3\n', '12 17 9 40\n']

Demo Output:
['2.0000000000\n', '32.8333333333\n']

Note:
In the first example you can put the fishes in cells (2, 1), (2, 2), (2, 3). In this case, for any of four possible positions of the scoop-net (highlighted with light green), the number of fishes inside is equal to two, and so is the expected value.

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