vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
While walking down the street Vanya saw a label "Hide&Seek". Because he is a programmer, he used & as a bitwise AND for these two words represented as a integers in base 64 and got new word. Now Vanya thinks of some string s and wants to know the number of pairs of words of length |s| (length of s), such that their bitwise AND is equal to s. As this number can be large, output it modulo 109 + 7.

To represent the string as a number in numeral system with base 64 Vanya uses the following rules:

  * digits from '0' to '9' correspond to integers from 0 to 9; 
  * letters from 'A' to 'Z' correspond to integers from 10 to 35; 
  * letters from 'a' to 'z' correspond to integers from 36 to 61; 
  * letter '-' correspond to integer 62; 
  * letter '_' correspond to integer 63. 

Input

The only line of the input contains a single word s (1 ≤ |s| ≤ 100 000), consisting of digits, lowercase and uppercase English letters, characters '-' and '_'.

Output

Print a single integer — the number of possible pairs of words, such that their bitwise AND is equal to string s modulo 109 + 7.

Examples

Input

z


Output

3


Input

V_V


Output

9


Input

Codeforces


Output

130653412

Note

For a detailed definition of bitwise AND we recommend to take a look in the corresponding article in Wikipedia.

In the first sample, there are 3 possible solutions: 

  1. z&_ = 61&63 = 61 = z
  2. _&z = 63&61 = 61 = z
  3. z&z = 61&61 = 61 = z

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Seryozha conducts a course dedicated to building a map of heights of Stepanovo recreation center. He laid a rectangle grid of size $n \times m$ cells on a map (rows of grid are numbered from $1$ to $n$ from north to south, and columns are numbered from $1$ to $m$ from west to east). After that he measured the average height of each cell above Rybinsk sea level and obtained a matrix of heights of size $n \times m$. The cell $(i, j)$ lies on the intersection of the $i$-th row and the $j$-th column and has height $h_{i, j}$. 

Seryozha is going to look at the result of his work in the browser. The screen of Seryozha's laptop can fit a subrectangle of size $a \times b$ of matrix of heights ($1 \le a \le n$, $1 \le b \le m$). Seryozha tries to decide how the weather can affect the recreation center — for example, if it rains, where all the rainwater will gather. To do so, he is going to find the cell having minimum height among all cells that are shown on the screen of his laptop.

Help Seryozha to calculate the sum of heights of such cells for all possible subrectangles he can see on his screen. In other words, you have to calculate the sum of minimum heights in submatrices of size $a \times b$ with top left corners in $(i, j)$ over all $1 \le i \le n - a + 1$ and $1 \le j \le m - b + 1$.

Consider the sequence $g_i = (g_{i - 1} \cdot x + y) \bmod z$. You are given integers $g_0$, $x$, $y$ and $z$. By miraculous coincidence, $h_{i, j} = g_{(i - 1) \cdot m + j - 1}$ ($(i - 1) \cdot m + j - 1$ is the index).


-----Input-----

The first line of the input contains four integers $n$, $m$, $a$ and $b$ ($1 \le n, m \le 3\,000$, $1 \le a \le n$, $1 \le b \le m$) — the number of rows and columns in the matrix Seryozha has, and the number of rows and columns that can be shown on the screen of the laptop, respectively.

The second line of the input contains four integers $g_0$, $x$, $y$ and $z$ ($0 \le g_0, x, y < z \le 10^9$).


-----Output-----

Print a single integer — the answer to the problem.


-----Example-----
Input
3 4 2 1
1 2 3 59

Output
111



-----Note-----

The matrix from the first example:  $\left. \begin{array}{|c|c|c|c|} \hline 1 & {5} & {13} & {29} \\ \hline 2 & {7} & {17} & {37} \\ \hline 18 & {39} & {22} & {47} \\ \hline \end{array} \right.$

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
A group of *n* merry programmers celebrate Robert Floyd's birthday. Polucarpus has got an honourable task of pouring Ber-Cola to everybody. Pouring the same amount of Ber-Cola to everybody is really important. In other words, the drink's volume in each of the *n* mugs must be the same.

