vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
East or west, home is best. That's why family reunion, the indispensable necessity of Lunar New Year celebration, is put in such a position.

After the reunion dinner, Little Tommy plays a game with the family. Here is a concise introduction to this game: 

  1. There is a sequence of n non-negative integers p1, p2, ..., pn in the beginning. It is ruled that each integer in this sequence should be non-negative at any time. 
  2. You can select two consecutive positive integers in this sequence, pi and pi + 1 (1 ≤ i < n), and then decrease them by their minimum (i. e. min(pi, pi + 1)), the cost of this operation is equal to min(pi, pi + 1). We call such operation as a descension. 
  3. The game immediately ends when there are no two consecutive positive integers. Your task is to end the game so that the total cost of your operations is as small as possible. 



Obviously, every game ends after at most n - 1 descensions. Please share your solution of this game with the lowest cost.

Input

The first line contains one integer n (1 ≤ n ≤ 3·105).

The second line contains n space-separated integers p1, p2, ..., pn (0 ≤ pi ≤ 109, i = 1, 2, ..., n).

Output

In the first line print one integer as the number of descensions m (0 ≤ m ≤ n - 1).

In the next m lines print the descensions chronologically. More precisely, in each line of the next m lines print one integer i (1 ≤ i < n) representing a descension would operate on pi and pi + 1 such that all the descensions could be utilized from top to bottom.

If there are many possible solutions to reach the minimal cost, print any of them.

Examples

Input

4
2 1 3 1


Output

2
1
3


Input

5
2 2 1 3 1


Output

3
2
1
4

Note

In the first sample, one possible best solution is <image>, of which the cost is 1 + 1 = 2.

In the second sample, one possible best solution is <image>, of which the cost is 1 + 1 + 1 = 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N one-off jobs available. If you take the i-th job and complete it, you will earn the reward of B_i after A_i days from the day you do it.

You can take and complete at most one of these jobs in a day.

However, you cannot retake a job that you have already done.

Find the maximum total reward that you can earn no later than M days from today.

You can already start working today.

Constraints

* All values in input are integers.
* 1 \leq N \leq 10^5
* 1 \leq M \leq 10^5
* 1 \leq A_i \leq 10^5
* 1 \leq B_i \leq 10^4

Input

Input is given from Standard Input in the following format:


N M
A_1 B_1
A_2 B_2
\vdots
A_N B_N


Output

Print the maximum total reward that you can earn no later than M days from today.

Examples

Input

3 4
4 3
4 1
2 2


Output

5


Input

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


Output

10


Input

1 1
2 1


Output

0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Nikolay got a string s of even length n, which consists only of lowercase Latin letters 'a' and 'b'. Its positions are numbered from 1 to n.

He wants to modify his string so that every its prefix of even length has an equal amount of letters 'a' and 'b'. To achieve that, Nikolay can perform the following operation arbitrary number of times (possibly, zero): choose some position in his string and replace the letter on this position with the other letter (i.e. replace 'a' with 'b' or replace 'b' with 'a'). Nikolay can use no letters except 'a' and 'b'.

The prefix of string s of length l (1 ≤ l ≤ n) is a string s[1..l].

For example, for the string s="abba" there are two prefixes of the even length. The first is s[1...2]="ab" and the second s[1...4]="abba". Both of them have the same number of 'a' and 'b'.

Your task is to calculate the minimum number of operations Nikolay has to perform with the string s to modify it so that every its prefix of even length has an equal amount of letters 'a' and 'b'.

Input

The first line of the input contains one even integer n (2 ≤ n ≤ 2⋅10^{5}) — the length of string s.

The second line of the input contains the string s of length n, which consists only of lowercase Latin letters 'a' and 'b'.

Output

In the first line print the minimum number of operations Nikolay has to perform with the string s to modify it so that every its prefix of even length has an equal amount of letters 'a' and 'b'.

In the second line print the string Nikolay obtains after applying all the operations. If there are multiple answers, you can print any of them.

Examples

Input


4
bbbb


Output


2
abba


Input


6
ababab


Output


0
ababab


Input


2
aa


Output


1
ba

Note

In the first example Nikolay has to perform two operations. For example, he can replace the first 'b' with 'a' and the last 'b' with 'a'. 

