vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
A tuple of positive integers (a, b, c) is said to be a *bad tuple* if a, b, c are distinct, a divides b, and b divides c. For example, (1, 2, 4) and (7, 21, 42) are bad tuples while (1, 2, 3) and (2, 4, 4) are not.

Chef has the N integers from 1 to N with him. He wants to pick a [subset] of these numbers such that it doesn't contain a *bad tuple*. How many distinct subsets can he pick?

------ Input Format ------ 

- The first and only line of input contains a single integer N, the number of available integers.

------ Output Format ------ 

Output the number of subsets that don't contain any bad tuples in them.

------ Constraints ------ 

$1 ≤ N ≤ 60$

----- Sample Input 1 ------ 
2

----- Sample Output 1 ------ 
4

----- explanation 1 ------ 

----- Sample Input 2 ------ 
4

----- Sample Output 2 ------ 
14

----- explanation 2 ------ 
Test case $1$: There are $4$ subsets in total — $\{\}$, $\{1\}$, $\{2\}$, $\{1, 2\}$. None of these subsets violate the condition.

Test case $2$: There are $16$ subsets in total, out of which $2$ subsets — $\{1, 2, 4\}$ and $\{1, 2, 3, 4\}$ — violate the given condition as they contain the bad tuple $(1, 2, 4)$ in them.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ivan places knights on infinite chessboard. Initially there are n knights. If there is free cell which is under attack of at least 4 knights then he places new knight in this cell. Ivan repeats this until there are no such free cells. One can prove that this process is finite. One can also prove that position in the end does not depend on the order in which new knights are placed.

Ivan asked you to find initial placement of exactly n knights such that in the end there will be at least ⌊ \frac{n^{2}}{10} ⌋ knights.

Input

The only line of input contains one integer n (1 ≤ n ≤ 10^{3}) — number of knights in the initial placement.

Output

Print n lines. Each line should contain 2 numbers x_{i} and y_{i} (-10^{9} ≤ x_{i},    y_{i} ≤ 10^{9}) — coordinates of i-th knight. For all i ≠ j, (x_{i},    y_{i}) ≠ (x_{j},    y_{j}) should hold. In other words, all knights should be in different cells.

It is guaranteed that the solution exists.

Examples

Input

4


Output

1 1
3 1
1 5
4 4


Input

7


Output

2 1
1 2
4 1
5 2
2 6
5 7
6 6

Note

Let's look at second example:

<image>

Green zeroes are initial knights. Cell (3,    3) is under attack of 4 knights in cells (1,    2), (2,    1), (4,    1) and (5,    2), therefore Ivan will place a knight in this cell. Cell (4,    5) is initially attacked by only 3 knights in cells (2,    6), (5,    7) and (6,    6). But new knight in cell (3,    3) also attacks cell (4,    5), now it is attacked by 4 knights and Ivan will place another knight in this cell. There are no more free cells which are attacked by 4 or more knights, so the process stops. There are 9 knights in the end, which is not less than ⌊ \frac{7^{2}}{10} ⌋ = 4.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Lunar New Year is approaching, and Bob received a gift from his friend recently — a recursive sequence! He loves this sequence very much and wants to play with it.

Let f_1, f_2, …, f_i, … be an infinite sequence of positive integers. Bob knows that for i > k, f_i can be obtained by the following recursive equation:

$$$f_i = \left(f_{i - 1} ^ {b_1} ⋅ f_{i - 2} ^ {b_2} ⋅ ⋅⋅⋅ ⋅ f_{i - k} ^ {b_k}\right) mod p,$$$

which in short is

$$$f_i = \left(∏_{j = 1}^{k} f_{i - j}^{b_j}\right) mod p,$$$

where p = 998 244 353 (a widely-used prime), b_1, b_2, …, b_k are known integer constants, and x mod y denotes the remainder of x divided by y.