Polycarpus has already began the process and he partially emptied the Ber-Cola bottle. Now the first mug has *a*1 milliliters of the drink, the second one has *a*2 milliliters and so on. The bottle has *b* milliliters left and Polycarpus plans to pour them into the mugs so that the main equation was fulfilled.

Write a program that would determine what volume of the drink Polycarpus needs to add into each mug to ensure that the following two conditions were fulfilled simultaneously: 
 -  there were *b* milliliters poured in total. That is, the bottle need to be emptied; -  after the process is over, the volumes of the drink in the mugs should be equal.

Input Specification:
The first line contains a pair of integers *n*, *b* (2<=≤<=*n*<=≤<=100,<=1<=≤<=*b*<=≤<=100), where *n* is the total number of friends in the group and *b* is the current volume of drink in the bottle. The second line contains a sequence of integers *a*1,<=*a*2,<=...,<=*a**n* (0<=≤<=*a**i*<=≤<=100), where *a**i* is the current volume of drink in the *i*-th mug.

Output Specification:
Print a single number "-1" (without the quotes), if there is no solution. Otherwise, print *n* float numbers *c*1,<=*c*2,<=...,<=*c**n*, where *c**i* is the volume of the drink to add in the *i*-th mug. Print the numbers with no less than 6 digits after the decimal point, print each *c**i* on a single line. Polycarpus proved that if a solution exists then it is unique.

Russian locale is installed by default on the testing computer. Make sure that your solution use the point to separate the integer part of a real number from the decimal, not a comma.

Demo Input:
['5 50\n1 2 3 4 5\n', '2 2\n1 100\n']

