vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
In this problem you will write a simple code generator for a 2D programming language derived from [Brainfuck](https://en.wikipedia.org/wiki/Brainfuck).

The code in this language is a rectangular grid of characters '.' and 'X'. The code is converted to a Brainfuck program as follows: the characters are read in the usual order (top to bottom, left to right), and each 'X' character is converted a Brainfuck instruction to be executed. The instruction is defined by the left, top and right neighbors of the 'X' character using the following conversion table:

<image>

You are given a string. Output a program in the described language which prints this string.

You can download the language interpreter used for judging here: <https://assets.codeforces.com/rounds/952/puzzling-interpreter.cpp> (use C++11 to compile the code). Note several implementation details:

  * The first step of the language interpretation is conversion to a Brainfuck program, which is then executed.
  * The code must be rectangular, with all lines of the same length. It can have at most 10,000 lines and 10,000 columns, and can have at most 500,000 'X' characters.
  * The code has toroidal topology, i.e. the 'X' on the first line will have top neighbor in the last line.
  * Brainfuck interpreter has 30000 memory cells which store integers from 0 to 255 with increment/decrement done modulo 256.
  * Console input (, command) is allowed in Brainfuck code but has no effect when executed.

Input

The input consists of a single string of characters with ASCII codes between 33 ('!') and 122 ('z'), inclusive. The length of the string is between 1 and 10 characters, inclusive.

Output

Output a program in the described language which, when executed, will print the given message.

Example

Input

$$$

Output

.......X.......
......XXX......
.....XXXXX.....
....XXXXXXX....
...XXXXXXXXX...
..XXXXXXXXXXX..
.XXXXXXXXXXXXX.
...............
X.............X
X..............
X..............
X..............

Note

The example corresponds to the following Brainfuck program:
    
    
           -  
          >+<  
         >+++<  
        >+++++<  
       >+++++++<  
      >+++++++++<  
     >+++++++++++<  
      
    <             >  
    .  
    .  
    .  
    

The triangular block decrements the first memory cell and sets the value of the second memory cell to 36 - the ASCII code of '$' character. The next line after the triangular block moves the memory pointer to the second memory cell, and the next three lines print the '$' character three times.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a list of word lists of size  M * N. The task is to return all sentences possible taking one word from a list at a time via recursion. 
Example 1:
Input: 
L = {{"you", "we"},
     {"have", "are"},
Output: 
{{you have}
{you are}
{we have}
{we are}}
Explanation:
Consider every every word from the list and form
sentences with every other words, taking one word from a list .
Note: You need to maintain the order of the sentences.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function sentences() which takes a matrix of strings as input and returns a matrix of string containing all possible sentences.
Expected Time Complexity: O(M^{N})
Expected Auxiliary Space: O(M^{N})
 
Constraints:
1 <= M, N <= 6
'a' <= sentence[i][j] <= 'z'

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp decided to relax on his weekend and visited to the performance of famous ropewalkers: Agafon, Boniface and Konrad.

The rope is straight and infinite in both directions. At the beginning of the performance, Agafon, Boniface and Konrad are located in positions $a$, $b$ and $c$ respectively. At the end of the performance, the distance between each pair of ropewalkers was at least $d$.

Ropewalkers can walk on the rope. In one second, only one ropewalker can change his position. Every ropewalker can change his position exactly by $1$ (i. e. shift by $1$ to the left or right direction on the rope). Agafon, Boniface and Konrad can not move at the same time (Only one of them can move at each moment). Ropewalkers can be at the same positions at the same time and can "walk past each other".

You should find the minimum duration (in seconds) of the performance. In other words, find the minimum number of seconds needed so that the distance between each pair of ropewalkers can be greater or equal to $d$.

Ropewalkers can walk to negative coordinates, due to the rope is infinite to both sides.


-----Input-----

The only line of the input contains four integers $a$, $b$, $c$, $d$ ($1 \le a, b, c, d \le 10^9$). It is possible that any two (or all three) ropewalkers are in the same position at the beginning of the performance.


-----Output-----

Output one integer — the minimum duration (in seconds) of the performance.


-----Examples-----
Input
5 2 6 3

Output
2

Input
3 1 5 6

Output
8

Input
8 3 3 2

Output
2

Input
2 3 10 4

Output
3



-----Note-----

In the first example: in the first two seconds Konrad moves for 2 positions to the right (to the position $8$), while Agafon and Boniface stay at their positions. Thus, the distance between Agafon and Boniface will be $|5 - 2| = 3$, the distance between Boniface and Konrad will be $|2 - 8| = 6$ and the distance between Agafon and Konrad will be $|5 - 8| = 3$. Therefore, all three pairwise distances will be at least $d=3$, so the performance could be finished within 2 seconds.

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
Robot Bender decided to make Fray a birthday present. He drove *n* nails and numbered them from 1 to *n* in some order. Bender decided to make a picture using metal rods. The picture is a closed polyline, which vertices should be nails (in the given order). The segments of the polyline should be parallel to the coordinate axes. Polyline is allowed to have self-intersections. Bender can take a rod and fold it exactly once in any place to form an angle of 90 degrees. Then he can attach the place of the fold to some unoccupied nail and attach two ends of this rod to adjacent nails. A nail is considered unoccupied if there is no rod attached to it (neither by it's end nor the by the fold place). No rod could be used twice. It is not required to use all the rods.

Help Bender to solve this difficult task.

Input Specification:
The first line contains two positive integers *n* and *m* (4<=≤<=*n*<=≤<=500,<=2<=≤<=*m*<=≤<=500, *n* is even) — the amount of nails and the amount of rods. *i*-th of the following *n* lines contains a pair of integers, denoting the coordinates of the *i*-th nail. Nails should be connected in the same order as they are given in the input. The last line contains *m* integers — the lenghts of the rods. All coordinates do not exceed 104 by absolute value. Lengths of the rods are between 1 and 200<=000. No rod can be used twice. It is guaranteed that all segments of the given polyline are parallel to coordinate axes. No three consecutive nails lie on the same line.

Output Specification:
If it is impossible to solve Bender's problem, output NO. Otherwise, output YES in the first line, and in the second line output *n* numbers — *i*-th of them should be the number of rod, which fold place is attached to the *i*-th nail, or -1, if there is no such rod.

If there are multiple solutions, print any of them.

Demo Input:
['4 2\n0 0\n0 2\n2 2\n2 0\n4 4\n', '6 3\n0 0\n1 0\n1 1\n2 1\n2 2\n0 2\n3 2 3\n', '6 3\n0 0\n1 0\n1 1\n2 1\n2 2\n0 2\n2 2 3\n']

Demo Output:
['YES\n1 -1 2 -1 \n', 'YES\n1 -1 2 -1 3 -1 \n', 'NO\n']

Note:
none

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given *n* integers *a*1,<=*a*2,<=...,<=*a**n*. Find the number of pairs of indexes *i*,<=*j* (*i*<=&lt;<=*j*) that *a**i*<=+<=*a**j* is a power of 2 (i. e. some integer *x* exists so that *a**i*<=+<=*a**j*<==<=2*x*).

Input Specification:
The first line contains the single positive integer *n* (1<=≤<=*n*<=≤<=105) — the number of integers.

The second line contains *n* positive integers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=109).

Output Specification:
Print the number of pairs of indexes *i*,<=*j* (*i*<=&lt;<=*j*) that *a**i*<=+<=*a**j* is a power of 2.

Demo Input:
['4\n7 3 2 1\n', '3\n1 1 1\n']

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

Note:
In the first example the following pairs of indexes include in answer: (1, 4) and (2, 4).

In the second example all pairs of indexes (*i*, *j*) (where *i* &lt; *j*) include in answer.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This will probably be a little series :)

X-Shape

You will get an odd Integer n (>= 3) and your task is to draw a X. Each line is separated with '\n'.

Use the following characters:  ■ □

For Ruby, Crystal and PHP:   whitespace and o 

e.g.:



                                     ■□□□■
            ■□■                      □■□■□
  x(3) =>   □■□              x(5)=>  □□■□□
            ■□■                      □■□■□
                                     ■□□□■


 Series: ASCII Fun

ASCII Fun #1: X-Shape
ASCII Fun #2: Funny Dots
ASCII Fun #3: Puzzle Tiles
ASCII Fun #4: Build a pyramid

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a long plate s containing n digits. Iahub wants to delete some digits (possibly none, but he is not allowed to delete all the digits) to form his "magic number" on the plate, a number that is divisible by 5. Note that, the resulting number may contain leading zeros.

Now Iahub wants to count the number of ways he can obtain magic number, modulo 1000000007 (10^9 + 7). Two ways are different, if the set of deleted positions in s differs.

Look at the input part of the statement, s is given in a special form.


-----Input-----

In the first line you're given a string a (1 ≤ |a| ≤ 10^5), containing digits only. In the second line you're given an integer k (1 ≤ k ≤ 10^9). The plate s is formed by concatenating k copies of a together. That is n = |a|·k.


-----Output-----

Print a single integer — the required number of ways modulo 1000000007 (10^9 + 7).


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

Output
4

Input
13990
2

Output
528

Input
555
2

Output
63



-----Note-----

In the first case, there are four possible ways to make a number that is divisible by 5: 5, 15, 25 and 125.

In the second case, remember to concatenate the copies of a. The actual plate is 1399013990.

In the third case, except deleting all digits, any choice will do. Therefore there are 2^6 - 1 = 63 possible ways to delete digits.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Create a function which answers the question "Are you playing banjo?".  
If your name starts with the letter "R" or lower case "r", you are playing banjo!

The function takes a name as its only argument, and returns one of the following strings:
```
name + " plays banjo" 
name + " does not play banjo"
```
Names given are always valid strings.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya has n days of vacations! So he decided to improve his IT skills and do sport. Vasya knows the following information about each of this n days: whether that gym opened and whether a contest was carried out in the Internet on that day. For the i-th day there are four options:

  on this day the gym is closed and the contest is not carried out;  on this day the gym is closed and the contest is carried out;  on this day the gym is open and the contest is not carried out;  on this day the gym is open and the contest is carried out. 

On each of days Vasya can either have a rest or write the contest (if it is carried out on this day), or do sport (if the gym is open on this day).

Find the minimum number of days on which Vasya will have a rest (it means, he will not do sport and write the contest at the same time). The only limitation that Vasya has — he does not want to do the same activity on two consecutive days: it means, he will not do sport on two consecutive days, and write the contest on two consecutive days.


-----Input-----

The first line contains a positive integer n (1 ≤ n ≤ 100) — the number of days of Vasya's vacations.

The second line contains the sequence of integers a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ 3) separated by space, where: 

  a_{i} equals 0, if on the i-th day of vacations the gym is closed and the contest is not carried out;  a_{i} equals 1, if on the i-th day of vacations the gym is closed, but the contest is carried out;  a_{i} equals 2, if on the i-th day of vacations the gym is open and the contest is not carried out;  a_{i} equals 3, if on the i-th day of vacations the gym is open and the contest is carried out.


