vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
In this problem you will write a simple generator of Brainfuck (<https://en.wikipedia.org/wiki/Brainfuck>) calculators.

You are given an arithmetic expression consisting of integers from 0 to 255 and addition/subtraction signs between them. Output a Brainfuck program which, when executed, will print the result of evaluating this expression.

We use a fairly standard Brainfuck interpreter for checking the programs:

  * 30000 memory cells.
  * memory cells store integers from 0 to 255 with unsigned 8-bit wraparound.
  * console input (, command) is not supported, but it's not needed for this problem.

Input

The only line of input data contains the arithmetic expression. The expression will contain between 2 and 10 operands, separated with arithmetic signs plus and/or minus. Each operand will be an integer between 0 and 255, inclusive. The calculations result is guaranteed to be an integer between 0 and 255, inclusive (results of intermediary calculations might be outside of these boundaries).

Output

Output a Brainfuck program which, when executed, will print the result of evaluating this expression. The program must be at most 5000000 characters long (including the non-command characters), and its execution must be complete in at most 50000000 steps.

Examples

Input

2+3


Output

++&gt;
+++&gt;
&lt;[&lt;+&gt;-]&lt;
++++++++++++++++++++++++++++++++++++++++++++++++.


Input

9-7


Output

+++++++++&gt;
+++++++&gt;
&lt;[&lt;-&gt;-]&lt;
++++++++++++++++++++++++++++++++++++++++++++++++.

Note

You can download the source code of the Brainfuck interpreter by the link [http://assets.codeforces.com/rounds/784/bf.cpp](//assets.codeforces.com/rounds/784/bf.cpp). We use this code to interpret outputs.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Kornislav the turtle never has anything interesting to do. Since he’s going to live for three hundred years, he keeps trying to find way to kill time. This weekend he started playing "enclose the largest rectangle".

To start with, Kornislav needs four positive integers. He tries to enclose a rectangle by moving in one direction, then turning 90 degrees, then walking in the new direction etc. Kornislav makes a total of three 90-degree turns and walks four segments.

When walking in some direction, the number of steps he takes must be equal to one of the four chosen integers and each integer must be used exactly once. Depending on the order in which Kornislav uses the integers, his walk will make various shapes, some of which don’t contain enclosed rectangles. Write a program that calculates the largest rectangle the turtle can enclose with its walk.

-----Input-----
The first line contains four positive integers $A, B, C$ and $D~ (0 < A, B, C, D < 100)$, the four chosen integers.

-----Output-----
Output the largest area.

-----Examples-----
Sample Input:
1 2 3 4
Sample Output:
3

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There have recently been elections in the zoo. Overall there were 7 main political parties: one of them is the Little Elephant Political Party, 6 other parties have less catchy names.

Political parties find their number in the ballot highly important. Overall there are m possible numbers: 1, 2, ..., m. Each of these 7 parties is going to be assigned in some way to exactly one number, at that, two distinct parties cannot receive the same number.

The Little Elephant Political Party members believe in the lucky digits 4 and 7. They want to evaluate their chances in the elections. For that, they need to find out, how many correct assignments are there, such that the number of lucky digits in the Little Elephant Political Party ballot number is strictly larger than the total number of lucky digits in the ballot numbers of 6 other parties. 

Help the Little Elephant Political Party, calculate this number. As the answer can be rather large, print the remainder from dividing it by 1000000007 (109 + 7).

Input

A single line contains a single positive integer m (7 ≤ m ≤ 109) — the number of possible numbers in the ballot.

Output

In a single line print a single integer — the answer to the problem modulo 1000000007 (109 + 7).

Examples

Input

7


Output

0


Input

8


Output

1440

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The day has come when all the great coders are going to compete one last time in IIITA programming series . As a chief guest the organizers has called "THE GREAT CHOTU" to cheer the students. 

Chotu decides to distribute chocolates among the coders. Chotu has initially X chocolates and there are N coders. Being a coder himself he wants to give chocolate to every coder without wasting any chocolate, so he decides to convert X chocolates into exactly N chocolates by using his superdevice.

His device has two buttons : Red and Blue. By clicking the red button he can double the amount of chocolates and By clicking the blue button, he can decrease the amount of chocolates by 1.

You need to find the minimum number of clicks chotu has to make in order obtain exactly N chocolates?

Input
First line of input contains T the number of test cases.
Next T lines contain 2 integers each X, N.

Output
For each test case print minimum number of clicks required.

Constraints
1 ≤ T ≤ 11
1 ≤ X ≤ 10000
1 ≤ N ≤ 10000 

SAMPLE INPUT
2
4 6
10 1

SAMPLE OUTPUT
2
9

Explanation

In the first example you need to push the blue button once, and then push the red button once.

In the second example, doubling the number is unnecessary, so we need to push the blue button nine times.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given are an integer N and arrays S, T, U, and V, each of length N.
Construct an N×N matrix a that satisfy the following conditions:
 - a_{i,j} is an integer.
 - 0 \leq a_{i,j}  \lt 2^{64}.
 - If S_{i} = 0, the bitwise AND of the elements in the i-th row is U_{i}.
 - If S_{i} = 1, the bitwise OR of the elements in the i-th row is U_{i}.
 - If T_{i} = 0, the bitwise AND of the elements in the i-th column is V_{i}.
 - If T_{i} = 1, the bitwise OR of the elements in the i-th column is V_{i}.
However, there may be cases where no matrix satisfies the conditions.

-----Constraints-----
 - All values in input are integers.
 -  1 \leq N \leq 500 
 -  0 \leq S_{i} \leq 1 
 -  0 \leq T_{i} \leq 1  
 -  0 \leq U_{i} \lt 2^{64}  
 -  0 \leq V_{i} \lt 2^{64}  

-----Input-----
Input is given from Standard Input in the following format:
N
S_{1} S_{2} ...  S_{N}
T_{1} T_{2} ...  T_{N}
U_{1} U_{2} ...  U_{N}
V_{1} V_{2} ...  V_{N}

-----Output-----
If there exists a matrix that satisfies the conditions, print one such matrix in the following format:
a_{1,1} ...  a_{1,N}
:
a_{N,1} ...  a_{N,N}

Note that any matrix satisfying the conditions is accepted.
If no matrix satisfies the conditions, print -1.

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

-----Sample Output-----
1 1
1 0

In Sample Input 1, we need to find a matrix such that:
 - the bitwise AND of the elements in the 1-st row is 1;
 - the bitwise OR of the elements in the 2-nd row is 1;
 - the bitwise OR of the elements in the 1-st column is 1;
 - the bitwise AND of the elements in the 2-nd column is 0.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Consider some set of distinct characters $A$ and some string $S$, consisting of exactly $n$ characters, where each character is present in $A$.

You are given an array of $m$ integers $b$ ($b_1 < b_2 < \dots < b_m$). 

You are allowed to perform the following move on the string $S$:

  Choose some valid $i$ and set $k = b_i$;  Take the first $k$ characters of $S = Pr_k$;  Take the last $k$ characters of $S = Su_k$;  Substitute the first $k$ characters of $S$ with the reversed $Su_k$;  Substitute the last $k$ characters of $S$ with the reversed $Pr_k$. 

For example, let's take a look at $S =$ "abcdefghi" and $k = 2$. $Pr_2 =$ "ab", $Su_2 =$ "hi". Reversed $Pr_2 =$ "ba", $Su_2 =$ "ih". Thus, the resulting $S$ is "ihcdefgba".

The move can be performed arbitrary number of times (possibly zero). Any $i$ can be selected multiple times over these moves.

Let's call some strings $S$ and $T$ equal if and only if there exists such a sequence of moves to transmute string $S$ to string $T$. For the above example strings "abcdefghi" and "ihcdefgba" are equal. Also note that this implies $S = S$.

The task is simple. Count the number of distinct strings.

The answer can be huge enough, so calculate it modulo $998244353$.


-----Input-----

The first line contains three integers $n$, $m$ and $|A|$ ($2 \le n \le 10^9$, $1 \le m \le min(\frac n 2, 2 \cdot 10^5)$, $1 \le |A| \le 10^9$) — the length of the strings, the size of the array $b$ and the size of the set $A$, respectively.

The second line contains $m$ integers $b_1, b_2, \dots, b_m$ ($1 \le b_i \le \frac n 2$, $b_1 < b_2 < \dots < b_m$).


-----Output-----

Print a single integer — the number of distinct strings of length $n$ with characters from set $A$ modulo $998244353$.


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

Output
6

Input
9 2 26
2 3

Output
150352234

Input
12 3 1
2 5 6

Output
1



-----Note-----

Here are all the distinct strings for the first example. The chosen letters 'a' and 'b' are there just to show that the characters in $A$ are different. 

  "aaa"  "aab" = "baa"  "aba"  "abb" = "bba"  "bab"  "bbb"

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string str and a pattern pat. You need to check whether the pattern is present or not in the given string. 
Example 1:-
Input:
2
abcdefh
bcd
axzy
xy
Output:
Present
Not present
 
Your task:
You need to complete the function searchPattern() and you need to return a boolean value (True or False) according to the pattern present or not in the given string.
Returning True will represent the "Present" and False will be "Not Present".
 
Constraints:
1 <= T <= 100
1 <= |str| <= 100
1 <= |text| <= 100

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array arr that represents a permutation of numbers from 1 to n. You have a binary string of size n that initially has all its bits set to zero.
At each step i (assuming both the binary string and arr are 1-indexed) from 1 to n, the bit at position arr[i] is set to 1. You are given an integer m and you need to find the latest step at which there exists a group of ones of length m. A group of ones is a contiguous substring of 1s such that it cannot be extended in either direction.
Return the latest step at which there exists a group of ones of length exactly m. If no such group exists, return -1.
 
Example 1:
Input: arr = [3,5,1,2,4], m = 1
Output: 4
Explanation:
Step 1: "00100", groups: ["1"]
Step 2: "00101", groups: ["1", "1"]
Step 3: "10101", groups: ["1", "1", "1"]
Step 4: "11101", groups: ["111", "1"]
Step 5: "11111", groups: ["11111"]
The latest step at which there exists a group of size 1 is step 4.
Example 2:
Input: arr = [3,1,5,4,2], m = 2
Output: -1
Explanation:
Step 1: "00100", groups: ["1"]
Step 2: "10100", groups: ["1", "1"]
Step 3: "10101", groups: ["1", "1", "1"]
Step 4: "10111", groups: ["1", "111"]
Step 5: "11111", groups: ["11111"]
No group of size 2 exists during any step.

Example 3:
Input: arr = [1], m = 1
Output: 1

Example 4:
Input: arr = [2,1], m = 2
Output: 2

 
Constraints:

n == arr.length
1 <= n <= 10^5
1 <= arr[i] <= n
All integers in arr are distinct.
1 <= m <= arr.length

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef has just started Programming, he is in first year of Engineering. Chef is reading about Relational Operators. 

Relational Operators are operators which check relatioship between two values. Given two numerical values A and B you need to help chef in finding the relationship between them that is, 

- First one is greater than second or,
- First one is less than second or,
- First and second one are equal.

-----Input-----
First line contains an integer T, which denotes the number of testcases. Each of the T lines contain two integers A and B. 

-----Output-----
For each line of input produce one line of output. This line contains any one of the relational operators

'<' , '>' , '='.

-----Constraints-----

- 1 ≤ T ≤ 10000
- 1 ≤ A, B ≤ 1000000001

-----Example-----
Input:
3
10 20
20 10
10 10

Output:
<
>
=

-----Explanation-----
Example case 1. In this example 1 as 10 is lesser than 20.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Bizon the Champion isn't just a bison. He also is a favorite of the "Bizons" team.

At a competition the "Bizons" got the following problem: "You are given two distinct words (strings of English letters), *s* and *t*. You need to transform word *s* into word *t*". The task looked simple to the guys because they know the suffix data structures well. Bizon Senior loves suffix automaton. By applying it once to a string, he can remove from this string any single character. Bizon Middle knows suffix array well. By applying it once to a string, he can swap any two characters of this string. The guys do not know anything about the suffix tree, but it can help them do much more. 

Bizon the Champion wonders whether the "Bizons" can solve the problem. Perhaps, the solution do not require both data structures. Find out whether the guys can solve the problem and if they can, how do they do it? Can they solve it either only with use of suffix automaton or only with use of suffix array or they need both structures? Note that any structure may be used an unlimited number of times, the structures may be used in any order.

Input Specification:
The first line contains a non-empty word *s*. The second line contains a non-empty word *t*. Words *s* and *t* are different. Each word consists only of lowercase English letters. Each word contains at most 100 letters.

Output Specification:
In the single line print the answer to the problem. Print "need tree" (without the quotes) if word *s* cannot be transformed into word *t* even with use of both suffix array and suffix automaton. Print "automaton" (without the quotes) if you need only the suffix automaton to solve the problem. Print "array" (without the quotes) if you need only the suffix array to solve the problem. Print "both" (without the quotes), if you need both data structures to solve the problem.

It's guaranteed that if you can solve the problem only with use of suffix array, then it is impossible to solve it only with use of suffix automaton. This is also true for suffix automaton.

Demo Input:
['automaton\ntomat\n', 'array\narary\n', 'both\nhot\n', 'need\ntree\n']

Demo Output:
['automaton\n', 'array\n', 'both\n', 'need tree\n']

Note:
In the third sample you can act like that: first transform "both" into "oth" by removing the first character using the suffix automaton and then make two swaps of the string using the suffix array and get "hot".

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ujan has finally cleaned up his house and now wants to decorate the interior. He decided to place a beautiful carpet that would really tie the guest room together.

He is interested in carpets that are made up of polygonal patches such that each side of a patch is either a side of another (different) patch, or is an exterior side of the whole carpet. In other words, the carpet can be represented as a planar graph, where each patch corresponds to a face of the graph, each face is a simple polygon. The perimeter of the carpet is the number of the exterior sides. 

Ujan considers a carpet beautiful if it consists of f patches, where the i-th patch has exactly a_i sides, and the perimeter is the smallest possible. Find an example of such a carpet, so that Ujan can order it!

Input

The first line of input contains a single integer f (1 ≤ f ≤ 10^5), the number of patches in the carpet. 

The next line contains f integers a_1, …, a_f (3 ≤ a_i ≤ 3⋅ 10^5), the number of sides of the patches. The total number of the sides of the patches a_1 + … + a_f does not exceed 3⋅10^5.

Output

Output the description of the carpet as a graph. 

First, output a single integer n (3 ≤ n ≤ 3 ⋅ 10^5), the total number of vertices in your graph (the vertices must be numbered from 1 to n). 

Then output f lines containing the description of the faces. The i-th line should describe the i-th face and contain a_i distinct integers v_{i,1}, …, v_{i,a_i} (1 ≤ v_{i,j} ≤ n), which means that the vertices v_{i,j} and v_{i,(j mod{a_i})+1} are connected by an edge for any 1 ≤ j ≤ a_i.

The graph should be planar and satisfy the restrictions described in the problem statement. Its perimeter should be the smallest possible. There should be no double edges or self-loops in the graph. The graph should be connected. Note that a solution always exists; if there are multiple solutions, output any of them.

Examples

Input


2
3 3


Output


4
2 1 4 
1 2 3 


Input


3
5 3 5


Output


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

Note

In the first sample, the two triangular faces are connected by a single edge, which results in the minimum perimeter 4.

The figure shows one possible configuration for the second sample. The minimum perimeter in this case is 3. 

<image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Exclusive OR (XOR) is an operation on two binary numbers $ x $ and $ y $ (0 or 1) that produces 0 if $ x = y $ and $ 1 $ if $ x \ ne y $. This operation is represented by the symbol $ \ oplus $. From the definition: $ 0 \ oplus 0 = 0 $, $ 0 \ oplus 1 = 1 $, $ 1 \ oplus 0 = 1 $, $ 1 \ oplus 1 = 0 $.

Exclusive OR on two non-negative integers the following procedures: binary representation of the two integers are XORed on bit by bit bases, and the resultant bit array constitutes a new integer. This operation is also represented by the same symbol $ \ oplus $ For example, XOR of decimal numbers $ 3 $ and $ 5 $ is equivalent to binary operation $ 011 \ oplus 101 $ which results in $ 110 $, or $ 6 $ in integer format.

Bitwise XOR operation on a sequence $ Z $ consisting of $ M $ non-negative integers $ z_1, z_2, ..., z_M $ is defined as follows:

* $ v_0 = 0, v_i = v_ {i --1} \ oplus z_i $ ($ 1 \ leq i \ leq M $)
* Bitwise XOR on series $ Z $ is defined as $ v_M $.



You have a sequence $ A $ consisting of $ N $ non-negative integers, ample sheets of papers and an empty box. You performed each of the following operations once on every combinations of integers ($ L, R $), where $ 1 \ leq L \ leq R \ leq N $.

1. Perform the bitwise XOR operation on the sub-sequence (from $ L $ -th to $ R $ -th elements) and name the result as $ B $.
2. Select a sheet of paper and write $ B $ on it, then put it in the box.



Assume that ample sheets of paper are available to complete the trials. You select a positive integer $ K $ and line up the sheets of paper inside the box in decreasing order of the number written on them. What you want to know is the number written on the $ K $ -th sheet of paper.

You are given a series and perform all the operations described above. Then, you line up the sheets of paper in decreasing order of the numbers written on them. Make a program to determine the $ K $-th number in the series.



Input

The input is given in the following format.


$ N $ $ K $
$ a_1 $ $ a_2 $ ... $ a_N $


The first line provides the number of elements in the series $ N $ ($ 1 \ leq N \ leq 10 ^ 5 $) and the selected number $ K $ ($ 1 \ leq K \ leq N (N + 1) / 2 $) . The second line provides an array of elements $ a_i $ ($ 0 \ leq a_i \ leq 10 ^ 6 $).

Examples

Input

3 3
1 2 3


Output

2


Input

7 1
1 0 1 0 1 0 1


Output

1


Input

5 10
1 2 4 8 16


Output

7

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a positive integer n. Output its binary notation.

Input

The only line of input data contains an integer n (1 ≤ n ≤ 106).

Output

Output the binary notation of n (without any leading zeros).

Examples

Input

5


Output

101


Input

126


Output

1111110

Note

In the first example 5 = 1 * 22 + 0 * 21 + 1 * 20.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
"Don't Drink and Drive, but when you do, Better Call Saul."
Once Jesse and Walter were fighting over extra cash, and Saul decided to settle it with a game of stone piles whose winner gets the extra money. The game is described as follows :
There are N$N$ piles of stones with A$A$1$1$,$,$ A$A$2$2$,$,$ ...$...$ A$A$N$N$ stones in each pile. 
Jesse and Walter move alternately, and in one move, they remove one pile entirely. 
After a total of X$X$ moves, if the Sum of all the remaining piles is odd, Walter wins the game and gets the extra cash, else Jesse is the winner.
Walter moves first. 
Determine the winner of the game if both of them play optimally. 

-----Input:-----
- The first line will contain T$T$, number of testcases. T$T$ testcases follow : 
- The first line of each testcase contains two space-separated integers N,X$N, X$. 
- The second line of each testcase contains N$N$ space-separated integers A$A$1$1$,$,$ A$A$2$2$,$,$ ...,$...,$A$A$N$N$.

-----Output:-----
For each test case, print a single line containing the string "Jesse" (without quotes), if Jesse wins the game or "Walter" (without quotes) if Walter wins.

-----Constraints-----
- 1≤T≤104$1 \leq T \leq 10^4$
- 2≤N≤105$2 \leq N \leq 10^5$
- 1≤X≤N−1$1 \leq X \leq N-1$
- 1≤A$1 \leq A$i$i$ ≤100$ \leq 100$
- The sum of N$N$ over all test cases does not exceed 106$10^6$

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

-----Sample Output:-----
Jesse
Walter

-----EXPLANATION:-----
- 
For Test Case 1 : Playing optimally, Walter removes 4. Jesse removes 3 and then Walter removes 4. Jesse wins as 4+4=8$4 + 4 = 8$ is even.
- 
For Test Case 2 : Playing optimally, Walter removes 4, Jesse removes 3, Walter removes 2 and Jesse removes 1. Walter wins as  3+3+1=7$3 + 3 + 1 = 7$ is odd.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You just took a contract with the Jedi council. They need you to write a function, `greet_jedi()`, which takes two arguments (a first name and a last name), works out the corresponding *Jedi name*, and returns a string greeting the Jedi.

A person's *Jedi name* is the first three letters of their last name followed by the first two letters of their first name. For example:
```python
>>> greet_jedi('Beyonce', 'Knowles')
'Greetings, master KnoBe'
```
Note the capitalization: the first letter of each name is capitalized. Your input may or may not be capitalized. Your function should handle it and return the Jedi name in the correct case no matter what case the input is in:
```python
>>> greet_jedi('grae', 'drake')
'Greetings, master DraGr'
```
You can trust that your input names will always be at least three characters long.

If you're stuck, check out the [python.org tutorial](https://docs.python.org/3/tutorial/introduction.html#strings) section on strings and search "slice".

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