Demo Output:
['12.000000\n11.000000\n10.000000\n9.000000\n8.000000\n', '-1\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Nauuo is a girl who loves playing cards.

One day she was playing cards but found that the cards were mixed with some empty ones.

There are $n$ cards numbered from $1$ to $n$, and they were mixed with another $n$ empty cards. She piled up the $2n$ cards and drew $n$ of them. The $n$ cards in Nauuo's hands are given. The remaining $n$ cards in the pile are also given in the order from top to bottom.

In one operation she can choose a card in her hands and play it — put it at the bottom of the pile, then draw the top card from the pile.

Nauuo wants to make the $n$ numbered cards piled up in increasing order (the $i$-th card in the pile from top to bottom is the card $i$) as quickly as possible. Can you tell her the minimum number of operations?


-----Input-----

The first line contains a single integer $n$ ($1\le n\le 2\cdot 10^5$) — the number of numbered cards.

The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($0\le a_i\le n$) — the initial cards in Nauuo's hands. $0$ represents an empty card.

The third line contains $n$ integers $b_1,b_2,\ldots,b_n$ ($0\le b_i\le n$) — the initial cards in the pile, given in order from top to bottom. $0$ represents an empty card.

It is guaranteed that each number from $1$ to $n$ appears exactly once, either in $a_{1..n}$ or $b_{1..n}$.


-----Output-----

The output contains a single integer — the minimum number of operations to make the $n$ numbered cards piled up in increasing order.


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

Output
2
Input
3
0 2 0
1 0 3

Output
4
Input
11
0 0 0 5 0 0 0 4 0 0 11
9 2 6 0 8 1 7 0 3 0 10

Output
18


-----Note-----

Example 1

We can play the card $2$ and draw the card $3$ in the first operation. After that, we have $[0,3,0]$ in hands and the cards in the pile are $[0,1,2]$ from top to bottom.

Then, we play the card $3$ in the second operation. The cards in the pile are $[1,2,3]$, in which the cards are piled up in increasing order.

Example 2

Play an empty card and draw the card $1$, then play $1$, $2$, $3$ in order.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Bear and Finding Criminals

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
There are *n* cities in Bearland, numbered 1 through *n*. Cities are arranged in one long row. The distance between cities *i* and *j* is equal to |*i*<=-<=*j*|.

Limak is a police officer. He lives in a city *a*. His job is to catch criminals. It's hard because he doesn't know in which cities criminals are. Though, he knows that there is at most one criminal in each city.

Limak is going to use a BCD (Bear Criminal Detector). The BCD will tell Limak how many criminals there are for every distance from a city *a*. After that, Limak can catch a criminal in each city for which he is sure that there must be a criminal.

You know in which cities criminals are. Count the number of criminals Limak will catch, after he uses the BCD.

Input Specification:
The first line of the input contains two integers *n* and *a* (1<=≤<=*a*<=≤<=*n*<=≤<=100) — the number of cities and the index of city where Limak lives.

The second line contains *n* integers *t*1,<=*t*2,<=...,<=*t**n* (0<=≤<=*t**i*<=≤<=1). There are *t**i* criminals in the *i*-th city.

Output Specification:
Print the number of criminals Limak will catch.

Demo Input:
['6 3\n1 1 1 0 1 0\n', '5 2\n0 0 0 1 0\n']

Demo Output:
['3\n', '1\n']

Note:
In the first sample, there are six cities and Limak lives in the third one (blue arrow below). Criminals are in cities marked red.

Using the BCD gives Limak the following information:
 -  There is one criminal at distance 0 from the third city — Limak is sure that this criminal is exactly in the third city. -  There is one criminal at distance 1 from the third city — Limak doesn't know if a criminal is in the second or fourth city. -  There are two criminals at distance 2 from the third city — Limak is sure that there is one criminal in the first city and one in the fifth city. -  There are zero criminals for every greater distance. 
So, Limak will catch criminals in cities 1, 3 and 5, that is 3 criminals in total.

In the second sample (drawing below), the BCD gives Limak the information that there is one criminal at distance 2 from Limak's city. There is only one city at distance 2 so Limak is sure where a criminal is.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
>When no more interesting kata can be resolved, I just choose to create the new kata, to solve their own, to enjoy the process  --myjinxin2015 said

# Description:
 Given a string `str` that contains some "(" or ")". Your task is to find the longest substring in `str`(all brackets in the substring are closed). The result is the length of the longest substring.

 For example:
 ```
 str = "()()("
 findLongest(str) === 4 
 "()()" is the longest substring
 ```
 
# Note:
 - All inputs are valid.
 - If no such substring found, return 0.
 - Please pay attention to the performance of code. ;-)
 - In the performance test(100000 brackets str x 100 testcases), the time consuming of each test case should be within 35ms. This means, your code should run as fast as a rocket ;-) 
 
# Some Examples
 ```
 findLongest("()") === 2
 findLongest("()(") === 2
 findLongest("()()") === 4
 findLongest("()()(") === 4
 findLongest("(()())") === 6
 findLongest("(()(())") === 6
 findLongest("())(()))") === 4
 findLongest("))((") === 0
 findLongest("") === 0
 ```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.


Note that it is the kth smallest element in the sorted order, not the kth distinct element.


Example:

matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,

return 13.



Note: 
You may assume k is always valid, 1 ≤ k ≤ n2.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Little C loves number «3» very much. He loves all things about it.

Now he is playing a game on a chessboard of size $n \times m$. The cell in the $x$-th row and in the $y$-th column is called $(x,y)$. Initially, The chessboard is empty. Each time, he places two chessmen on two different empty cells, the Manhattan distance between which is exactly $3$. The Manhattan distance between two cells $(x_i,y_i)$ and $(x_j,y_j)$ is defined as $|x_i-x_j|+|y_i-y_j|$.

He want to place as many chessmen as possible on the chessboard. Please help him find the maximum number of chessmen he can place.


-----Input-----

A single line contains two integers $n$ and $m$ ($1 \leq n,m \leq 10^9$) — the number of rows and the number of columns of the chessboard.


