vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Ashima is moody, and like most girlfriend suffers from serious mood swings. Currently, looking at Pankaj's interest in numbers, she got interested in them too. To protect himself from serious emotional blackmail, he has given Ashima some numbers to play with. Ashima being a loving girlfriend that she is, is not satisfied with playing with the numbers alone and wants Pankaj to play with her too. 

She has written down the numbers in a line and is asking Pankaj to tell her the median from some starting position to another. Pankaj has answered some such queries of her, but being playful that she is, she wants to play more. Pankaj needs your help in answering her queries. 
Definition: The median of a sequence of numbers is the middle element of that sequence when the sequence is sorted. For even number of elements in the sequence, the first of the middle two elements is called the median.
Input

The first line of the input contains N, the number of integers Pankaj gave Ashima to play with.
Next N lines contains one integer each, one of the numbers of the number given by Pankaj.
Next line contains an integer Q, the number of queries asked by Ashima. Next Q lines contain a pair of space separated integers (i, j), implying that Ashima is interested in the median of numbers in the sequence from i^th position to the j^th position (both included, 1-based indexing, i ≤ j).

Output:
Q lines, each containing the median for that particular query.
Constraints
1 ≤ N ≤ 1414
1 ≤ Q ≤ N^2
Each of the numbers in the sequence given by Pankaj to Ashima will be positive and fit into an integer.

Note: Large I/O. Be careful with certain languages.

SAMPLE INPUT
5
1
2
3
4
5
10
1 1
1 2
1 3
1 4
1 5
2 2
2 4
3 3
4 4
5 5

SAMPLE OUTPUT
1
1
2
2
3
2
3
3
4
5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Little penguin Polo adores integer segments, that is, pairs of integers [l; r] (l ≤ r). 

He has a set that consists of n integer segments: [l_1; r_1], [l_2; r_2], ..., [l_{n}; r_{n}]. We know that no two segments of this set intersect. In one move Polo can either widen any segment of the set 1 unit to the left or 1 unit to the right, that is transform [l; r] to either segment [l - 1; r], or to segment [l; r + 1].

The value of a set of segments that consists of n segments [l_1; r_1], [l_2; r_2], ..., [l_{n}; r_{n}] is the number of integers x, such that there is integer j, for which the following inequality holds, l_{j} ≤ x ≤ r_{j}.

Find the minimum number of moves needed to make the value of the set of Polo's segments divisible by k.


-----Input-----

The first line contains two integers n and k (1 ≤ n, k ≤ 10^5). Each of the following n lines contain a segment as a pair of integers l_{i} and r_{i} ( - 10^5 ≤ l_{i} ≤ r_{i} ≤ 10^5), separated by a space.

It is guaranteed that no two segments intersect. In other words, for any two integers i, j (1 ≤ i < j ≤ n) the following inequality holds, min(r_{i}, r_{j}) < max(l_{i}, l_{j}).


-----Output-----

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


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

Output
2

Input
3 7
1 2
3 3
4 7

Output
0

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
Let's imagine: there is a chess piece billiard ball. Its movements resemble the ones of a bishop chess piece. The only difference is that when a billiard ball hits the board's border, it can reflect from it and continue moving.

More formally, first one of four diagonal directions is chosen and the billiard ball moves in that direction. When it reaches the square located on the board's edge, the billiard ball reflects from it; it changes the direction of its movement by 90 degrees and continues moving. Specifically, having reached a corner square, the billiard ball is reflected twice and starts to move the opposite way. While it moves, the billiard ball can make an infinite number of reflections. At any square of its trajectory the billiard ball can stop and on that the move is considered completed.

It is considered that one billiard ball *a* beats another billiard ball *b* if *a* can reach a point where *b* is located.

You are suggested to find the maximal number of billiard balls, that pairwise do not beat each other and that can be positioned on a chessboard *n*<=×<=*m* in size.

Input Specification:
The first line contains two integers *n* and *m* (2<=≤<=*n*,<=*m*<=≤<=106).

Output Specification:
Print a single number, the maximum possible number of billiard balls that do not pairwise beat each other.

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