Bob lost the values of f_1, f_2, …, f_k, which is extremely troublesome – these are the basis of the sequence! Luckily, Bob remembers the first k - 1 elements of the sequence: f_1 = f_2 = … = f_{k - 1} = 1 and the n-th element: f_n = m. Please find any possible value of f_k. If no solution exists, just tell Bob that it is impossible to recover his favorite sequence, regardless of Bob's sadness.

Input

The first line contains a positive integer k (1 ≤ k ≤ 100), denoting the length of the sequence b_1, b_2, …, b_k.

The second line contains k positive integers b_1, b_2, …, b_k (1 ≤ b_i < p).

The third line contains two positive integers n and m (k < n ≤ 10^9, 1 ≤ m < p), which implies f_n = m.

Output

Output a possible value of f_k, where f_k is a positive integer satisfying 1 ≤ f_k < p. If there are multiple answers, print any of them. If no such f_k makes f_n = m, output -1 instead.

It is easy to show that if there are some possible values of f_k, there must be at least one satisfying 1 ≤ f_k < p.

Examples

Input


3
2 3 5
4 16


Output


4


Input


5
4 7 1 5 6
7 14187219


Output


6


Input


8
2 3 5 6 1 7 9 10
23333 1


Output


1


Input


1
2
88888 66666


Output


-1


Input


3
998244352 998244352 998244352
4 2


Output


-1


Input


10
283 463 213 777 346 201 463 283 102 999
2333333 6263423


Output


382480067

Note

In the first sample, we have f_4 = f_3^2 ⋅ f_2^3 ⋅ f_1^5. Therefore, applying f_3 = 4, we have f_4 = 16. Note that there can be multiple answers.

In the third sample, applying f_7 = 1 makes f_{23333} = 1.

In the fourth sample, no such f_1 makes f_{88888} = 66666. Therefore, we output -1 instead.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Barney was hanging out with Nora for a while and now he thinks he may have feelings for her. Barney wants to send her a cheesy text message and wants to make her as happy as possible.

<image>

Initially, happiness level of Nora is 0. Nora loves some pickup lines like "I'm falling for you" and stuff. Totally, she knows n pickup lines, each consisting only of lowercase English letters, also some of them may be equal (in writing, but different in pronouncing or meaning though). Every time Nora sees i-th pickup line as a consecutive subsequence of Barney's text message her happiness level increases by ai. These substrings may overlap, for example, Nora will see the pickup line aa twice and the pickup line ab once in text message aaab.

Due to texting app limits, Barney's text may have up to l characters.

Barney asked you to help him make Nora as much happy as possible, it's gonna be legen...

Input

The first line of input contains two integers n and l (1 ≤ n ≤ 200, 1 ≤ l ≤ 1014) — the number of pickup lines and the maximum length of Barney's text.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 100), meaning that Nora's happiness level increases by ai after every time seeing i-th pickup line.

The next n lines contain the pickup lines. i-th of them contains a single string si consisting of only English lowercase letter. Summary length of all pickup lines does not exceed 200.

All strings are not empty.

Output

Print the only integer — the maximum possible value of Nora's happiness level after reading Barney's text.

Examples

Input

3 6
3 2 1
heart
earth
art


Output

6


Input

3 6
3 2 8
heart
earth
art


Output

16

Note

An optimal answer for the first sample case is hearth containing each pickup line exactly once.

An optimal answer for the second sample case is artart.

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
One cold winter evening Alice and her older brother Bob was sitting at home near the fireplace and giving each other interesting problems to solve. When it was Alice's turn, she told the number *n* to Bob and said:

—Shuffle the digits in this number in order to obtain the smallest possible number without leading zeroes.

—No problem! — said Bob and immediately gave her an answer.

Alice said a random number, so she doesn't know whether Bob's answer is correct. Help her to find this out, because impatient brother is waiting for the verdict.

Input Specification:
The first line contains one integer *n* (0<=≤<=*n*<=≤<=109) without leading zeroes. The second lines contains one integer *m* (0<=≤<=*m*<=≤<=109) — Bob's answer, possibly with leading zeroes.