In the second example Nikolay doesn't need to do anything because each prefix of an even length of the initial string already contains an equal amount of letters 'a' and 'b'.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
An online contest will soon be held on ForceCoders, a large competitive programming platform. The authors have prepared $n$ problems; and since the platform is very popular, $998244351$ coder from all over the world is going to solve them.

For each problem, the authors estimated the number of people who would solve it: for the $i$-th problem, the number of accepted solutions will be between $l_i$ and $r_i$, inclusive.

The creator of ForceCoders uses different criteria to determine if the contest is good or bad. One of these criteria is the number of inversions in the problem order. An inversion is a pair of problems $(x, y)$ such that $x$ is located earlier in the contest ($x < y$), but the number of accepted solutions for $y$ is strictly greater.

Obviously, both the creator of ForceCoders and the authors of the contest want the contest to be good. Now they want to calculate the probability that there will be no inversions in the problem order, assuming that for each problem $i$, any integral number of accepted solutions for it (between $l_i$ and $r_i$) is equally probable, and all these numbers are independent.


-----Input-----

The first line contains one integer $n$ ($2 \le n \le 50$) — the number of problems in the contest.

Then $n$ lines follow, the $i$-th line contains two integers $l_i$ and $r_i$ ($0 \le l_i \le r_i \le 998244351$) — the minimum and maximum number of accepted solutions for the $i$-th problem, respectively.


-----Output-----

The probability that there will be no inversions in the contest can be expressed as an irreducible fraction $\frac{x}{y}$, where $y$ is coprime with $998244353$. Print one integer — the value of $xy^{-1}$, taken modulo $998244353$, where $y^{-1}$ is an integer such that $yy^{-1} \equiv 1$ $(mod$ $998244353)$.


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

Output
499122177

Input
2
42 1337
13 420

Output
578894053

Input
2
1 1
0 0

Output
1

Input
2
1 1
1 1

Output
1



-----Note-----

The real answer in the first test is $\frac{1}{2}$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Panda is fond of numbers. Given a number, he subtracts it with squares of any one particular digit of that number to get new numbers. This operation can be applied any number of times (possibly zero) till he obtains a pandatic number. If he is able to reach to a pandatic number then he wins. A pandatic number is a number which can be expressed in the form A^A, where A is a positive integer.  

Input Format:
The first line will contain T, the number of test cases.
Then T lines follow, each containing an integer N.  

Output Format: 
For each test case, output whether it's possible for panda to reach a pandatic number by doing the operations as described. If it's possible print "Yes" (without quotes), otherwise print "No" (without quotes).    

Constraints:
Subtask 1: (10 points)
1 ≤ T ≤ 10^3
1 ≤ N ≤ 10^3 
Subtask 2: (90 points)
1 ≤ T ≤ 10^5
1 ≤ N ≤ 10^6 

SAMPLE INPUT
3
1
3
13

SAMPLE OUTPUT
Yes
No
Yes

Explanation

Case 1: 1 is a pandatic number, hence the answer is "Yes".
Case 2: 3 is not a pandatic number, the answer for this is "No". 3 - 3^3 = -6 is also not a "pandatic number". Hence the final answer is "No".
Case 3: 13 is not a pandatic number.
13 - 1^2 = 12 is not a pandatic number. 
13 - 3^2 = 4 is a pandatic number.
.
.
.
Hence the final answer is "Yes".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have a tree with N vertices numbered 1 to N. The i-th edge in the tree connects Vertex u_i and Vertex v_i, and its length is w_i. Your objective is to paint each vertex in the tree white or black (it is fine to paint all vertices the same color) so that the following condition is satisfied:

* For any two vertices painted in the same color, the distance between them is an even number.



Find a coloring of the vertices that satisfies the condition and print it. It can be proved that at least one such coloring exists under the constraints of this problem.

Constraints

* All values in input are integers.
* 1 \leq N \leq 10^5
* 1 \leq u_i < v_i \leq N
* 1 \leq w_i \leq 10^9

Input

Input is given from Standard Input in the following format:


N
u_1 v_1 w_1
u_2 v_2 w_2
.
.
.
u_{N - 1} v_{N - 1} w_{N - 1}


Output