Demo Input:
['3 4\n', '3 3\n']

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

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A network of size $N$ contains $N$ computers connected by $N-1$ cables, so that there is exactly $1$ path between any pair of computers.

The transmission cost between $2$ computers is equal to the square of the number of cables on the path connecting the $2$ computers.

The transmission cost of a network is equal to the sum of the transmission cost between all unordered pair of computers.

Given network $A$ with $N$ computers and network $B$ with $M$ computers, the administrator wants to create a new network $C$, by adding exactly one cable connecting one computer in $A$ and one computer in $B$.

Your task is to minimize the transmission cost of the new network $C$.

-----Input-----
 - The first line contains an integer $N$ - the number of computers in the network $A$ ($1 \leq N \leq 50000$).
 - In the next $N-1$ lines, each line contains two distinct integers $u$ and $v$, representing a cable connecting computers $u$ and $v$ in network $A$ ($1 \leq u,v \leq N$).
 - The next line contains an integer $M$ - the number of computers in the network $B$ ($1 \leq M \leq 50000$).
 - In the next $M-1$ lines, each line contains two distinct integers $u$ and $v$, representing a cable connecting computers $u$ and $v$ in network $B$ ($1 \leq u,v \leq M$).

It is guaranteed that each network is a tree.

-----Output-----
Write in one line the minimum transmission cost of the resulting network $C$.

-----Sample clarification-----
In the first sample below, connecting computer $2$ of network $A$ and computer $1$ of network $B$ will minimize the transmission cost of the network.

In the second sample below, connecting computer $4$ of network $A$ and computer $1$ of network $B$ will minimize the transmission cost of the network.

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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Vasya has got $n$ books, numbered from $1$ to $n$, arranged in a stack. The topmost book has number $a_1$, the next one — $a_2$, and so on. The book at the bottom of the stack has number $a_n$. All numbers are distinct.

Vasya wants to move all the books to his backpack in $n$ steps. During $i$-th step he wants to move the book number $b_i$ into his backpack. If the book with number $b_i$ is in the stack, he takes this book and all the books above the book $b_i$, and puts them into the backpack; otherwise he does nothing and begins the next step. For example, if books are arranged in the order $[1, 2, 3]$ (book $1$ is the topmost), and Vasya moves the books in the order $[2, 1, 3]$, then during the first step he will move two books ($1$ and $2$), during the second step he will do nothing (since book $1$ is already in the backpack), and during the third step — one book (the book number $3$). Note that $b_1, b_2, \dots, b_n$ are distinct.

Help Vasya! Tell him the number of books he will put into his backpack during each step.


-----Input-----

The first line contains one integer $n~(1 \le n \le 2 \cdot 10^5)$ — the number of books in the stack.

The second line contains $n$ integers $a_1, a_2, \dots, a_n~(1 \le a_i \le n)$ denoting the stack of books.

The third line contains $n$ integers $b_1, b_2, \dots, b_n~(1 \le b_i \le n)$ denoting the steps Vasya is going to perform.

All numbers $a_1 \dots a_n$ are distinct, the same goes for $b_1 \dots b_n$.


-----Output-----

Print $n$ integers. The $i$-th of them should be equal to the number of books Vasya moves to his backpack during the $i$-th step.


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

Output
2 0 1 

Input
5
3 1 4 2 5
4 5 1 3 2

Output
3 2 0 0 0 

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

Output
1 1 2 0 1 1 



-----Note-----

The first example is described in the statement.

In the second example, during the first step Vasya will move the books $[3, 1, 4]$. After that only books $2$ and $5$ remain in the stack ($2$ is above $5$). During the second step Vasya will take the books $2$ and $5$. After that the stack becomes empty, so during next steps Vasya won't move any books.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Motu and Patlu are playing with a Magical Ball. Patlu find some interesting pattern in the motion of the ball that ball always bounce back from the ground after travelling a linear distance whose value is some power of $2$. Patlu gave Motu total distance $D$ travelled by the ball and ask him to calculate the minimum number of bounces that the ball makes before coming to rest.

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- Each testcase contains of a single line of input, single integers $D$.
- Note : Power of $2$ must be a non-negative integer. 

