vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
As a tradition, every year before IOI all the members of Natalia Fan Club are invited to Malek Dance Club to have a fun night together. Malek Dance Club has 2^{n} members and coincidentally Natalia Fan Club also has 2^{n} members. Each member of MDC is assigned a unique id i from 0 to 2^{n} - 1. The same holds for each member of NFC.

One of the parts of this tradition is one by one dance, where each member of MDC dances with a member of NFC. A dance pair is a pair of numbers (a, b) such that member a from MDC dances with member b from NFC.

The complexity of a pairs' assignment is the number of pairs of dancing pairs (a, b) and (c, d) such that a < c and b > d.

You are given a binary number of length n named x. We know that member i from MDC dances with member $i \oplus x$ from NFC. Your task is to calculate the complexity of this assignment modulo 1000000007 (10^9 + 7).

Expression $x \oplus y$ denotes applying «XOR» to numbers x and y. This operation exists in all modern programming languages, for example, in C++ and Java it denotes as «^», in Pascal — «xor».


-----Input-----

The first line of input contains a binary number x of lenght n, (1 ≤ n ≤ 100).

This number may contain leading zeros.


-----Output-----

Print the complexity of the given dance assignent modulo 1000000007 (10^9 + 7).


-----Examples-----
Input
11

Output
6

Input
01

Output
2

Input
1

Output
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You've got an array, consisting of n integers a_1, a_2, ..., a_{n}. Also, you've got m queries, the i-th query is described by two integers l_{i}, r_{i}. Numbers l_{i}, r_{i} define a subsegment of the original array, that is, the sequence of numbers a_{l}_{i}, a_{l}_{i} + 1, a_{l}_{i} + 2, ..., a_{r}_{i}. For each query you should check whether the corresponding segment is a ladder. 

A ladder is a sequence of integers b_1, b_2, ..., b_{k}, such that it first doesn't decrease, then doesn't increase. In other words, there is such integer x (1 ≤ x ≤ k), that the following inequation fulfills: b_1 ≤ b_2 ≤ ... ≤ b_{x} ≥ b_{x} + 1 ≥ b_{x} + 2... ≥ b_{k}. Note that the non-decreasing and the non-increasing sequences are also considered ladders.


-----Input-----

The first line contains two integers n and m (1 ≤ n, m ≤ 10^5) — the number of array elements and the number of queries. The second line contains the sequence of integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9), where number a_{i} stands for the i-th array element.

The following m lines contain the description of the queries. The i-th line contains the description of the i-th query, consisting of two integers l_{i}, r_{i} (1 ≤ l_{i} ≤ r_{i} ≤ n) — the boundaries of the subsegment of the initial array.

The numbers in the lines are separated by single spaces.


-----Output-----

Print m lines, in the i-th line print word "Yes" (without the quotes), if the subsegment that corresponds to the i-th query is the ladder, or word "No" (without the quotes) otherwise. 


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

Output
Yes
Yes
No
Yes
No
Yes

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given $n$ intervals on the $X$ axis. Each interval $i$ is specified by its ends $[L_i, R_i]$. You want to color each interval either blue or yellow. After coloring all the intervals, the $X$ axis will will have $4$ colors:
- White, the part of $X$ axis contained in no interval
- Blue, the part of $X$ axis contained in atleast one blue colored interval and no yellow colored interval.
- Yellow, the part of $X$ axis contained in atleast one yellow colored interval and no blue colored interval.
- Green, the part of $X$ axis contained in at least one blue colored interval and at least one yellow colored interval.
You want to color the intervals so that the total length of the part colored green is maximized. If there are multiple ways to color which maximize the green part, you can output any of them.

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- The first line of each testcase contains $n$, the number of intervals.
- The $i^{\text{th}}$ of the next $n$ lines contains two integers $L_i$ and $R_i$ describing the $i^{\text{th}}$ interval.

-----Output:-----
For each testcase, output a single string on a new line, whose $i^{\text{th}}$ character is $0$ if you color the $i^{\text{th}}$ interval blue, and $1$ if you color it yellow.