Output Specification:
Print OK if Bob's answer is correct and WRONG_ANSWER otherwise.

Demo Input:
['3310\n1033\n', '4\n5\n']

Demo Output:
['OK\n', 'WRONG_ANSWER\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Rasta is a big fan of Kheshtaks. A Kheshtak is a rectangle that in each of it cells there is an integer.

Today rasta came up with an interesting problem, Biggest Common Subsquare  (BCS). A Kheshtak is called a Square if the number of its columns is equal to the number of its rows. A Square S is called a subsqaue of a Kheshtak A if and only if we can turn A to S by deleting some of its rows and some of its columns (maybe none).

He gives you two Kheshtaks, A and B (A one is n × m and B is x × y).

Input format
The first line of input contains n and m.

Then you are given A (n lines, in each line there are m space separated integers).

After that you are given x and y.

Then you are given B (x lines, in each line there are y space separated integers).

1 ≤ n, m, x, y ≤ 700 and all numbers in A and B are integers in the interval [1, 1000].

Output format
Print the size of BCS of A and B in a single line (size of a Square is number of its rows).

SAMPLE INPUT
3 3
1 2 0
1 2 1
1 2 3
3 3
0 1 2
1 1 2
3 1 2

SAMPLE OUTPUT
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a positive integer $n$. Since $n$ may be very large, you are given its binary representation.

You should compute the number of triples $(a,b,c)$ with $0 \leq a,b,c \leq n$ such that $a \oplus b$, $b \oplus c$, and $a \oplus c$ are the sides of a non-degenerate triangle.

Here, $\oplus$ denotes the bitwise XOR operation .

You should output the answer modulo $998\,244\,353$.

Three positive values $x$, $y$, and $z$ are the sides of a non-degenerate triangle if and only if $x+y>z$, $x+z>y$, and $y+z>x$.


-----Input-----

The first and only line contains the binary representation of an integer $n$ ($0 < n < 2^{200000}$) without leading zeros.

For example, the string 10 is the binary representation of the number $2$, while the string 1010 represents the number $10$.


-----Output-----

Print one integer — the number of triples $(a,b,c)$ satisfying the conditions described in the statement modulo $998\,244\,353$.


-----Examples-----

Input
101
Output
12
Input
1110
Output
780
Input
11011111101010010
Output
141427753


-----Note-----

In the first test case, $101_2=5$.

The triple $(a, b, c) = (0, 3, 5)$ is valid because $(a\oplus b, b\oplus c, c\oplus a) = (3, 6, 5)$ are the sides of a non-degenerate triangle.

The triple $(a, b, c) = (1, 2, 4)$ is valid because $(a\oplus b, b\oplus c, c\oplus a) = (3, 6, 5)$ are the sides of a non-degenerate triangle.

The $6$ permutations of each of these two triples are all the valid triples, thus the answer is $12$.

In the third test case, $11\,011\,111\,101\,010\,010_2=114\,514$. The full answer (before taking the modulo) is $1\,466\,408\,118\,808\,164$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Is it rated?

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Is it rated?

Here it is. The Ultimate Question of Competitive Programming, Codeforces, and Everything. And you are here to answer it.

Another Codeforces round has been conducted. No two participants have the same number of points. For each participant, from the top to the bottom of the standings, their rating before and after the round is known.

It's known that if at least one participant's rating has changed, then the round was rated for sure.

It's also known that if the round was rated and a participant with lower rating took a better place in the standings than a participant with higher rating, then at least one round participant's rating has changed.

In this problem, you should not make any other assumptions about the rating system.

Determine if the current round is rated, unrated, or it's impossible to determine whether it is rated of not.

Input Specification:
The first line contains a single integer *n* (2<=≤<=*n*<=≤<=1000) — the number of round participants.

Each of the next *n* lines contains two integers *a**i* and *b**i* (1<=≤<=*a**i*,<=*b**i*<=≤<=4126) — the rating of the *i*-th participant before and after the round, respectively. The participants are listed in order from the top to the bottom of the standings.

Output Specification:
If the round is rated for sure, print "rated". If the round is unrated for sure, print "unrated". If it's impossible to determine whether the round is rated or not, print "maybe".

Demo Input:
['6\n3060 3060\n2194 2194\n2876 2903\n2624 2624\n3007 2991\n2884 2884\n', '4\n1500 1500\n1300 1300\n1200 1200\n1400 1400\n', '5\n3123 3123\n2777 2777\n2246 2246\n2246 2246\n1699 1699\n']

Demo Output:
['rated\n', 'unrated\n', 'maybe\n']

Note:
In the first example, the ratings of the participants in the third and fifth places have changed, therefore, the round was rated.

In the second example, no one's rating has changed, but the participant in the second place has lower rating than the participant in the fourth place. Therefore, if the round was rated, someone's rating would've changed for sure.

In the third example, no one's rating has changed, and the participants took places in non-increasing order of their rating. Therefore, it's impossible to determine whether the round is rated or not.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
During the break, we decided to relax and play dominoes. Our box with Domino was empty, so we decided to borrow the teacher's dominoes.

The teacher responded instantly at our request. He put nm dominoes on the table as an n × 2m rectangle so that each of the n rows contained m dominoes arranged horizontally. Each half of each domino contained number (0 or 1).

We were taken aback, and the teacher smiled and said: "Consider some arrangement of dominoes in an n × 2m matrix. Let's count for each column of the matrix the sum of numbers in this column. Then among all such sums find the maximum one. Can you rearrange the dominoes in the matrix in such a way that the maximum sum will be minimum possible? Note that it is prohibited to change the orientation of the dominoes, they all need to stay horizontal, nevertheless dominoes are allowed to rotate by 180 degrees. As a reward I will give you all my dominoes".

We got even more taken aback. And while we are wondering what was going on, help us make an optimal matrix of dominoes.

Input

The first line contains integers n, m (1 ≤ n, m ≤ 103).

In the next lines there is a description of the teachers' matrix. Each of next n lines contains m dominoes. The description of one domino is two integers (0 or 1), written without a space — the digits on the left and right half of the domino.

Output

Print the resulting matrix of dominoes in the format: n lines, each of them contains m space-separated dominoes.

If there are multiple optimal solutions, print any of them.

Examples

Input

2 3
01 11 00
00 01 11


Output

11 11 10
00 00 01


Input

4 1
11
10
01
00


Output

11
10
01
00

Note

Consider the answer for the first sample. There, the maximum sum among all columns equals 1 (the number of columns is 6, and not 3). Obviously, this maximum can't be less than 1, then such matrix is optimal.

Note that the dominoes can be rotated by 180 degrees.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A telephone number is a sequence of exactly 11 digits, where the first digit is 8. For example, the sequence 80011223388 is a telephone number, but the sequences 70011223388 and 80000011223388 are not.

You are given a string $s$ of length $n$, consisting of digits.

In one operation you can delete any character from string $s$. For example, it is possible to obtain strings 112, 111 or 121 from string 1121.

You need to determine whether there is such a sequence of operations (possibly empty), after which the string $s$ becomes a telephone number.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 100$) — the number of test cases.