Print a coloring of the vertices that satisfies the condition, in N lines. The i-th line should contain `0` if Vertex i is painted white and `1` if it is painted black.

If there are multiple colorings that satisfy the condition, any of them will be accepted.

Examples

Input

3
1 2 2
2 3 1


Output

0
0
1


Input

5
2 5 2
2 3 10
1 3 8
3 4 2


Output

1
0
1
0
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Little girl Tanya climbs the stairs inside a multi-storey building. Every time Tanya climbs a stairway, she starts counting steps from $1$ to the number of steps in this stairway. She speaks every number aloud. For example, if she climbs two stairways, the first of which contains $3$ steps, and the second contains $4$ steps, she will pronounce the numbers $1, 2, 3, 1, 2, 3, 4$.

You are given all the numbers pronounced by Tanya. How many stairways did she climb? Also, output the number of steps in each stairway.

The given sequence will be a valid sequence that Tanya could have pronounced when climbing one or more stairways.


-----Input-----

The first line contains $n$ ($1 \le n \le 1000$) — the total number of numbers pronounced by Tanya.

The second line contains integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 1000$) — all the numbers Tanya pronounced while climbing the stairs, in order from the first to the last pronounced number. Passing a stairway with $x$ steps, she will pronounce the numbers $1, 2, \dots, x$ in that order.

The given sequence will be a valid sequence that Tanya could have pronounced when climbing one or more stairways.


-----Output-----

In the first line, output $t$ — the number of stairways that Tanya climbed. In the second line, output $t$ numbers — the number of steps in each stairway she climbed. Write the numbers in the correct order of passage of the stairways.


-----Examples-----
Input
7
1 2 3 1 2 3 4

Output
2
3 4 
Input
4
1 1 1 1

Output
4
1 1 1 1 
Input
5
1 2 3 4 5

Output
1
5 
Input
5
1 2 1 2 1

Output
3
2 2 1

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Leonid works for a small and promising start-up that works on decoding the human genome. His duties include solving complex problems of finding certain patterns in long strings consisting of letters 'A', 'T', 'G' and 'C'.

Let's consider the following scenario. There is a fragment of a human DNA chain, recorded as a string *S*. To analyze the fragment, you need to find all occurrences of string *T* in a string *S*. However, the matter is complicated by the fact that the original chain fragment could contain minor mutations, which, however, complicate the task of finding a fragment. Leonid proposed the following approach to solve this problem.

Let's write down integer *k*<=≥<=0 — the error threshold. We will say that string *T* occurs in string *S* on position *i* (1<=≤<=*i*<=≤<=|*S*|<=-<=|*T*|<=+<=1), if after putting string *T* along with this position, each character of string *T* corresponds to the some character of the same value in string *S* at the distance of at most *k*. More formally, for any *j* (1<=≤<=*j*<=≤<=|*T*|) there must exist such *p* (1<=≤<=*p*<=≤<=|*S*|), that |(*i*<=+<=*j*<=-<=1)<=-<=*p*|<=≤<=*k* and *S*[*p*]<==<=*T*[*j*].

For example, corresponding to the given definition, string "ACAT" occurs in string "AGCAATTCAT" in positions 2, 3 and 6.

Note that at *k*<==<=0 the given definition transforms to a simple definition of the occurrence of a string in a string.

Help Leonid by calculating in how many positions the given string *T* occurs in the given string *S* with the given error threshold.

Input Specification:
The first line contains three integers |*S*|,<=|*T*|,<=*k* (1<=≤<=|*T*|<=≤<=|*S*|<=≤<=200<=000, 0<=≤<=*k*<=≤<=200<=000) — the lengths of strings *S* and *T* and the error threshold.

The second line contains string *S*.

The third line contains string *T*.

Both strings consist only of uppercase letters 'A', 'T', 'G' and 'C'.

Output Specification:
Print a single number — the number of occurrences of *T* in *S* with the error threshold *k* by the given definition.

Demo Input:
['10 4 1\nAGCAATTCAT\nACAT\n']

Demo Output:
['3\n']

Note:
If you happen to know about the structure of the human genome a little more than the author of the problem, and you are not impressed with Leonid's original approach, do not take everything described above seriously.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n friends who want to give gifts for the New Year to each other. Each friend should give exactly one gift and receive exactly one gift. The friend cannot give the gift to himself.

