vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Yaroslav, Andrey and Roman can play cubes for hours and hours. But the game is for three, so when Roman doesn't show up, Yaroslav and Andrey play another game. 

Roman leaves a word for each of them. Each word consists of 2·n binary characters "0" or "1". After that the players start moving in turns. Yaroslav moves first. During a move, a player must choose an integer from 1 to 2·n, which hasn't been chosen by anybody up to that moment. Then the player takes a piece of paper and writes out the corresponding character from his string. 

Let's represent Yaroslav's word as s = s_1s_2... s_2n. Similarly, let's represent Andrey's word as t = t_1t_2... t_2n. Then, if Yaroslav choose number k during his move, then he is going to write out character s_{k} on the piece of paper. Similarly, if Andrey choose number r during his move, then he is going to write out character t_{r} on the piece of paper.

The game finishes when no player can make a move. After the game is over, Yaroslav makes some integer from the characters written on his piece of paper (Yaroslav can arrange these characters as he wants). Andrey does the same. The resulting numbers can contain leading zeroes. The person with the largest number wins. If the numbers are equal, the game ends with a draw.

You are given two strings s and t. Determine the outcome of the game provided that Yaroslav and Andrey play optimally well.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 10^6). The second line contains string s — Yaroslav's word. The third line contains string t — Andrey's word.

It is guaranteed that both words consist of 2·n characters "0" and "1".


-----Output-----

Print "First", if both players play optimally well and Yaroslav wins. If Andrey wins, print "Second" and if the game ends with a draw, print "Draw". Print the words without the quotes.


-----Examples-----
Input
2
0111
0001

Output
First

Input
3
110110
001001

Output
First

Input
3
111000
000111

Output
Draw

Input
4
01010110
00101101

Output
First

Input
4
01100000
10010011

Output
Second

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are playing a variation of game 2048. Initially you have a multiset $s$ of $n$ integers. Every integer in this multiset is a power of two. 

You may perform any number (possibly, zero) operations with this multiset.

During each operation you choose two equal integers from $s$, remove them from $s$ and insert the number equal to their sum into $s$.

For example, if $s = \{1, 2, 1, 1, 4, 2, 2\}$ and you choose integers $2$ and $2$, then the multiset becomes $\{1, 1, 1, 4, 4, 2\}$.

You win if the number $2048$ belongs to your multiset. For example, if $s = \{1024, 512, 512, 4\}$ you can win as follows: choose $512$ and $512$, your multiset turns into $\{1024, 1024, 4\}$. Then choose $1024$ and $1024$, your multiset turns into $\{2048, 4\}$ and you win.

You have to determine if you can win this game.

You have to answer $q$ independent queries.


-----Input-----

The first line contains one integer $q$ ($1 \le q \le 100$) – the number of queries.

The first line of each query contains one integer $n$ ($1 \le n \le 100$) — the number of elements in multiset.

The second line of each query contains $n$ integers $s_1, s_2, \dots, s_n$ ($1 \le s_i \le 2^{29}$) — the description of the multiset. It is guaranteed that all elements of the multiset are powers of two. 


-----Output-----

For each query print YES if it is possible to obtain the number $2048$ in your multiset, and NO otherwise.

You may print every letter in any case you want (so, for example, the strings yEs, yes, Yes and YES will all be recognized as positive answer).


-----Example-----
Input
6
4
1024 512 64 512
1
2048
3
64 512 2
2
4096 4
7
2048 2 2048 2048 2048 2048 2048
2
2048 4096

Output
YES
YES
NO
NO
YES
YES



-----Note-----

In the first query you can win as follows: choose $512$ and $512$, and $s$ turns into $\{1024, 64, 1024\}$. Then choose $1024$ and $1024$, and $s$ turns into $\{2048, 64\}$ and you win.

In the second query $s$ contains $2048$ initially.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
After returned from forest, Alyona started reading a book. She noticed strings *s* and *t*, lengths of which are *n* and *m* respectively. As usual, reading bored Alyona and she decided to pay her attention to strings *s* and *t*, which she considered very similar.