-----Output-----

Print one integer — the maximum number of chessmen Little C can place.


-----Examples-----
Input
2 2

Output
0
Input
3 3

Output
8


-----Note-----

In the first example, the Manhattan distance between any two cells is smaller than $3$, so the answer is $0$.

In the second example, a possible solution is $(1,1)(3,2)$, $(1,2)(3,3)$, $(2,1)(1,3)$, $(3,1)(2,3)$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It's one more school day now. Sasha doesn't like classes and is always bored at them. So, each day he invents some game and plays in it alone or with friends.

Today he invented one simple game to play with Lena, with whom he shares a desk. The rules are simple. Sasha draws n sticks in a row. After that the players take turns crossing out exactly k sticks from left or right in each turn. Sasha moves first, because he is the inventor of the game. If there are less than k sticks on the paper before some turn, the game ends. Sasha wins if he makes strictly more moves than Lena. Sasha wants to know the result of the game before playing, you are to help him.


-----Input-----

The first line contains two integers n and k (1 ≤ n, k ≤ 10^18, k ≤ n) — the number of sticks drawn by Sasha and the number k — the number of sticks to be crossed out on each turn.


-----Output-----

If Sasha wins, print "YES" (without quotes), otherwise print "NO" (without quotes).

You can print each letter in arbitrary case (upper of lower).


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

Output
YES

Input
10 4

Output
NO



-----Note-----

In the first example Sasha crosses out 1 stick, and then there are no sticks. So Lena can't make a move, and Sasha wins.

In the second example Sasha crosses out 4 sticks, then Lena crosses out 4 sticks, and after that there are only 2 sticks left. Sasha can't make a move. The players make equal number of moves, so Sasha doesn't win.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya owns three strings s , a and b, each of them consists only of first k Latin letters.

Let a template be such a string of length k that each of the first k Latin letters appears in it exactly once (thus there are k! distinct templates). Application of template p to the string s is the replacement of each character in string s with p_i, i is the index of this letter in the alphabet. For example, applying template "bdca" to a string "aabccd" yields string "bbdcca".

Vasya wants to know if there exists such a template which yields a string lexicographically greater than or equal to string a and lexicographically less than or equal to string b after applying it to s.

If there exist multiple suitable templates, print any of them.

String a is lexicographically less than string b if there is some i (1 ≤ i ≤ n) that a_i < b_i and for any j (1 ≤ j < i) a_j = b_j.

You are required to answer t testcases independently.

Input

The first line contains a single integer t (1 ≤ t ≤ 10^6) — the number of testcases.

In hacks you can only use t = 1.

Each of the next t lines contains the description of the testcase in the following form:

The first line of the testcase contains a single integer k (1 ≤ k ≤ 26) — the length of the template.

The second line of the testcase contains the string s (1 ≤ |s| ≤ 10^6).

The third line of the testcase contains the string a.

The fourth line of the testcase contains the string b.

Strings s, a and b have the same length (|s| = |a| = |b|) and consist only of the first k Latin letters, all letters are lowercase.

It is guaranteed that string a is lexicographically less than or equal to string b.

It is also guaranteed that the total length of strings over all testcase won't exceed 3 ⋅ 10^6.

Output

Print the answers to all testcases in the following form:

If there exists no suitable template then print "NO" in the first line.

Otherwise print "YES" in the first line and the template itself in the second line (k lowercase letters, each of the first k Latin letters should appear exactly once).

If there exist multiple suitable templates, print any of them.

Example

Input

2
4
bbcb
aada
aada
3
abc
bbb
bbb


Output

YES
badc
NO

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef had an array A of length N such that 1 ≤ A_{i} ≤ N for all 1 ≤ i ≤ N. Chef constructed another binary array B of length N in the following manner:
B_{i} = 1 if the frequency of element i in A is *odd*.
B_{i} = 0 if the frequency of element i in A is *even*.