-----Output-----

Print the minimum possible number of days on which Vasya will have a rest. Remember that Vasya refuses:

  to do sport on any two consecutive days,  to write the contest on any two consecutive days. 


-----Examples-----
Input
4

1 3 2 0


Output
2


Input
7

1 3 3 2 1 2 3


Output
0


Input
2

2 2


Output
1




-----Note-----

In the first test Vasya can write the contest on the day number 1 and do sport on the day number 3. Thus, he will have a rest for only 2 days.

In the second test Vasya should write contests on days number 1, 3, 5 and 7, in other days do sport. Thus, he will not have a rest for a single day.

In the third test Vasya can do sport either on a day number 1 or number 2. He can not do sport in two days, because it will be contrary to the his limitation. Thus, he will have a rest for only one day.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Kolya is going to make fresh orange juice. He has *n* oranges of sizes *a*1,<=*a*2,<=...,<=*a**n*. Kolya will put them in the juicer in the fixed order, starting with orange of size *a*1, then orange of size *a*2 and so on. To be put in the juicer the orange must have size not exceeding *b*, so if Kolya sees an orange that is strictly greater he throws it away and continues with the next one.

The juicer has a special section to collect waste. It overflows if Kolya squeezes oranges of the total size strictly greater than *d*. When it happens Kolya empties the waste section (even if there are no more oranges) and continues to squeeze the juice. How many times will he have to empty the waste section?