For each friend the value f_i is known: it is either f_i = 0 if the i-th friend doesn't know whom he wants to give the gift to or 1 ≤ f_i ≤ n if the i-th friend wants to give the gift to the friend f_i.

You want to fill in the unknown values (f_i = 0) in such a way that each friend gives exactly one gift and receives exactly one gift and there is no friend who gives the gift to himself. It is guaranteed that the initial information isn't contradictory.

If there are several answers, you can print any.

Input

The first line of the input contains one integer n (2 ≤ n ≤ 2 ⋅ 10^5) — the number of friends.

The second line of the input contains n integers f_1, f_2, ..., f_n (0 ≤ f_i ≤ n, f_i ≠ i, all f_i ≠ 0 are distinct), where f_i is the either f_i = 0 if the i-th friend doesn't know whom he wants to give the gift to or 1 ≤ f_i ≤ n if the i-th friend wants to give the gift to the friend f_i. It is also guaranteed that there is at least two values f_i = 0.

Output

Print n integers nf_1, nf_2, ..., nf_n, where nf_i should be equal to f_i if f_i ≠ 0 or the number of friend whom the i-th friend wants to give the gift to. All values nf_i should be distinct, nf_i cannot be equal to i. Each friend gives exactly one gift and receives exactly one gift and there is no friend who gives the gift to himself.

If there are several answers, you can print any.

Examples

Input


5
5 0 0 2 4


Output


5 3 1 2 4 


Input


7
7 0 0 1 4 0 6


Output


7 3 2 1 4 5 6 


Input


7
7 4 0 3 0 5 1


Output


7 4 2 3 6 5 1 


Input


5
2 1 0 0 0


Output


2 1 4 5 3 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Dima got into number sequences. Now he's got sequence a_1, a_2, ..., a_{n}, consisting of n positive integers. Also, Dima has got a function f(x), which can be defined with the following recurrence:  f(0) = 0;  f(2·x) = f(x);  f(2·x + 1) = f(x) + 1. 

Dima wonders, how many pairs of indexes (i, j) (1 ≤ i < j ≤ n) are there, such that f(a_{i}) = f(a_{j}). Help him, count the number of such pairs. 


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^5). The second line contains n positive integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9).

The numbers in the lines are separated by single spaces.


-----Output-----

In a single line print the answer to the problem.

Please, don't use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specifier.


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

Output
3

Input
3
5 3 1

Output
1



-----Note-----

In the first sample any pair (i, j) will do, so the answer is 3.

In the second sample only pair (1, 2) will do.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: New Year and Rating

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Every Codeforces user has rating, described with one integer, possibly negative or zero. Users are divided into two divisions. The first division is for users with rating 1900 or higher. Those with rating 1899 or lower belong to the second division. In every contest, according to one's performance, his or her rating changes by some value, possibly negative or zero.

Limak competed in *n* contests in the year 2016. He remembers that in the *i*-th contest he competed in the division *d**i* (i.e. he belonged to this division just before the start of this contest) and his rating changed by *c**i* just after the contest. Note that negative *c**i* denotes the loss of rating.

What is the maximum possible rating Limak can have right now, after all *n* contests? If his rating may be arbitrarily big, print "Infinity". If there is no scenario matching the given information, print "Impossible".

Input Specification:
The first line of the input contains a single integer *n* (1<=≤<=*n*<=≤<=200<=000).

The *i*-th of next *n* lines contains two integers *c**i* and *d**i* (<=-<=100<=≤<=*c**i*<=≤<=100, 1<=≤<=*d**i*<=≤<=2), describing Limak's rating change after the *i*-th contest and his division during the *i*-th contest contest.

Output Specification:
If Limak's current rating can be arbitrarily big, print "Infinity" (without quotes). If the situation is impossible, print "Impossible" (without quotes). Otherwise print one integer, denoting the maximum possible value of Limak's current rating, i.e. rating after the *n* contests.

Demo Input:
['3\n-7 1\n5 2\n8 2\n', '2\n57 1\n22 2\n', '1\n-5 1\n', '4\n27 2\n13 1\n-50 1\n8 2\n']