Alyona has her favourite positive integer *k* and because she is too small, *k* does not exceed 10. The girl wants now to choose *k* disjoint non-empty substrings of string *s* such that these strings appear as disjoint substrings of string *t* and in the same order as they do in string *s*. She is also interested in that their length is maximum possible among all variants.

Formally, Alyona wants to find a sequence of *k* non-empty strings *p*1,<=*p*2,<=*p*3,<=...,<=*p**k* satisfying following conditions:
 -  *s* can be represented as concatenation *a*1*p*1*a*2*p*2... *a**k**p**k**a**k*<=+<=1, where *a*1,<=*a*2,<=...,<=*a**k*<=+<=1 is a sequence of arbitrary strings (some of them may be possibly empty); -  *t* can be represented as concatenation *b*1*p*1*b*2*p*2... *b**k**p**k**b**k*<=+<=1, where *b*1,<=*b*2,<=...,<=*b**k*<=+<=1 is a sequence of arbitrary strings (some of them may be possibly empty); -  sum of the lengths of strings in sequence is maximum possible. 
Please help Alyona solve this complicated problem and find at least the sum of the lengths of the strings in a desired sequence.

A substring of a string is a subsequence of consecutive characters of the string.

Input Specification:
In the first line of the input three integers *n*, *m*, *k* (1<=≤<=*n*,<=*m*<=≤<=1000, 1<=≤<=*k*<=≤<=10) are given — the length of the string *s*, the length of the string *t* and Alyona's favourite number respectively.

The second line of the input contains string *s*, consisting of lowercase English letters.

The third line of the input contains string *t*, consisting of lowercase English letters.

Output Specification:
In the only line print the only non-negative integer — the sum of the lengths of the strings in a desired sequence.

It is guaranteed, that at least one desired sequence exists.

Demo Input:
['3 2 2\nabc\nab\n', '9 12 4\nbbaaababb\nabbbabbaaaba\n']

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

Note:
The following image describes the answer for the second sample case:

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given a rectangular field of *n*<=×<=*m* cells. Each cell is either empty or impassable (contains an obstacle). Empty cells are marked with '.', impassable cells are marked with '*'. Let's call two empty cells adjacent if they share a side.

Let's call a connected component any non-extendible set of cells such that any two of them are connected by the path of adjacent cells. It is a typical well-known definition of a connected component.

For each impassable cell (*x*,<=*y*) imagine that it is an empty cell (all other cells remain unchanged) and find the size (the number of cells) of the connected component which contains (*x*,<=*y*). You should do it for each impassable cell independently.

The answer should be printed as a matrix with *n* rows and *m* columns. The *j*-th symbol of the *i*-th row should be "." if the cell is empty at the start. Otherwise the *j*-th symbol of the *i*-th row should contain the only digit —- the answer modulo 10. The matrix should be printed without any spaces.

To make your output faster it is recommended to build the output as an array of *n* strings having length *m* and print it as a sequence of lines. It will be much faster than writing character-by-character.

As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.

Input Specification:
The first line contains two integers *n*,<=*m* (1<=≤<=*n*,<=*m*<=≤<=1000) — the number of rows and columns in the field.

Each of the next *n* lines contains *m* symbols: "." for empty cells, "*" for impassable cells.

Output Specification:
Print the answer as a matrix as described above. See the examples to precise the format of the output.

Demo Input:
['3 3\n*.*\n.*.\n*.*\n', '4 5\n**..*\n..***\n.*.*.\n*.*.*\n']

Demo Output:
['3.3\n.5.\n3.3\n', '46..3\n..732\n.6.4.\n5.4.3\n']

Note:
In first example, if we imagine that the central cell is empty then it will be included to component of size 5 (cross). If any of the corner cell will be empty then it will be included to component of size 3 (corner).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It is September 9 in Japan now.
You are given a two-digit integer N. Answer the question: Is 9 contained in the decimal notation of N?

-----Constraints-----
 - 10≤N≤99