-----Constraints-----
- $ 1 \leq T \leq 10^5 $
- $ 1 \leq n \leq 10^5 $
- The sum of $n$ over all testcases doesn't exceed $10^5$.
- $ 1 \leq L_i \leq R_i \leq 10^9 $ for al $ 1 \leq i \leq n$.

-----Sample Input:-----
1
3
3 7
2 5
6 9

-----Sample Output:-----
100

-----Explanation:-----
The intervals are $[3, 7]$, $[2, 5]$, $[6, 9]$. It is optimal to color them in yellow, blue and blue respectively. In this coloring:
- $[2, 3) \cup (7, 9]$ is colored blue.
- $(5, 6)$ is colored yellow.
- $[3, 5] \cup [6, 7]$ is colored green, with a total length of $(5 - 3) + (7 - 6) = 3$.
- Rest of the $X$ axis is colored white.
Please note that colors at the endpoints of the intervals don't matter when computing the lengths, and we can ignore them. Open and closed intervals have been used in the explanation section only for clarity, and it doesn't matter whether they are open or closed.
Note that 011 is also a valid output.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Captain Fint is involved in another treasure hunt, but have found only one strange problem. The problem may be connected to the treasure's location or may not. That's why captain Flint decided to leave the solving the problem to his crew and offered an absurdly high reward: one day off. The problem itself sounds like this...

There are two arrays $a$ and $b$ of length $n$. Initially, an $ans$ is equal to $0$ and the following operation is defined:   Choose position $i$ ($1 \le i \le n$);  Add $a_i$ to $ans$;  If $b_i \neq -1$ then add $a_i$ to $a_{b_i}$. 

What is the maximum $ans$ you can get by performing the operation on each $i$ ($1 \le i \le n$) exactly once?

Uncle Bogdan is eager to get the reward, so he is asking your help to find the optimal order of positions to perform the operation on them.


-----Input-----

The first line contains the integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of arrays $a$ and $b$.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($−10^6 \le a_i \le 10^6$).

The third line contains $n$ integers $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le n$ or $b_i = -1$).

Additional constraint: it's guaranteed that for any $i$ ($1 \le i \le n$) the sequence $b_i, b_{b_i}, b_{b_{b_i}}, \ldots$ is not cyclic, in other words it will always end with $-1$.


-----Output-----

In the first line, print the maximum $ans$ you can get.

In the second line, print the order of operations: $n$ different integers $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$). The $p_i$ is the position which should be chosen at the $i$-th step. If there are multiple orders, print any of them.


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

Output
10
1 2 3 

Input
2
-1 100
2 -1

Output
99
2 1 

Input
10
-10 -1 2 2 5 -2 -3 -4 2 -6
-1 -1 2 2 -1 5 5 7 7 9

Output
-9
3 5 6 1 9 4 10 7 8 2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef has an array A of length N consisting of 1 and -1 only.

In one operation, Chef can choose any index i (1≤ i ≤ N) and multiply the element A_{i} by -1.

Find the minimum number of operations required to make the sum of the array equal to 0. Output -1 if the sum of the array cannot be made 0.

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

- First line will contain T, number of test cases. Then the test cases follow.
- First line of each test case consists of a single integer N denoting the length of the array.
- Second line of each test case contains N space-separated integers A_{1}, A_{2}, \dots, A_{N} denoting the array A.

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

For each test case, output the minimum number of operations to make the sum of the array equal to 0. Output -1 if it is not possible to make the sum equal to 0.

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

$1 ≤ T ≤ 100$
$2 ≤ N ≤ 1000$
$A_{i} = 1$ or $A_{i} = -1$

----- Sample Input 1 ------ 
4
4
1 1 1 1
5
1 -1 1 -1 1
6
1 -1 -1 1 1 1
2
1 -1

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

----- explanation 1 ------ 
Test case $1$: The minimum number of operations required is $2$. In the first operation, change $A_{3}$ from $1$ to $-1$. Similarly, in the second operation, change $A_{4}$ from $1$ to $-1$. Thus, the sum of the final array is $1+1-1-1=0$.

Test case $2$: It can be proven that the sum of the array cannot be made equal to zero by making any number of operations.

Test case $3$: We can change $A_{1}$ from $1$ to $-1$ in one operation. Thus, the sum of the array becomes $-1-1-1+1+1+1=0$.