Demo Output:
['1907\n', 'Impossible\n', 'Infinity\n', '1897\n']

Note:
In the first sample, the following scenario matches all information Limak remembers and has maximum possible final rating:
 -  Limak has rating 1901 and belongs to the division 1 in the first contest. His rating decreases by 7. -  With rating 1894 Limak is in the division 2. His rating increases by 5. -  Limak has rating 1899 and is still in the division 2. In the last contest of the year he gets  + 8 and ends the year with rating 1907. 
In the second sample, it's impossible that Limak is in the division 1, his rating increases by 57 and after that Limak is in the division 2 in the second contest.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
n children are standing in a circle and playing a game. Children's numbers in clockwise order form a permutation a_1, a_2, ..., a_{n} of length n. It is an integer sequence such that each integer from 1 to n appears exactly once in it.

The game consists of m steps. On each step the current leader with index i counts out a_{i} people in clockwise order, starting from the next person. The last one to be pointed at by the leader becomes the new leader.

You are given numbers l_1, l_2, ..., l_{m} — indices of leaders in the beginning of each step. Child with number l_1 is the first leader in the game. 

Write a program which will restore a possible permutation a_1, a_2, ..., a_{n}. If there are multiple solutions then print any of them. If there is no solution then print -1.


-----Input-----

The first line contains two integer numbers n, m (1 ≤ n, m ≤ 100).

The second line contains m integer numbers l_1, l_2, ..., l_{m} (1 ≤ l_{i} ≤ n) — indices of leaders in the beginning of each step.


-----Output-----

Print such permutation of n numbers a_1, a_2, ..., a_{n} that leaders in the game will be exactly l_1, l_2, ..., l_{m} if all the rules are followed. If there are multiple solutions print any of them. 

If there is no permutation which satisfies all described conditions print -1.


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

Output
3 1 2 4 

Input
3 3
3 1 2

Output
-1



-----Note-----

Let's follow leadership in the first example:   Child 2 starts.  Leadership goes from 2 to 2 + a_2 = 3.  Leadership goes from 3 to 3 + a_3 = 5. As it's greater than 4, it's going in a circle to 1.  Leadership goes from 1 to 1 + a_1 = 4.  Leadership goes from 4 to 4 + a_4 = 8. Thus in circle it still remains at 4.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It was decided in IT City to distinguish successes of local IT companies by awards in the form of stars covered with gold from one side. To order the stars it is necessary to estimate order cost that depends on the area of gold-plating. Write a program that can calculate the area of a star.

A "star" figure having n ≥ 5 corners where n is a prime number is constructed the following way. On the circle of radius r n points are selected so that the distances between the adjacent ones are equal. Then every point is connected by a segment with two maximally distant points. All areas bounded by the segments parts are the figure parts. [Image] 


-----Input-----

The only line of the input contains two integers n (5 ≤ n < 10^9, n is prime) and r (1 ≤ r ≤ 10^9) — the number of the star corners and the radius of the circumcircle correspondingly.


-----Output-----

Output one number — the star area. The relative error of your answer should not be greater than 10^{ - 7}.


-----Examples-----
Input
7 10

Output
108.395919545675

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Another Problem on Strings

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
A string is binary, if it consists only of characters "0" and "1".

String *v* is a substring of string *w* if it has a non-zero length and can be read starting from some position in string *w*. For example, string "010" has six substrings: "0", "1", "0", "01", "10", "010". Two substrings are considered different if their positions of occurrence are different. So, if some string occurs multiple times, we should consider it the number of times it occurs.

You are given a binary string *s*. Your task is to find the number of its substrings, containing exactly *k* characters "1".

Input Specification:
The first line contains the single integer *k* (0<=≤<=*k*<=≤<=106). The second line contains a non-empty binary string *s*. The length of *s* does not exceed 106 characters.

Output Specification:
Print the single number — the number of substrings of the given string, containing exactly *k* characters "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.

Demo Input:
['1\n1010\n', '2\n01010\n', '100\n01010\n']

Demo Output:
['6\n', '4\n', '0\n']

Note:
In the first sample the sought substrings are: "1", "1", "10", "01", "10", "010".

In the second sample the sought substrings are: "101", "0101", "1010", "01010".

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