-----Input-----
Input is given from Standard Input in the following format:
N

-----Output-----
If 9 is contained in the decimal notation of N, print Yes; if not, print No.

-----Sample Input-----
29

-----Sample Output-----
Yes

The one's digit of 29 is 9.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Our world is one-dimensional, and ruled by two empires called Empire A and Empire B.
The capital of Empire A is located at coordinate X, and that of Empire B is located at coordinate Y.
One day, Empire A becomes inclined to put the cities at coordinates x_1, x_2, ..., x_N under its control, and Empire B becomes inclined to put the cities at coordinates y_1, y_2, ..., y_M under its control.
If there exists an integer Z that satisfies all of the following three conditions, they will come to an agreement, but otherwise war will break out.
 - X < Z \leq Y
 - x_1, x_2, ..., x_N < Z
 - y_1, y_2, ..., y_M \geq Z
Determine if war will break out.

-----Constraints-----
 - All values in input are integers.
 - 1 \leq N, M \leq 100
 - -100 \leq X < Y \leq 100
 - -100 \leq x_i, y_i \leq 100
 - x_1, x_2, ..., x_N \neq X
 - x_i are all different.
 - y_1, y_2, ..., y_M \neq Y
 - y_i are all different.

-----Input-----
Input is given from Standard Input in the following format:
N M X Y
x_1 x_2 ... x_N
y_1 y_2 ... y_M

-----Output-----
If war will break out, print War; otherwise, print No War.

-----Sample Input-----
3 2 10 20
8 15 13
16 22

-----Sample Output-----
No War

The choice Z = 16 satisfies all of the three conditions as follows, thus they will come to an agreement.
 - X = 10 < 16 \leq 20 = Y
 - 8, 15, 13 < 16
 - 16, 22 \geq 16

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Two players (numbered $\mbox{1}$ and $2$) are playing a game of Tower Breakers! The rules of the game are as follows:

Player $\mbox{1}$ always moves first.
Initially there are $N$ towers of various heights.
The players move in alternating turns. In each turn, a player must choose a tower of height $\mbox{X}$ and break it down into $\mathbf{Y}$ towers, each of height $\mbox{z}$. The numbers $\mathbf{Y}$ and $\mbox{z}$ must satisfy $Y\times Z=X$ and $Y>1$.  
If the current player is unable to make any move, they lose the game.

Given the value of $N$ and the respective height values for all towers, can you determine who will win, assuming both players always move optimally? If the first player wins, print $\mbox{1}$; otherwise, print $2$.

Input Format

The first line contains an integer, $\mathbf{T}$, denoting the number of test cases. 

The $2T$ subsequent lines define the test cases. Each test case is described by two lines:

An integer, $N$, denoting the number of towers.
$N$ space-separated integers, $h_0,h_1,\ldots,h_{N-1}$, where each $h_i$ describes the height of tower $\boldsymbol{i}$.

Constraints

$1\leq T\leq200$
$1\leq N\leq100$
$1\leq h_i\leq10^5$

Output Format

For each test case, print a single integer denoting the winner (i.e., either $\mbox{1}$ or $2$) on a new line.

Sample Input
2
2 
1 2
3 
1 2 3

Sample Output
1
2

Explanation

In the first test case, the first player simply breaks down the second tower of height $2$ into two towers of height $\mbox{1}$ and wins.

In the second test case, there are only two possible moves:

Break the second tower into $2$ towers of height $\mbox{1}$.
Break the third tower into $3$ towers of height $\mbox{1}$. 

Whichever move player $\mbox{1}$ makes, player $2$ can make the other move and win the game.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Maxim loves to fill in a matrix in a special manner. Here is a pseudocode of filling in a matrix of size (m + 1) × (m + 1):

[Image]

Maxim asks you to count, how many numbers m (1 ≤ m ≤ n) are there, such that the sum of values in the cells in the row number m + 1 of the resulting matrix equals t.