The first line of each test case contains one integer $n$ ($1 \le n \le 100$) — the length of string $s$.

The second line of each test case contains the string $s$ ($|s| = n$) consisting of digits.


-----Output-----

For each test print one line.

If there is a sequence of operations, after which $s$ becomes a telephone number, print YES.

Otherwise, print NO.


-----Example-----
Input
2
13
7818005553535
11
31415926535

Output
YES
NO



-----Note-----

In the first test case you need to delete the first and the third digits. Then the string 7818005553535 becomes 88005553535.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You will be given three integers $A$, $B$ and $C$. The numbers will not be given in that exact order, but we do know that $A$ is less than $B$ and $B$ less than $C$. In order to make for a more pleasant viewing, we want to rearrange them in a given order.

-----Input-----
The first line contains the three positive integers $A$, $B$ and $C$, not necessarily in that order. The three numbers will be less than or equal to $100$.

The second line contains three uppercase letters ’A’, ’B’ and ’C’ (with no spaces between them) representing the desired order.

-----Output-----
Output $A$, $B$ and $C$ in the desired order on a single line, separated by single spaces.

-----Examples-----
Sample Input:
1 5 3
ABC
Sample Output:
1 3 5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

Example 1:


Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:


Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a non-negative integer n, its decimal representation consists of at most 100 digits and doesn't contain leading zeroes.

