vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Below is a right-angled triangle:

```
  |\
  | \
  |  \
  |   \ 
o |    \ h 
  |     \
  |    θ \
  |_______\ 
     a
```

Your challange is to write a function (```missingAngle``` in C/C#, ```missing_angle``` in Ruby), that calculates the angle θ in degrees to the nearest integer. You will be given three arguments representing each side: o, h and a. One of the arguments equals zero. Use the length of the two other sides to calculate θ. You will not be expected to handle any erronous data in your solution.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a permutation p of length n. Also you are given m foe pairs (a_{i}, b_{i}) (1 ≤ a_{i}, b_{i} ≤ n, a_{i} ≠ b_{i}). 

Your task is to count the number of different intervals (x, y) (1 ≤ x ≤ y ≤ n) that do not contain any foe pairs. So you shouldn't count intervals (x, y) that contain at least one foe pair in it (the positions and order of the values from the foe pair are not important).

Consider some example: p = [1, 3, 2, 4] and foe pairs are {(3, 2), (4, 2)}. The interval (1, 3) is incorrect because it contains a foe pair (3, 2). The interval (1, 4) is also incorrect because it contains two foe pairs (3, 2) and (4, 2). But the interval (1, 2) is correct because it doesn't contain any foe pair.


-----Input-----

The first line contains two integers n and m (1 ≤ n, m ≤ 3·10^5) — the length of the permutation p and the number of foe pairs.

The second line contains n distinct integers p_{i} (1 ≤ p_{i} ≤ n) — the elements of the permutation p.

Each of the next m lines contains two integers (a_{i}, b_{i}) (1 ≤ a_{i}, b_{i} ≤ n, a_{i} ≠ b_{i}) — the i-th foe pair. Note a foe pair can appear multiple times in the given list.


-----Output-----

Print the only integer c — the number of different intervals (x, y) that does not contain any foe pairs.

Note that the answer can be too large, so you should use 64-bit integer type to store it. In C++ you can use the long long integer type and in Java you can use long integer type.


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

Output
5

Input
9 5
9 7 2 3 1 4 6 5 8
1 6
4 5
2 7
7 2
2 7

Output
20



-----Note-----

In the first example the intervals from the answer are (1, 1), (1, 2), (2, 2), (3, 3) and (4, 4).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef has received a challenge for which he needs your help. 

Given N, find a *permutation* P of numbers (1, 2, \ldots, N) such that:  

P_{i} \oplus P_{i+1} \neq P_{i+2} \text{ , where } (1 ≤ i ≤ N-2). Here \oplus denotes the [bitwise XOR] operation.

If multiple such permutations exist, print any. If no such permutation exists, print -1.

Note that, a *permutation* of length N is a sequence of N integers P = (P_{1}, P_{2}, \ldots, P_{N}) such that every integer from 1 to N (inclusive) appears in it exactly once. For example, (2,5,4,1,3) is a permutation of length 5 while (2, 5, 2, 1, 3) is not.

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

- First line will contain T, number of test cases. Then the test cases follow.
- Each test case contains of a single integer as input, N - the length of the required permutation.

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

For each test case, output in a new line, N space-separated integers, denoting a *permutation* satisfying the condition.  
If multiple such permutations exist, print any. If no such permutation exists, print -1.

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

$1 ≤ T ≤ 500$
$3 ≤ N ≤ 10^{5}$
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
4
3
5
10
22
----- Sample Output 1 ------ 
-1
5 1 2 4 3
1 2 4 3 6 10 8 9 7 5
10 9 8 7 6 5 1 2 4 3 11 12 13 14 15 16 17 18 19 20 21 22

----- explanation 1 ------ 
Test Case $1$: There is no permutation that satisfies the given XOR condition.

Test Case $2$: $ (5 \oplus 1 = 4) \text{ ,   } (1 \oplus 2 = 3) \text{ ,   } (2 \oplus 4 = 6) $  
Since all the adjacent XORs are different from the next term, hence, this is a valid answer.

Test Case $3$: $ (1 \oplus 2 = 3) \text{ ,   } (2 \oplus 4 = 6) \text{ ,   } (4 \oplus 3 = 7) \text{  and so on... } $  
Since all the adjacent XORs are different from the next term, hence, this is a valid answer.

Test Case $4$: $ (10 \oplus 9 = 3) \text{ ,   } (9 \oplus 8 = 1) \text{ ,   } (8 \oplus 7 = 15) \text{  and so on... } $  
Since all the adjacent XORs are different from the next term, hence, this is a valid answer.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array A, consisting of N integers and an array B, consisting of M integers.
The subsequence of A is the array that can be obtained by picking the elements at the arbitrary sorted set of positions from A.
Your task is to count the number of such subsequences C of A that:

- C contains exactly M elements.
- The array (C+B) is non-decreasing. Here by + operation, we mean element-wise sum. 

For example, the array (4, 8, 5) plus the array (10, 20, 30) is (14, 28, 35).

Formally, (C+B) is an array of size M such that (C+B)i = Ci + Bi.

In case some subsequence appears more that once, you should counts it as many times as it appears.

Formally, two subarrays of an array a, (ai_1, ai_2, ... ,ai_n) and (aj_1, aj_2, ... ,aj_m) will be considered different if either their lengths are different i.e. n != m or there exists an index k such that such that i_k  != j_k.

Since the answer can be very large, we ask you to calculate it, modulo 109+7.

-----Input-----
The first line of input contains a pair of space separated integers N and M, denoting the number of elements in the array A and the number of elements in the array B.
The second line contains N space-separated integers Ai, denoting the array A.
The third line contains M space-separated integers Bj, denoting the array B.

-----Output-----
Output a single line containing the number of subsequences C as asked in the problem, modulo 109+7.

-----Constraints-----
- 1 ≤ Ai, Bi ≤ 109
- 1 ≤ M ≤ N

-----Subtasks-----
- Subtask #1 (33 points): 1 ≤ N ≤ 50, 1 ≤ M ≤ 5
- Subtask #2 (33 points): 1 ≤ N ≤ 500, 1 ≤ M ≤ 50
- Subtask #3 (34 points): 1 ≤ N ≤ 2000, 1 ≤ M ≤ 1000

-----Example-----
Input #1:
5 3
1 5 2 4 7
7 9 6

Output #1:
4

Input #2:
4 2
7 7 7 7
3 4

Output #2:
6

-----Explanation-----
Example case 1. The suitable subsequences are (1, 2, 7), (1, 4, 7), (5, 4, 7), (2, 4, 7).
Example case 2. The suitable subsequence is (7, 7), and it appears 6 times:

- at indices (1, 2)
- at indices (1, 3)
- at indices (1, 4)
- at indices (2, 3)
- at indices (2, 4)
- at indices (3, 4)

So, the answer is 6.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Easy and hard versions are actually different problems, so read statements of both problems completely and carefully.

Summer vacation has started so Alice and Bob want to play and joy, but... Their mom doesn't think so. She says that they have to read exactly $m$ books before all entertainments. Alice and Bob will read each book together to end this exercise faster.

There are $n$ books in the family library. The $i$-th book is described by three integers: $t_i$ — the amount of time Alice and Bob need to spend to read it, $a_i$ (equals $1$ if Alice likes the $i$-th book and $0$ if not), and $b_i$ (equals $1$ if Bob likes the $i$-th book and $0$ if not).

So they need to choose exactly $m$ books from the given $n$ books in such a way that:  Alice likes at least $k$ books from the chosen set and Bob likes at least $k$ books from the chosen set;  the total reading time of these $m$ books is minimized (they are children and want to play and joy as soon a possible). 

The set they choose is the same for both Alice an Bob (it's shared between them) and they read all books together, so the total reading time is the sum of $t_i$ over all books that are in the chosen set.

Your task is to help them and find any suitable set of books or determine that it is impossible to find such a set.


-----Input-----

The first line of the input contains three integers $n$, $m$ and $k$ ($1 \le k \le m \le n \le 2 \cdot 10^5$).

The next $n$ lines contain descriptions of books, one description per line: the $i$-th line contains three integers $t_i$, $a_i$ and $b_i$ ($1 \le t_i \le 10^4$, $0 \le a_i, b_i \le 1$), where:  $t_i$ — the amount of time required for reading the $i$-th book;  $a_i$ equals $1$ if Alice likes the $i$-th book and $0$ otherwise;  $b_i$ equals $1$ if Bob likes the $i$-th book and $0$ otherwise. 


-----Output-----

If there is no solution, print only one integer -1.

If the solution exists, print $T$ in the first line — the minimum total reading time of the suitable set of books. In the second line print $m$ distinct integers from $1$ to $n$ in any order — indices of books which are in the set you found.

If there are several answers, print any of them.


-----Examples-----
Input
6 3 1
6 0 0
11 1 0
9 0 1
21 1 1
10 1 0
8 0 1

Output
24
6 5 1 
Input
6 3 2
6 0 0
11 1 0
9 0 1
21 1 1
10 1 0
8 0 1

Output
39
4 6 5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For a dictionary $M$ that stores elements formed by a pair of a string key and an integer value, perform a sequence of the following operations. Note that each key in $M$ must be unique.

* insert($key$, $x$): Insert an element formed by a pair of $key$ and $x$ to $M$. If there is an element with $key$, replace the corresponding value with $x$.
* get($key$): Print the value with the specified $key$.

Constraints

* $1 \leq q \leq 200,000$
* $1 \leq x \leq 1,000,000,000$
* $1 \leq $ length of $key$ $ \leq 20$
* $key$ consits of lower-case letter
* For a get operation, the element with the specified key exists in $M$.

Input

The input is given in the following format.


$q$
$query_1$
$query_2$
:
$query_q$


Each query $query_i$ is given by


0 $key$ $x$


or


1 $key$


where the first digits 0, 1 and 2 represent insert and get operations respectively.

Output

For each get operation, print an integer in a line.

Example

Input

7
0 blue 4
0 red 1
0 white 5
1 red
1 blue
0 black 8
1 black


Output

1
4
8

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Arkady is playing Battleship. The rules of this game aren't really important.

There is a field of $n \times n$ cells. There should be exactly one $k$-decker on the field, i. e. a ship that is $k$ cells long oriented either horizontally or vertically. However, Arkady doesn't know where it is located. For each cell Arkady knows if it is definitely empty or can contain a part of the ship.

Consider all possible locations of the ship. Find such a cell that belongs to the maximum possible number of different locations of the ship.

Input Specification:
The first line contains two integers $n$ and $k$ ($1 \le k \le n \le 100$) — the size of the field and the size of the ship.

The next $n$ lines contain the field. Each line contains $n$ characters, each of which is either '#' (denotes a definitely empty cell) or '.' (denotes a cell that can belong to the ship).

Output Specification:
Output two integers — the row and the column of a cell that belongs to the maximum possible number of different locations of the ship.

If there are multiple answers, output any of them. In particular, if no ship can be placed on the field, you can output any cell.

Demo Input:
['4 3\n#..#\n#.#.\n....\n.###\n', '10 4\n#....##...\n.#...#....\n..#..#..#.\n...#.#....\n.#..##.#..\n.....#...#\n...#.##...\n.#...#.#..\n.....#..#.\n...#.#...#\n', '19 6\n##..............###\n#......#####.....##\n.....#########.....\n....###########....\n...#############...\n..###############..\n.#################.\n.#################.\n.#################.\n.#################.\n#####....##....####\n####............###\n####............###\n#####...####...####\n.#####..####..#####\n...###........###..\n....###########....\n.........##........\n#.................#\n']

Demo Output:
['3 2\n', '6 1\n', '1 8\n']

Note:
The picture below shows the three possible locations of the ship that contain the cell $(3, 2)$ in the first sample.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The prestigious Codeforces kindergarten consists of n kids, numbered 1 through n. Each of them are given allowance in rubles by their parents.

Today, they are going to the most famous candy shop in the town. The shop sells candies in packages: for all i between 1 and m, inclusive, it sells a package containing exactly i candies. A candy costs one ruble, so a package containing x candies costs x rubles.

The kids will purchase candies in turns, starting from kid 1. In a single turn, kid i will purchase one candy package. Due to the highly competitive nature of Codeforces kindergarten, during a turn, the number of candies contained in the package purchased by the kid will always be strictly greater than the number of candies contained in the package purchased by the kid in the preceding turn (an exception is in the first turn: the first kid may purchase any package). Then, the turn proceeds to kid i + 1, or to kid 1 if it was kid n's turn. This process can be ended at any time, but at the end of the purchase process, all the kids must have the same number of candy packages. Of course, the amount spent by each kid on the candies cannot exceed their allowance.

You work at the candy shop and would like to prepare the candies for the kids. Print the maximum number of candies that can be sold by the candy shop to the kids. If the kids cannot purchase any candy (due to insufficient allowance), print 0.

Input

The first line contains two space-separated integers n and m (2 ≤ n ≤ 2·105, 2 ≤ m ≤ 5·106, n ≤ m), denoting the number of kids and the maximum number of candies in a package sold by the candy shop, respectively.

Then n lines follow, each line will contain a single positive integer not exceeding <image> denoting the allowance of a kid in rubles. The allowances are given in order from kid 1 to kid n.

Please, do not use the %lld specificator to read or write 64-bit integers in C++. It is recommended to use cin, cout streams (also you may use %I64d specificator).

Output

Print a single integer denoting the maximum number of candies that can be sold by the candy shop.

Examples

Input

2 5
5
10


Output

13


Input

3 8
8
16
13


Output

32


Input

2 5000000
12500002500000
12500002500000


Output

12500002500000

Note

For the first example, one of the scenarios that will result in 13 purchased candies is as follows. 

  * Turn 1. Kid 1 purchases 1 candy. 
  * Turn 2. Kid 2 purchases 3 candies. 
  * Turn 3. Kid 1 purchases 4 candies. 
  * Turn 4. Kid 2 purchases 5 candies. 

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
Little Petya often travels to his grandmother in the countryside. The grandmother has a large garden, which can be represented as a rectangle 1<=×<=*n* in size, when viewed from above. This rectangle is divided into *n* equal square sections. The garden is very unusual as each of the square sections possesses its own fixed height and due to the newest irrigation system we can create artificial rain above each section.

Creating artificial rain is an expensive operation. That's why we limit ourselves to creating the artificial rain only above one section. At that, the water from each watered section will flow into its neighbouring sections if their height does not exceed the height of the section. That is, for example, the garden can be represented by a 1<=×<=5 rectangle, where the section heights are equal to 4, 2, 3, 3, 2. Then if we create an artificial rain over any of the sections with the height of 3, the water will flow over all the sections, except the ones with the height of 4. See the illustration of this example at the picture:

As Petya is keen on programming, he decided to find such a section that if we create artificial rain above it, the number of watered sections will be maximal. Help him.

Input Specification:
The first line contains a positive integer *n* (1<=≤<=*n*<=≤<=1000). The second line contains *n* positive integers which are the height of the sections. All the numbers are no less than 1 and not more than 1000.

Output Specification:
Print a single number, the maximal number of watered sections if we create artificial rain above exactly one section.

Demo Input:
['1\n2\n', '5\n1 2 1 2 1\n', '8\n1 2 1 1 1 3 3 4\n']

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Brain Network (hard)

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Breaking news from zombie neurology! It turns out that – contrary to previous beliefs – every zombie is born with a single brain, and only later it evolves into a complicated brain structure. In fact, whenever a zombie consumes a brain, a new brain appears in its nervous system and gets immediately connected to one of the already existing brains using a single brain connector. Researchers are now interested in monitoring the brain latency of a zombie. Your task is to write a program which, given a history of evolution of a zombie's nervous system, computes its brain latency at every stage.

Input Specification:
The first line of the input contains one number *n* – the number of brains in the final nervous system (2<=≤<=*n*<=≤<=200000). In the second line a history of zombie's nervous system evolution is given. For convenience, we number all the brains by 1,<=2,<=...,<=*n* in the same order as they appear in the nervous system (the zombie is born with a single brain, number 1, and subsequently brains 2,<=3,<=...,<=*n* are added). The second line contains *n*<=-<=1 space-separated numbers *p*2,<=*p*3,<=...,<=*p**n*, meaning that after a new brain *k* is added to the system, it gets connected to a parent-brain .

Output Specification:
Output *n*<=-<=1 space-separated numbers – the brain latencies after the brain number *k* is added, for *k*<==<=2,<=3,<=...,<=*n*.

Demo Input:
['6\n1\n2\n2\n1\n5\n']

Demo Output:
['1 2 2 3 4 ']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mrs. Smith is trying to contact her husband, John Smith, but she forgot the secret phone number!

The only thing Mrs. Smith remembered was that any permutation of $n$ can be a secret phone number. Only those permutations that minimize secret value might be the phone of her husband.

The sequence of $n$ integers is called a permutation if it contains all integers from $1$ to $n$ exactly once.

The secret value of a phone number is defined as the sum of the length of the longest increasing subsequence (LIS) and length of the longest decreasing subsequence (LDS). 

A subsequence $a_{i_1}, a_{i_2}, \ldots, a_{i_k}$ where $1\leq i_1 < i_2 < \ldots < i_k\leq n$ is called increasing if $a_{i_1} < a_{i_2} < a_{i_3} < \ldots < a_{i_k}$. If $a_{i_1} > a_{i_2} > a_{i_3} > \ldots > a_{i_k}$, a subsequence is called decreasing. An increasing/decreasing subsequence is called longest if it has maximum length among all increasing/decreasing subsequences.

For example, if there is a permutation $[6, 4, 1, 7, 2, 3, 5]$, LIS of this permutation will be $[1, 2, 3, 5]$, so the length of LIS is equal to $4$. LDS can be $[6, 4, 1]$, $[6, 4, 2]$, or $[6, 4, 3]$, so the length of LDS is $3$.

Note, the lengths of LIS and LDS can be different.

So please help Mrs. Smith to find a permutation that gives a minimum sum of lengths of LIS and LDS.


-----Input-----

The only line contains one integer $n$ ($1 \le n \le 10^5$) — the length of permutation that you need to build.


-----Output-----

Print a permutation that gives a minimum sum of lengths of LIS and LDS. 

If there are multiple answers, print any.


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

Output
3 4 1 2

Input
2

Output
2 1



-----Note-----

In the first sample, you can build a permutation $[3, 4, 1, 2]$. LIS is $[3, 4]$ (or $[1, 2]$), so the length of LIS is equal to $2$. LDS can be ony of $[3, 1]$, $[4, 2]$, $[3, 2]$, or $[4, 1]$. The length of LDS is also equal to $2$. The sum is equal to $4$. Note that $[3, 4, 1, 2]$ is not the only permutation that is valid.

In the second sample, you can build a permutation $[2, 1]$. LIS is $[1]$ (or $[2]$), so the length of LIS is equal to $1$. LDS is $[2, 1]$, so the length of LDS is equal to $2$. The sum is equal to $3$. Note that permutation $[1, 2]$ is also valid.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Leha somehow found an array consisting of n integers. Looking at it, he came up with a task. Two players play the game on the array. Players move one by one. The first player can choose for his move a subsegment of non-zero length with an odd sum of numbers and remove it from the array, after that the remaining parts are glued together into one array and the game continues. The second player can choose a subsegment of non-zero length with an even sum and remove it. Loses the one who can not make a move. Who will win if both play optimally?


-----Input-----

First line of input data contains single integer n (1 ≤ n ≤ 10^6) — length of the array.

Next line contains n integers a_1, a_2, ..., a_{n} (0 ≤ a_{i} ≤ 10^9).


-----Output-----

Output answer in single line. "First", if first player wins, and "Second" otherwise (without quotes).


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

Output
First

Input
2
2 2

Output
Second



-----Note-----

In first sample first player remove whole array in one move and win.

In second sample first player can't make a move and lose.

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