Expression (x xor y) means applying the operation of bitwise excluding "OR" to numbers x and y. The given operation exists in all modern programming languages. For example, in languages C++ and Java it is represented by character "^", in Pascal — by "xor".


-----Input-----

A single line contains two integers n and t (1 ≤ n, t ≤ 10^12, t ≤ n + 1).

Please, do not use the %lld specifier to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specifier.


-----Output-----

In a single line print a single integer — the answer to the problem. 


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

Output
1

Input
3 2

Output
1

Input
3 3

Output
0

Input
1000000000000 1048576

Output
118606527258

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ikshu's love for binary numbers

Ikshu recently learnt to generate random numbers. He is generating stream binary numbers. Uptil now he has generated N bits of the binary number. Now, he wants to know if there is a streak of contiguous 1's of length K.

Help him to find the probability of existence of such a streak in his binary number.

Assume that probability of generating a one and zero is equal i.e 0.5.

Input:
First and only line of input contains two space separated integers N and K as described above.

Output:
output contains one line containing probablity. output should be in n/m form where it is n/m is in its lowest fraction.

Constraints:
1 ≤ N ≤ 60
1 ≤ K ≤ N

SAMPLE INPUT
5 1

SAMPLE OUTPUT
31/32

Explanation

Ikshu generated the 5 BIT binary number. Now, Out of 32 distinct binary numbers possible there are 31 cases having atleast one set bit. So, ans is 31/32

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Two people are playing a game with a string $s$, consisting of lowercase latin letters. 

On a player's turn, he should choose two consecutive equal letters in the string and delete them. 

For example, if the string is equal to "xaax" than there is only one possible turn: delete "aa", so the string will become "xx". A player not able to make a turn loses.

Your task is to determine which player will win if both play optimally.


-----Input-----

The only line contains the string $s$, consisting of lowercase latin letters ($1 \leq |s| \leq 100\,000$), where $|s|$ means the length of a string $s$.


-----Output-----

If the first player wins, print "Yes". If the second player wins, print "No".


-----Examples-----
Input
abacaba

Output
No

Input
iiq

Output
Yes

Input
abba

Output
No



-----Note-----

In the first example the first player is unable to make a turn, so he loses.

In the second example first player turns the string into "q", then second player is unable to move, so he loses.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a cave consisting of N rooms and M one-directional passages. The rooms are numbered 1 through N.

Takahashi is now in Room 1, and Room N has the exit. The i-th passage connects Room s_i and Room t_i (s_i < t_i) and can only be traversed in the direction from Room s_i to Room t_i. It is known that, for each room except Room N, there is at least one passage going from that room.

Takahashi will escape from the cave. Each time he reaches a room (assume that he has reached Room 1 at the beginning), he will choose a passage uniformly at random from the ones going from that room and take that passage.

Aoki, a friend of Takahashi's, can block one of the passages (or do nothing) before Takahashi leaves Room 1. However, it is not allowed to block a passage so that Takahashi is potentially unable to reach Room N.

Let E be the expected number of passages Takahashi takes before he reaches Room N. Find the value of E when Aoki makes a choice that minimizes E.

Constraints

* 2 \leq N \leq 600
* N-1 \leq M \leq \frac{N(N-1)}{2}
* s_i < t_i
* If i != j, (s_i, t_i) \neq (s_j, t_j). (Added 21:23 JST)
* For every v = 1, 2, ..., N-1, there exists i such that v = s_i.

Input

Input is given from Standard Input in the following format:


N M
s_1 t_1
:
s_M t_M


Output

Print the value of E when Aoki makes a choice that minimizes E. Your output will be judged as correct when the absolute or relative error from the judge's output is at most 10^{-6}.

Examples

Input

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


Output

1.5000000000


Input

3 2
1 2
2 3


Output

2.0000000000


Input

10 33
3 7
5 10
8 9
1 10
4 6
2 5
1 7
6 10
1 4
1 3
8 10
1 5
2 6
6 9
5 6
5 8
3 6
4 8
2 7
2 9
6 7
1 2
5 9
6 8
9 10
3 9
7 8
4 5
2 10
5 7
3 5
4 7
4 9