Input Specification:
The first line of the input contains three integers *n*, *b* and *d* (1<=≤<=*n*<=≤<=100<=000, 1<=≤<=*b*<=≤<=*d*<=≤<=1<=000<=000) — the number of oranges, the maximum size of the orange that fits in the juicer and the value *d*, which determines the condition when the waste section should be emptied.

The second line contains *n* integers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=1<=000<=000) — sizes of the oranges listed in the order Kolya is going to try to put them in the juicer.

Output Specification:
Print one integer — the number of times Kolya will have to empty the waste section.

Demo Input:
['2 7 10\n5 6\n', '1 5 10\n7\n', '3 10 10\n5 7 7\n', '1 1 1\n1\n']

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

Note:
In the first sample, Kolya will squeeze the juice from two oranges and empty the waste section afterwards.

In the second sample, the orange won't fit in the juicer so Kolya will have no juice at all.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is an infinite board of square tiles. Initially all tiles are white.

Vova has a red marker and a blue marker. Red marker can color a tiles. Blue marker can color b tiles. If some tile isn't white then you can't use marker of any color on it. Each marker must be drained completely, so at the end there should be exactly a red tiles and exactly b blue tiles across the board.

Vova wants to color such a set of tiles that:

  * they would form a rectangle, consisting of exactly a+b colored tiles; 
  * all tiles of at least one color would also form a rectangle. 



Here are some examples of correct colorings:

<image>

Here are some examples of incorrect colorings:

<image>

Among all correct colorings Vova wants to choose the one with the minimal perimeter. What is the minimal perimeter Vova can obtain?

It is guaranteed that there exists at least one correct coloring.

Input