Your task is to determine if it is possible in this case to remove some of the digits (possibly not remove any digit at all) so that the result contains at least one digit, forms a non-negative integer, doesn't have leading zeroes and is divisible by 8. After the removing, it is forbidden to rearrange the digits.

If a solution exists, you should print it.

Input

The single line of the input contains a non-negative integer n. The representation of number n doesn't contain any leading zeroes and its length doesn't exceed 100 digits. 

Output

Print "NO" (without quotes), if there is no such way to remove some digits from number n. 

Otherwise, print "YES" in the first line and the resulting number after removing digits from number n in the second line. The printed number must be divisible by 8.

If there are multiple possible answers, you may print any of them.

Examples

Input

3454


Output

YES
344


Input

10


Output

YES
0


Input

111111


Output

NO

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
If you finish this kata, you can try [Insane Coloured Triangles](http://www.codewars.com/kata/insane-coloured-triangles) by Bubbler, which is a ***much*** harder version of this one.

A coloured triangle is created from a row of colours, each of which is red, green or blue. Successive rows, each containing one fewer colour than the last, are generated by considering the two touching colours in the previous row. If these colours are identical, the same colour is used in the new row. If they are different, the missing colour is used in the new row. This is continued until the final row, with only a single colour, is generated.

The different possibilities are:
```
Colour here:        G G        B G        R G        B R
Becomes colour:      G          R          B          G
```

With a bigger example:
```
R R G B R G B B
 R B R G B R B
  G G B R G G
   G R G B G
    B B R R
     B G R
      R B
       G
```
  
You will be given the first row of the triangle as a string and its your job to return the final colour which would appear in the bottom row as a string. In the case of the example above, you would the given `RRGBRGBB` you should return `G`.

* The input string will only contain the uppercase letters `R, G, B` and there will be at least one letter so you do not have to test for invalid input.
* If you are only given one colour as the input, return that colour. 


*Adapted from the 2017 British Informatics Olympiad*

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The only difference between problems C1 and C2 is that all values in input of problem C1 are distinct (this condition may be false for problem C2).

You are given a sequence a consisting of n integers. All these integers are distinct, each value from 1 to n appears in the sequence exactly once.

You are making a sequence of moves. During each move you must take either the leftmost element of the sequence or the rightmost element of the sequence, write it down and remove it from the sequence. Your task is to write down a strictly increasing sequence, and among all such sequences you should take the longest (the length of the sequence is the number of elements in it).

For example, for the sequence [2, 1, 5, 4, 3] the answer is 4 (you take 2 and the sequence becomes [1, 5, 4, 3], then you take the rightmost element 3 and the sequence becomes [1, 5, 4], then you take 4 and the sequence becomes [1, 5] and then you take 5 and the sequence becomes [1], the obtained increasing sequence is [2, 3, 4, 5]).

Input

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

The second line of the input contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ n), where a_i is the i-th element of a. All these integers are pairwise distinct.

Output

In the first line of the output print k — the maximum number of elements in a strictly increasing sequence you can obtain.

In the second line print a string s of length k, where the j-th character of this string s_j should be 'L' if you take the leftmost element during the j-th move and 'R' otherwise. If there are multiple answers, you can print any.

Examples

Input


5
2 1 5 4 3


Output


4
LRRR


Input


7
1 3 5 6 7 4 2


Output


7
LRLRLLL


Input


3
1 2 3


Output


3
LLL


Input


4
1 2 4 3


Output


4
LLRL

Note

The first example is described in the problem statement.

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