Test case $4$: The sum of the array is already zero. Thus we do not need to make any operations.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The administration of the Tomsk Region firmly believes that it's time to become a megacity (that is, get population of one million). Instead of improving the demographic situation, they decided to achieve its goal by expanding the boundaries of the city.

The city of Tomsk can be represented as point on the plane with coordinates (0; 0). The city is surrounded with n other locations, the i-th one has coordinates (xi, yi) with the population of ki people. You can widen the city boundaries to a circle of radius r. In such case all locations inside the circle and on its border are included into the city.

Your goal is to write a program that will determine the minimum radius r, to which is necessary to expand the boundaries of Tomsk, so that it becomes a megacity.

Input

The first line of the input contains two integers n and s (1 ≤ n ≤ 103; 1 ≤ s < 106) — the number of locatons around Tomsk city and the population of the city. Then n lines follow. The i-th line contains three integers — the xi and yi coordinate values of the i-th location and the number ki of people in it (1 ≤ ki < 106). Each coordinate is an integer and doesn't exceed 104 in its absolute value.

It is guaranteed that no two locations are at the same point and no location is at point (0; 0).

Output

In the output, print "-1" (without the quotes), if Tomsk won't be able to become a megacity. Otherwise, in the first line print a single real number — the minimum radius of the circle that the city needs to expand to in order to become a megacity.

The answer is considered correct if the absolute or relative error don't exceed 10 - 6.

Examples

Input

4 999998
1 1 1
2 2 1
3 3 1
2 -2 1


Output

2.8284271


Input

4 999998
1 1 2
2 2 1
3 3 1
2 -2 1


Output

1.4142136


Input

2 1
1 1 999997
2 2 1


Output

-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Kefa decided to make some money doing business on the Internet for exactly n days. He knows that on the i-th day (1 ≤ i ≤ n) he makes a_{i} money. Kefa loves progress, that's why he wants to know the length of the maximum non-decreasing subsegment in sequence a_{i}. Let us remind you that the subsegment of the sequence is its continuous fragment. A subsegment of numbers is called non-decreasing if all numbers in it follow in the non-decreasing order.

Help Kefa cope with this task!


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^5).

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


-----Output-----

Print a single integer — the length of the maximum non-decreasing subsegment of sequence a.


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

Output
3
Input
3
2 2 9

Output
3


-----Note-----

In the first test the maximum non-decreasing subsegment is the numbers from the third to the fifth one.

In the second test the maximum non-decreasing subsegment is the numbers from the first to the third one.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
There are *n* castles in the Lannister's Kingdom and some walls connect two castles, no two castles are connected by more than one wall, no wall connects a castle to itself. 

Sir Jaime Lannister has discovered that Daenerys Targaryen is going to attack his kingdom soon. Therefore he wants to defend his kingdom. He has *k* liters of a strange liquid. He wants to distribute that liquid among the castles, so each castle may contain some liquid (possibly zero or non-integer number of liters). After that the stability of a wall is defined as follows: if the wall connects two castles *a* and *b*, and they contain *x* and *y* liters of that liquid, respectively, then the strength of that wall is *x*·*y*.

Your task is to print the maximum possible sum of stabilities of the walls that Sir Jaime Lannister can achieve.

Input Specification:
The first line of the input contains two integers *n* and *k* (1<=≤<=*n*<=≤<=40, 1<=≤<=*k*<=≤<=1000).

Then *n* lines follows. The *i*-th of these lines contains *n* integers *a**i*,<=1,<=*a**i*,<=2,<=...,<=*a**i*,<=*n* (). If castles *i* and *j* are connected by a wall, then *a**i*,<=*j*<==<=1. Otherwise it is equal to 0.

It is guaranteed that *a**i*,<=*j*<==<=*a**j*,<=*i* and *a**i*,<=*i*<==<=0 for all 1<=≤<=*i*,<=*j*<=≤<=*n*.

Output Specification:
Print the maximum possible sum of stabilities of the walls that Sir Jaime Lannister can achieve.

Your answer will be considered correct if its absolute or relative error does not exceed 10<=-<=6.

Namely: let's assume that your answer is *a*, and the answer of the jury is *b*. The checker program will consider your answer correct, if .