Output

3.0133333333

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given an integer *a* that consists of *n* digits. You are also given a sequence of digits *s* of length *m*. The digit in position *j* (1<=≤<=*j*<=≤<=*m*) of sequence *s* means that you can choose an arbitrary position *i* (1<=≤<=*i*<=≤<=*n*) in *a* and replace the digit in the chosen position *i* with *s**j*. Each element in the sequence *s* can participate in no more than one replacing operation.

Your task is to perform such sequence of replacements, that the given number *a* gets maximum value. You are allowed to use not all elements from *s*.

Input Specification:
The first line contains positive integer *a*. Its length *n* is positive and doesn't exceed 105. The second line contains sequence of digits *s*. Its length *m* is positive and doesn't exceed 105. The digits in the sequence *s* are written consecutively without any separators.

The given number *a* doesn't contain leading zeroes.

Output Specification:
Print the maximum value that can be obtained from *a* after a series of replacements. You are allowed to use not all elements from *s*. The printed number shouldn't contain any leading zeroes.

Demo Input:
['1024\n010\n', '987\n1234567\n']

Demo Output:
['1124\n', '987\n']

Note:
none

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

A linear regression line has an equation in the form `$Y = a + bX$`, where `$X$` is the explanatory variable and `$Y$` is the dependent variable. The parameter `$b$` represents the *slope* of the line, while `$a$` is called the *intercept* (the value of `$y$` when `$x = 0$`).

For more details visit the related [wikipedia page](http://en.wikipedia.org/wiki/Simple_linear_regression).

---
---
#### Task:
The function that you have to write accepts two list/array, `$x$` and `$y$`,  representing the coordinates of the points to regress (so that, for example, the first point has coordinates (`x[0], y[0]`)).

Your function should return a tuple (in Python) or an array (any other language) of two elements: `a` (intercept) and `b` (slope) in this order.

You must round your result to the first 4 decimal digits

#### Formula:

   

`$x_i$` and `$y_i$` is `$x$` and `$y$` co-ordinate of `$i$`-th point;  
`$n$` is length of input.  

`$a =  \dfrac{\sum x_i^2\cdot \sum y_i - \sum x_i \cdot\sum x_iy_i}{n\sum x_i^2 - (\sum x_i)^2}$`

`$b =  \dfrac{n\sum x_i y_i - \sum x_i \cdot \sum y_i}{n\sum x^2_i - (\sum x_i)^2}$`
#### Examples:

```python
regressionLine([25,30,35,40,45,50], [78,70,65,58,48,42]) == (114.381, -1.4457)

regressionLine([56,42,72,36,63,47,55,49,38,42,68,60], [147,125,160,118,149,128,150,145,115,140,152,155]) == (80.7777, 1.138)
```
----

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let us define a magic grid to be a square matrix of integers of size n × n, satisfying the following conditions. 

  * All integers from 0 to (n^2 - 1) inclusive appear in the matrix exactly once. 
  * [Bitwise XOR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) of all elements in a row or a column must be the same for each row and column. 



You are given an integer n which is a multiple of 4. Construct a magic grid of size n × n.

Input

The only line of input contains an integer n (4 ≤ n ≤ 1000). It is guaranteed that n is a multiple of 4.

Output

Print a magic grid, i.e. n lines, the i-th of which contains n space-separated integers, representing the i-th row of the grid.

If there are multiple answers, print any. We can show that an answer always exists.

Examples

Input


4


Output


8 9 1 13
3 12 7 5
0 2 4 11
6 10 15 14

Input


8


Output


19 55 11 39 32 36 4 52
51 7 35 31 12 48 28 20
43 23 59 15 0 8 16 44
3 47 27 63 24 40 60 56
34 38 6 54 17 53 9 37
14 50 30 22 49 5 33 29
2 10 18 46 41 21 57 13
26 42 62 58 1 45 25 61

Note

In the first example, XOR of each row and each column is 13.

In the second example, XOR of each row and each column is 60.

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