A single line contains two integers a and b (1 ≤ a, b ≤ 10^{14}) — the number of tiles red marker should color and the number of tiles blue marker should color, respectively.

Output

Print a single integer — the minimal perimeter of a colored rectangle Vova can obtain by coloring exactly a tiles red and exactly b tiles blue.

It is guaranteed that there exists at least one correct coloring.

Examples

Input

4 4


Output

12


Input

3 9


Output

14


Input

9 3


Output

14


Input

3 6


Output

12


Input

506 2708


Output

3218

Note

The first four examples correspond to the first picture of the statement.

Note that for there exist multiple correct colorings for all of the examples.

In the first example you can also make a rectangle with sides 1 and 8, though its perimeter will be 18 which is greater than 8.

In the second example you can make the same resulting rectangle with sides 3 and 4, but red tiles will form the rectangle with sides 1 and 3 and blue tiles will form the rectangle with sides 3 and 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In telecomunications we use information coding to detect and prevent errors while sending data. 

A parity bit is a bit added to a string of binary code that indicates whether the number of 1-bits in the string is even or odd. Parity bits are used as the simplest form of error detecting code, and can detect a 1 bit error.

In this case we are using even parity: the parity bit is set to `0` if the number of `1`-bits is even, and is set to `1` if odd.  

We are using them for the transfer of ASCII characters in binary (7-bit strings): the parity is added to the end of the 7-bit string, forming the 8th bit.

In this Kata you are to test for 1-bit errors and return a new string consisting of all of the correct ASCII caracters **in 7 bit format** (removing the parity bit), or `"error"` in place of ASCII characters in which errors were detected.

For more information on parity bits: https://en.wikipedia.org/wiki/Parity_bit


## Examples

Correct 7 bit string with an even parity bit as the 8th bit:
```
"01011001" <-- The "1" on the right is the parity bit.
```

In this example, there are three 1-bits. Three is an odd number, and the parity bit is set to `1`. No errors are detected, so return `"0101100"` (7 bits).

Example of a string of ASCII characters:
```
"01011001 01101110 01100000 01010110 10001111 01100011"
```
This should return:
```
"0101100 error 0110000 0101011 error 0110001"
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A little boy Laurenty has been playing his favourite game Nota for quite a while and is now very hungry. The boy wants to make sausage and cheese sandwiches, but first, he needs to buy a sausage and some cheese.

The town where Laurenty lives in is not large. The houses in it are located in two rows, n houses in each row. Laurenty lives in the very last house of the second row. The only shop in town is placed in the first house of the first row.

The first and second rows are separated with the main avenue of the city. The adjacent houses of one row are separated by streets.

Each crosswalk of a street or an avenue has some traffic lights. In order to cross the street, you need to press a button on the traffic light, wait for a while for the green light and cross the street. Different traffic lights can have different waiting time.

The traffic light on the crosswalk from the j-th house of the i-th row to the (j + 1)-th house of the same row has waiting time equal to a_{ij} (1 ≤ i ≤ 2, 1 ≤ j ≤ n - 1). For the traffic light on the crossing from the j-th house of one row to the j-th house of another row the waiting time equals b_{j} (1 ≤ j ≤ n). The city doesn't have any other crossings.

The boy wants to get to the store, buy the products and go back. The main avenue of the city is wide enough, so the boy wants to cross it exactly once on the way to the store and exactly once on the way back home. The boy would get bored if he had to walk the same way again, so he wants the way home to be different from the way to the store in at least one crossing. [Image] Figure to the first sample. 

Help Laurenty determine the minimum total time he needs to wait at the crossroads.


-----Input-----

The first line of the input contains integer n (2 ≤ n ≤ 50) — the number of houses in each row. 

Each of the next two lines contains n - 1 space-separated integer — values a_{ij} (1 ≤ a_{ij} ≤ 100). 

The last line contains n space-separated integers b_{j} (1 ≤ b_{j} ≤ 100).


-----Output-----

Print a single integer — the least total time Laurenty needs to wait at the crossroads, given that he crosses the avenue only once both on his way to the store and on his way back home.


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

Output
12

Input
3
1 2
3 3
2 1 3

Output
11

Input
2
1
1
1 1

Output
4



-----Note-----

The first sample is shown on the figure above. 

In the second sample, Laurenty's path can look as follows:   Laurenty crosses the avenue, the waiting time is 3;  Laurenty uses the second crossing in the first row, the waiting time is 2;  Laurenty uses the first crossing in the first row, the waiting time is 1;  Laurenty uses the first crossing in the first row, the waiting time is 1;  Laurenty crosses the avenue, the waiting time is 1;  Laurenty uses the second crossing in the second row, the waiting time is 3.  In total we get that the answer equals 11.

In the last sample Laurenty visits all the crossings, so the answer is 4.

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