Demo Input:
['3 1\n0 1 0\n1 0 0\n0 0 0\n', '4 4\n0 1 0 1\n1 0 1 0\n0 1 0 1\n1 0 1 0\n']

Demo Output:
['0.250000000000\n', '4.000000000000\n']

Note:
In the first sample, we can assign 0.5, 0.5, 0 liters of liquid to castles 1, 2, 3, respectively, to get the maximum sum (0.25).

In the second sample, we can assign 1.0, 1.0, 1.0, 1.0 liters of liquid to castles 1, 2, 3, 4, respectively, to get the maximum sum (4.0)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Oleg came to see the maze of mirrors. The maze is a n by n room in which each cell is either empty or contains a mirror connecting opposite corners of this cell. Mirrors in this maze reflect light in a perfect way, which causes the interesting visual effects and contributes to the loss of orientation in the maze.

Oleg is a person of curious nature, so he decided to install n lasers facing internal of the maze on the south wall of the maze. On the north wall of the maze, Oleg installed n receivers, also facing internal of the maze. Let's number lasers and receivers from west to east with distinct integers from 1 to n. Each laser sends a beam of some specific kind and receiver with number a_i should receive the beam sent from laser number i. Since two lasers' beams can't come to the same receiver, these numbers form a permutation — each of the receiver numbers occurs exactly once.

You came to the maze together with Oleg. Help him to place the mirrors in the initially empty maze so that the maximum number of lasers' beams will come to the receivers they should. There are no mirrors outside the maze, so if the laser beam leaves the maze, it will not be able to go back.

Input

The first line contains a single integer n (1 ≤ n ≤ 1000) — the size of the maze.

The second line contains a permutation of n integers a_i (1 ≤ a_i ≤ n), where a_i defines the number of the receiver, to which the beam from i-th laser should come.

Output

In the first line print the maximum possible number of laser beams, which can come to the receivers they should.

In the next n lines of length n print the arrangement of mirrors, causing such number of laser beams to come where they should. If the corresponding cell is empty, print ".", otherwise print "/" or "\", depending on the orientation of the mirror.

In your output north should be above, south should be below, and west and east should be on left and on the right respectively.

It is allowed for laser beams to come not to the receivers they correspond to, but they are not counted in the answer.

If there are multiple arrangements of mirrors leading to the optimal answer — print any of them.

Example

Input

4
4 1 3 2


Output

3
...
\..
/../
...\

Note

The picture illustrates the arrangements of the mirrors in the first example.

<image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a 2D array A, each cell is 0 (representing sea) or 1 (representing land)
A move consists of walking from one land square 4-directionally to another land square, or off the boundary of the grid.
Return the number of land squares in the grid for which we cannot walk off the boundary of the grid in any number of moves.
 