-----Output:-----
For each testcase, output in a single line answer, the minimum number of bounces the ball makes before coming to rest.

-----Constraints-----
- $1 \leq T \leq 10^5$
- $1$ $\leq$ $M$< $10$^18

-----Sample Input:-----
1
13 

-----Sample Output:-----
2

-----EXPLANATION:-----

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Xenny was a teacher and he had N students. The N children were sitting in a room. Each child was wearing a white T-shirt, with a unique number from the range 1 to N written on it. T-Shirts of pink and blue color were to be distributed among the students by Xenny. This made the students very happy.

Xenny felt that a random distribution of T-Shirts would be very uninteresting. So, he decided to keep an interesting condition:

Every student would get a T-Shirt that is of a different color than his/her friends. That is, if X and Y are friends and X has a Pink T-Shirt, then Y should compulsorily have a Blue T-Shirt, and vice-versa.

Also, Xenny had a belief that Boys should wear blue T-Shirts and Girls should wear pink T-Shirts. If a boy was given a pink T-Shirt or a girl was given a Blue T-Shirt, he called it an inversion.

So, Xenny wanted to distribute T-Shirts in the above-mentioned interesting manner and also wanted to minimize "inversions". Help him solve the task.

Note: There are no disjoint groups of friends in the room. That is, 2 distinct groups with finite number of students do not exist, but exactly 1 group of students exists in the given situation.

Input Format:
First line contains 2 space-separated integers - N and M - number of students and number of friendships present respectively.

Second line consists of N space-separated characters, where i^th character denotes the gender of the i^th student. B: Boy, G: Girl.

M lines follow. Each line consists of 2 space-separated integers, u and v, showing that u is a friend of v and vice-versa.

Output Format:
If Xenny could distribute the T-Shirts in the desired way, print the minimum number of inversions required.
Else, print "Not possible".

Constraints:
1 ≤ N ≤ 10^5
1 ≤ M ≤ 10^5
1 ≤ u, v ≤ N

Colours of T-Shirt are represented by uppercase characters 'B' and 'G'

SAMPLE INPUT
3 2
B G B
1 2
1 3

SAMPLE OUTPUT
1

Explanation

Student 1 can be given a Blue T-Shirt. Hence, Student 2 and 3 would receive Pink T-Shirts.

Since, Student 3 is a Boy and has received a Pink T-Shirt, number of inversions = 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A few years ago, Aaron left his old school and registered at another due to security reasons. Now he wishes to find Jane, one of his schoolmates and good friends.

There are `n` schools numbered from 1 to `n`. One can travel between each pair of schools by buying a ticket. The ticket between schools `i` and `j` costs `(i + j) modulo (n + 1)` and can be used multiple times. Help Aaron find the minimum total cost to visit all schools. He can start and finish at any school.

Range : 1 ≤ n ≤ 10^(6)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
## TL;DR

Given a number of vertices `N` and a list of weighted directed edges in a directed acyclic graph (each edge is written as `[start, end, weight]` where `from < to`), compute the weight of the shortest path from vertex `0` to vertex `N - 1`.  If there is no such path, return `-1`.

## Background

A weighted DAG is a directed acyclic graph where each edge has a weight associated with it:













1
5
3
1
5




A
B
C
D


In this example, the shortest path from A to D is given by A -> B -> D, which has a total weight of 4.

Finding shortest distances in DAGs is made easier by the fact that the nodes can be _linearized:_ they can be given an order `A1, A2, ..., An` such that edges only point forward (that is, there are no edges from `Aj` to `Ai` when `j > i`).  In the example above, the two possible linear orderings are `A, B, C, D` and `A, C, B, D.`














1

1
5
5
3





A
B
C
D


## Your Task

Given a number `N` (indicating a graph with vertices `0, 1, ..., N-1`) and a list of weighted edges `[start, end, weight]` for a DAG, where `start < end` for each edge, find the weight (a.k.a. length) of the shortest path from node `0` to node `N-1`.

For example, if the input is