Such an array B is called the *parity encoding* array of A.

For example, if A = [1, 1, 2, 3], then B = [0, 1, 1, 0].

Unfortunately, Chef completely forgot the array A and vaguely remembers the *parity encoding* array B. He is now wondering whether there exists any valid array A for which the *parity encoding* array is B. Can you help Chef?

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

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first line of each test case contains an integer N — the size of the arrays A and B.
- The second line of each test case contains N space-separated integers B_{1}, B_{2}, \dots, B_{N} denoting the *parity encoding* array B.

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

For each test case, output YES if there exists any valid array A for which the *parity encoding* array is B. Otherwise, output NO.

You may print each character of YES and NO in uppercase or lowercase (for example, yes, yEs, Yes will be considered identical).

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$B_{i} \in \{0, 1\}$
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
3
4
0 1 0 1
5
1 1 1 1 0
6
1 1 1 1 1 1

----- Sample Output 1 ------ 
YES
NO
YES

----- explanation 1 ------ 
Test case $1$: $A = [2, 4, 3, 3]$ is a valid array for the given array $B$.

Test case $2$: It can be proven that there does not exist any array $A$ for the given parity encoding array $B$.

Test case $3$: $A = [1, 2, 3, 4, 5, 6]$ is a valid array for the given array $B$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an integer array a_1, a_2, ..., a_n, where a_i represents the number of blocks at the i-th position. It is guaranteed that 1 ≤ a_i ≤ n. 

In one operation you can choose a subset of indices of the given array and remove one block in each of these indices. You can't remove a block from a position without blocks.

All subsets that you choose should be different (unique).

You need to remove all blocks in the array using at most n+1 operations. It can be proved that the answer always exists.

Input

The first line contains a single integer n (1 ≤ n ≤ 10^3) — length of the given array.

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ n) — numbers of blocks at positions 1, 2, ..., n.

Output

In the first line print an integer op (0 ≤ op ≤ n+1).

In each of the following op lines, print a binary string s of length n. If s_i='0', it means that the position i is not in the chosen subset. Otherwise, s_i should be equal to '1' and the position i is in the chosen subset.

All binary strings should be distinct (unique) and a_i should be equal to the sum of s_i among all chosen binary strings.

If there are multiple possible answers, you can print any.

It can be proved that an answer always exists.

Examples

Input


5
5 5 5 5 5


Output


6
11111
01111
10111
11011
11101
11110


Input


5
5 1 1 1 1


Output


5
11000
10000
10100
10010
10001


Input


5
4 1 5 3 4


Output


5
11111
10111
10101
00111
10100

Note

In the first example, the number of blocks decrease like that:

{ 5,5,5,5,5 } → { 4,4,4,4,4 } → { 4,3,3,3,3 } → { 3,3,2,2,2 } → { 2,2,2,1,1 } → { 1,1,1,1,0 } → { 0,0,0,0,0 }. And we can note that each operation differs from others.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an unsorted linked list of N nodes. The task is to remove duplicate elements from this unsorted Linked List. When a value appears in multiple nodes, the node which appeared first should be kept, all others duplicates are to be removed.
Example 1:
Input:
N = 4
value[] = {5,2,2,4}
Output: 5 2 4
Explanation:Given linked list elements are
5->2->2->4, in which 2 is repeated only.
So, we will delete the extra repeated
elements 2 from the linked list and the
resultant linked list will contain 5->2->4
Example 2:
Input:
N = 5
value[] = {2,2,2,2,2}
Output: 2
Explanation:Given linked list elements are
2->2->2->2->2, in which 2 is repeated. So,
we will delete the extra repeated elements
2 from the linked list and the resultant
linked list will contain only 2.
Your Task:
You have to complete the method removeDuplicates() which takes 1 argument: the head of the linked list.  Your function should return a pointer to a linked list with no duplicate element.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 <= size of linked lists <= 10^{6}
0 <= numbers in list <= 10^{4}

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