Example 1:
Input: [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
Output: 3
Explanation: 
There are three 1s that are enclosed by 0s, and one 1 that isn't enclosed because its on the boundary.
Example 2:
Input: [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
Output: 0
Explanation: 
All 1s are either on the boundary or can reach the boundary.

 
Note:

1 <= A.length <= 500
1 <= A[i].length <= 500
0 <= A[i][j] <= 1
All rows have the same size.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You will be given two numbers a and b. Your task is to print 1 if a < b, print 2 if a > b and print 3 if a = b. 
Example 1:
Input: 
a = 1234
b = 12345
Output: 1
Explanation: a < b so answer is 1.
Example 2:
Input:
a = 100
b = 1
Output: 2
Explanation: a > b, so answer is 2.
User Task:
Your task is to complete the function check() which takes 2 arguments(string a, string b) and returns the answer. You need not take input or print anything.
Expected Time Complexity: O(|a| + |b|).
Expected Auxiliary Space: O(|a| - |b|).
Constraints:
1 ≤ |a|, |b| ≤ 155^{       }
'0' ≤  a_{i},b_{i } ≤  '9'

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A permutation p is an ordered group of numbers p_1,   p_2,   ...,   p_{n}, consisting of n distinct positive integers, each is no more than n. We'll define number n as the length of permutation p_1,   p_2,   ...,   p_{n}.

Simon has a positive integer n and a non-negative integer k, such that 2k ≤ n. Help him find permutation a of length 2n, such that it meets this equation: $\sum_{i = 1}^{n}|a_{2 i - 1} - a_{2i}|-|\sum_{i = 1}^{n} a_{2 i - 1} - a_{2i}|= 2 k$.


-----Input-----

The first line contains two integers n and k (1 ≤ n ≤ 50000, 0 ≤ 2k ≤ n).


-----Output-----

Print 2n integers a_1, a_2, ..., a_2n — the required permutation a. It is guaranteed that the solution exists. If there are multiple solutions, you can print any of them.


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

Output
1 2
Input
2 1

Output
3 2 1 4

Input
4 0

Output
2 7 4 6 1 3 5 8



-----Note-----

Record |x| represents the absolute value of number x. 

In the first sample |1 - 2| - |1 - 2| = 0.

In the second sample |3 - 2| + |1 - 4| - |3 - 2 + 1 - 4| = 1 + 3 - 2 = 2.

In the third sample |2 - 7| + |4 - 6| + |1 - 3| + |5 - 8| - |2 - 7 + 4 - 6 + 1 - 3 + 5 - 8| = 12 - 12 = 0.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
While exploring the old caves, researchers found a book, or more precisely, a stash of mixed pages from a book. Luckily, all of the original pages are present and each page contains its number. Therefore, the researchers can reconstruct the book.

After taking a deeper look into the contents of these pages, linguists think that this may be some kind of dictionary. What's interesting is that this ancient civilization used an alphabet which is a subset of the English alphabet, however, the order of these letters in the alphabet is not like the one in the English language.

Given the contents of pages that researchers have found, your task is to reconstruct the alphabet of this ancient civilization using the provided pages from the dictionary.


-----Input-----

First-line contains two integers: $n$ and $k$ ($1 \le n, k \le 10^3$) — the number of pages that scientists have found and the number of words present at each page. Following $n$ groups contain a line with a single integer $p_i$ ($0 \le n \lt 10^3$) — the number of $i$-th page, as well as $k$ lines, each line containing one of the strings (up to $100$ characters) written on the page numbered $p_i$.


-----Output-----

Output a string representing the reconstructed alphabet of this ancient civilization. If the book found is not a dictionary, output "IMPOSSIBLE" without quotes. In case there are multiple solutions, output any of them.


-----Example-----
Input
3 3
2
b
b
bbac
0
a
aca
acba
1
ab
c
ccb

Output
acb

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We have N cards numbered 1, 2, ..., N. Card i (1 \leq i \leq N) has an integer A_i written in red ink on one side and an integer B_i written in blue ink on the other side. Initially, these cards are arranged from left to right in the order from Card 1 to Card N, with the red numbers facing up.

Determine whether it is possible to have a non-decreasing sequence facing up from left to right (that is, for each i (1 \leq i \leq N - 1), the integer facing up on the (i+1)-th card from the left is not less than the integer facing up on the i-th card from the left) by repeating the operation below. If the answer is yes, find the minimum number of operations required to achieve it.

* Choose an integer i (1 \leq i \leq N - 1). Swap the i-th and (i+1)-th cards from the left, then flip these two cards.

Constraints

* 1 \leq N \leq 18
* 1 \leq A_i, B_i \leq 50 (1 \leq i \leq N)
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N
A_1 A_2 ... A_N
B_1 B_2 ... B_N


Output

If it is impossible to have a non-decreasing sequence, print `-1`. If it is possible, print the minimum number of operations required to achieve it.

Examples

Input

3
3 4 3
3 2 3


Output

1


Input

2
2 1
1 2


Output

-1


Input

4
1 2 3 4
5 6 7 8


Output

0


Input

5
28 15 22 43 31
20 22 43 33 32


Output

-1


Input

5
4 46 6 38 43
33 15 18 27 37


Output

3

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


-----Input-----

The first line of the input is a string (between 1 and 50 characters long, inclusive). Each character will be a letter of English alphabet, lowercase or uppercase.

The second line of the input is an integer between 0 and 26, inclusive.


-----Output-----

Output the required string.


-----Examples-----
Input
AprilFool
14

Output
AprILFooL

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