```
N = 4
edgeList = [
  [0, 1, 1], [0, 2, 5], [0, 3, 5], [1, 3, 3], [2, 3, 1]
]
```

then we have the graph depicted above (with `0 = A`, `1 = B`, etc.) and the answer is `4`.

If there is no path from node `0` to node `N-1`, return `-1`.

## Notes and Warnings

**Precondition:** `N` will always be greater than 1, and edge weights will always be positive integers.  There may be multiple edges going between two nodes.

**Warning:** You will probably need to use a dynamic programming solution if you want your solution to run fast enough not to time out--that's the whole point of this kata!


However, a well-written general shortest-path algorithm such as Dijkstra's Algorithm may also be fast enough to past the soak tests.  (The reason is that the dividing line between linear and linearithmic time is hard to define and depends on a variety of external factors, so the kata's tests err on the safe side.)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Little Mirko wrote into his math notebook an equation containing three positive integers, the equals sign and one of the four basic arithmetic operations (addition, subtraction, multiplication and division).

During another class, his friend Slavko erased the equals sign and the operations from Mirko’s notebook. Help Mirko by reconstructing the equation from the three integers

-----Input-----
The first line of input contains three integers less than 100, separated by spaces. The input data will guarantee that a solution, although not necessarily unique, will always exist.

-----Output-----
On a single line, output a valid equation containing the three integers (in the same order), an equals sign and one of the four operations. If there are multiple solutions, output any of them.

-----Examples-----
Sample Input:
5 3 8
Sample Output:
5+3=8

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A factory produces thimbles in bulk. Typically, it can produce up to a thimbles a day. However, some of the machinery is defective, so it can currently only produce b thimbles each day. The factory intends to choose a k-day period to do maintenance and construction; it cannot produce any thimbles during this time, but will be restored to its full production of a thimbles per day after the k days are complete.

Initially, no orders are pending. The factory receives updates of the form d_{i}, a_{i}, indicating that a_{i} new orders have been placed for the d_{i}-th day. Each order requires a single thimble to be produced on precisely the specified day. The factory may opt to fill as many or as few of the orders in a single batch as it likes.

As orders come in, the factory owner would like to know the maximum number of orders he will be able to fill if he starts repairs on a given day p_{i}. Help the owner answer his questions.


-----Input-----

The first line contains five integers n, k, a, b, and q (1 ≤ k ≤ n ≤ 200 000, 1 ≤ b < a ≤ 10 000, 1 ≤ q ≤ 200 000) — the number of days, the length of the repair time, the production rates of the factory, and the number of updates, respectively.

The next q lines contain the descriptions of the queries. Each query is of one of the following two forms:   1 d_{i} a_{i} (1 ≤ d_{i} ≤ n, 1 ≤ a_{i} ≤ 10 000), representing an update of a_{i} orders on day d_{i}, or  2 p_{i} (1 ≤ p_{i} ≤ n - k + 1), representing a question: at the moment, how many orders could be filled if the factory decided to commence repairs on day p_{i}? 

It's guaranteed that the input will contain at least one query of the second type.


-----Output-----

For each query of the second type, print a line containing a single integer — the maximum number of orders that the factory can fill over all n days.


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

Output
3
6
4

Input
5 4 10 1 6
1 1 5
1 5 5
1 3 2
1 5 2
2 1
2 2

Output
7
1



-----Note-----

Consider the first sample.

We produce up to 1 thimble a day currently and will produce up to 2 thimbles a day after repairs. Repairs take 2 days.

For the first question, we are able to fill 1 order on day 1, no orders on days 2 and 3 since we are repairing, no orders on day 4 since no thimbles have been ordered for that day, and 2 orders for day 5 since we are limited to our production capacity, for a total of 3 orders filled.

For the third question, we are able to fill 1 order on day 1, 1 order on day 2, and 2 orders on day 5, for a total of 4 orders.

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

Find a sequence of fractions (a_i)/(b_i), i = 1 … k (where a_i and b_i are positive integers) for some k such that:

$$$ \begin{cases} $b_i$ divides $n$, $1 < b_i < n$ for $i = 1 … k$ \\\ $1 ≤ a_i < b_i$ for $i = 1 … k$ \\\ \text{$∑_{i=1}^k (a_i)/(b_i) = 1 - 1/n$} \end{cases} $$$

Input

The input consists of a single integer n (2 ≤ n ≤ 10^9).

Output

In the first line print "YES" if there exists such a sequence of fractions or "NO" otherwise.

If there exists such a sequence, next lines should contain a description of the sequence in the following format.

The second line should contain integer k (1 ≤ k ≤ 100 000) — the number of elements in the sequence. It is guaranteed that if such a sequence exists, then there exists a sequence of length at most 100 000.

Next k lines should contain fractions of the sequence with two integers a_i and b_i on each line.

Examples

Input


2


Output


NO


Input


6


Output


YES
2
1 2
1 3

Note

In the second example there is a sequence 1/2, 1/3 such that 1/2 + 1/3 = 1 - 1/6.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a sequence a = \\{a_1, ..., a_N\\} with all zeros, and a sequence b = \\{b_1, ..., b_N\\} consisting of 0 and 1. The length of both is N.

You can perform Q kinds of operations. The i-th operation is as follows:

* Replace each of a_{l_i}, a_{l_i + 1}, ..., a_{r_i} with 1.



Minimize the hamming distance between a and b, that is, the number of i such that a_i \neq b_i, by performing some of the Q operations.

Constraints

* 1 \leq N \leq 200,000
* b consists of 0 and 1.
* 1 \leq Q \leq 200,000
* 1 \leq l_i \leq r_i \leq N
* If i \neq j, either l_i \neq l_j or r_i \neq r_j.

Input

Input is given from Standard Input in the following format:


N
b_1 b_2 ... b_N
Q
l_1 r_1
l_2 r_2
:
l_Q r_Q


Output

Print the minimum possible hamming distance.

Examples

Input

3
1 0 1
1
1 3


Output

1


Input

3
1 0 1
2
1 1
3 3


Output

0


Input

3
1 0 1
2
1 1
2 3


Output

1


Input

5
0 1 0 1 0
1
1 5


Output

2


Input

9
0 1 0 1 1 1 0 1 0
3
1 4
5 8
6 7


Output

3


Input

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


Output

5


Input

10
0 0 0 1 0 0 1 1 1 0
7
1 4
2 5
1 3
6 7
9 9
1 5
7 9


Output

1

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 ≤ 106) — length of the array.

Next line contains n integers a1, a2, ..., an (0 ≤ ai ≤ 109).

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.
The only difference between easy and hard versions is the constraints.

Vova likes pictures with kittens. The news feed in the social network he uses can be represented as an array of $n$ consecutive pictures (with kittens, of course). Vova likes all these pictures, but some are more beautiful than the others: the $i$-th picture has beauty $a_i$.

Vova wants to repost exactly $x$ pictures in such a way that:   each segment of the news feed of at least $k$ consecutive pictures has at least one picture reposted by Vova;  the sum of beauty values of reposted pictures is maximum possible. 

For example, if $k=1$ then Vova has to repost all the pictures in the news feed. If $k=2$ then Vova can skip some pictures, but between every pair of consecutive pictures Vova has to repost at least one of them.

Your task is to calculate the maximum possible sum of values of reposted pictures if Vova follows conditions described above, or say that there is no way to satisfy all conditions.


-----Input-----

The first line of the input contains three integers $n, k$ and $x$ ($1 \le k, x \le n \le 200$) — the number of pictures in the news feed, the minimum length of segment with at least one repost in it and the number of pictures Vova is ready to repost.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), where $a_i$ is the beauty of the $i$-th picture.


-----Output-----

Print -1 if there is no way to repost some pictures to satisfy all the conditions in the problem statement.

Otherwise print one integer — the maximum sum of values of reposted pictures if Vova follows conditions described in the problem statement.


-----Examples-----
Input
5 2 3
5 1 3 10 1

Output
18

Input
6 1 5
10 30 30 70 10 10

Output
-1

Input
4 3 1
1 100 1 1

Output
100

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