vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
A continued fraction of height n is a fraction of form $a_{1} + \frac{1}{a_{2} + \frac{1}{\ldots + \frac{1}{a_{n}}}}$. You are given two rational numbers, one is represented as [Image] and the other one is represented as a finite fraction of height n. Check if they are equal.


-----Input-----

The first line contains two space-separated integers p, q (1 ≤ q ≤ p ≤ 10^18) — the numerator and the denominator of the first fraction.

The second line contains integer n (1 ≤ n ≤ 90) — the height of the second fraction. The third line contains n space-separated integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^18) — the continued fraction.

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


-----Output-----

Print "YES" if these fractions are equal and "NO" otherwise.


-----Examples-----
Input
9 4
2
2 4

Output
YES

Input
9 4
3
2 3 1

Output
YES

Input
9 4
3
1 2 4

Output
NO



-----Note-----

In the first sample $2 + \frac{1}{4} = \frac{9}{4}$.

In the second sample $2 + \frac{1}{3 + \frac{1}{1}} = 2 + \frac{1}{4} = \frac{9}{4}$.

In the third sample $1 + \frac{1}{2 + \frac{1}{4}} = \frac{13}{9}$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The Government of Siruseri is no different from any other when it comes to being "capital-centric" in its policies. Recently the government decided to set up a nationwide fiber-optic network to take Siruseri into the digital age. And as usual, this decision was implemented in a capital centric manner --- from each city in the country, a fiber optic cable was laid to the capital! Thus, traffic between any two cities had to go through the capital.
Soon, it became apparent that this was not quite a clever idea, since any breakdown at the capital resulted in the disconnection of services between other cities. So, in the second phase, the government plans to connect a few more pairs of cities directly by fiber-optic cables. The government has specified that this is to be done in such a way that the disruption of services at any one city will still leave the rest of the country connected.
The government has data on the cost of laying fiber optic cables between every pair of cities. You task is to compute the minimum cost of additional cabling required to ensure the requirement described above is met.
For example, if Siruseri has $4$ cities numbered $1,2,3$ and $4$ where $1$ is the capital and further suppose that the cost of laying cables between these cities are as given in the table below:

Note that the government has already connected the capital with every other city. So, if we connect the cities $2$ and $3$ as well as $3$ and $4$, you can check that disruption of service at any one city will still leave the other cities connected. The cost of connecting these two pairs is $4 + 6 = 10$. The same effect could have been achieved by connecting $2$ and $3$ as well as $2$ and $4$, which would have cost $4 + 5 = 9$. You can check that this is the best you can do.
Your task is to write a program that allows the government to determine the minimum cost it has to incur in laying additional cables to fulfil the requirement.

-----Input:-----
- The first line of the input contains a single integer $N$ indicating the number of cities in Siruseri. You may assume that the capital city is always numbered $1$. 
- This is followed by $N$ lines of input each containing $N$ integers. 
- The $j^{th}$ integer on line $i$ is the cost of connecting city $i$ with city $j$. The $j^{th}$ integer on line $i$ will be the same as the $i^{th}$ integer on line $j$ (since the links are bidirectional) and the $i^{th}$ entry on line $i$ will always be $0$ (there is no cost in connecting a city with itself).

-----Output:-----
A single integer indicating the minimum total cost of the links to be added to ensure that disruption of services at one city does not disconnect the rest of the cities.

-----Constraints:-----
- $1 \leq N \leq 2000$.
- $0 \leq$ costs given in the input $\leq 100000$

-----Sample Input-----
4
0 7 8 10
7 0 4 5 
8 4 0 6
10 5 6 0

-----Sample Output-----
9

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

Find any pair of integers $(x,y)$ ($1\leq x,y\leq n$) such that $x^y\cdot y+y^x\cdot x = n$.


-----Input-----

The first line contains a single integer $t$ ($1\leq t\leq 10^4$) — the number of test cases.

Each test case contains one line with a single integer $n$ ($1\leq n\leq 10^9$).


-----Output-----

For each test case, if possible, print two integers $x$ and $y$ ($1\leq x,y\leq n$). If there are multiple answers, print any.

Otherwise, print $-1$.


-----Examples-----

Input
5
3
7
42
31250
20732790
Output
-1
-1
2 3
5 5
3 13


-----Note-----

In the third test case, $2^3 \cdot 3+3^2 \cdot 2 = 42$, so $(2,3),(3,2)$ will be considered as legal solutions.

In the fourth test case, $5^5 \cdot 5+5^5 \cdot 5 = 31250$, so $(5,5)$ is a legal solution.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given three points on a plane. You should choose some segments on the plane that are parallel to coordinate axes, so that all three points become connected. The total length of the chosen segments should be the minimal possible.

Two points $a$ and $b$ are considered connected if there is a sequence of points $p_0 = a, p_1, \ldots, p_k = b$ such that points $p_i$ and $p_{i+1}$ lie on the same segment.


-----Input-----

The input consists of three lines describing three points. Each line contains two integers $x$ and $y$ separated by a space — the coordinates of the point ($-10^9 \le x, y \le 10^9$). The points are pairwise distinct.


-----Output-----

On the first line output $n$ — the number of segments, at most 100.

The next $n$ lines should contain descriptions of segments. Output four integers $x_1$, $y_1$, $x_2$, $y_2$ on a line — the coordinates of the endpoints of the corresponding segment ($-10^9 \le x_1, y_1, x_2, y_2 \le 10^9$). Each segment should be either horizontal or vertical.

It is guaranteed that the solution with the given constraints exists.


-----Examples-----

Input
1 1
3 5
8 6
Output
3
1 1 1 5
1 5 8 5
8 5 8 6


-----Note-----

The points and the segments from the example are shown below.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N trees in a circle. Each tree has a fruit value associated with it. A bird has to sit on a tree for 0.5 sec to gather all the fruits present on the tree and then the bird can move to a neighboring tree. It takes the bird 0.5 seconds to move from one tree to another. Once all the fruits are picked from a particular tree, she can’t pick any more fruits from that tree. The maximum number of fruits she can gather is infinite.
Given N and M (the total number of seconds the bird has), and the fruit values of the trees. Maximize the total fruit value that the bird can gather. The bird can start from any tree.
 
Example 1:
Input:
N=7 M=3
arr[] = { 2 ,1 ,3 ,5 ,0 ,1 ,4 }
Output: 9
Explanation: 
She can start from tree 1 and move
to tree2 and then to tree 3.
Hence, total number of gathered fruits
= 1 + 3 + 5 = 9.
 
Example 2:
Input:
N=6 M=2
arr[] = { 1, 6, 2, 5, 3, 4 }
Output: 8
Explanation: 
She can start from tree 1 and move 
to tree 2. In this case she will gather
6 + 2 = 8 fruits. She can also start 
from tree 3 and move to tree 4. In this
case, too, she will gather 5 + 3 = 8 
fruits.
 
Your Task:
You don't need to read input, or print anything. You just need to complete the function maxFruits() that takes array arr, integer N and integer M as parameters and returns the maximum number of fruits she can gather.
 
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
 
Constraints:
2 ≤ N ≤ 10^{6}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Aizuwakamatsu City is known as the "City of History". About 400 years ago, the skeleton of the castle town was created by Gamo Ujisato, but after that, it became the central city of the Aizu clan 230,000 stones, whose ancestor was Hoshina Masayuki, the half-brother of Tokugawa's third shogun Iemitsu. Developed. Many tourists from all over the country visit every year because historic sites and remnants of old days still remain throughout the city.

This year, "Shinsengumi!" Is being broadcast in the NHK Taiga drama, so the number of tourists is increasing significantly as a place related to the Shinsengumi (* 1). Therefore, the city decided to install lanterns at intervals of 100 m along the streets connecting the historic sites scattered throughout the city. The condition is that you can reach all the historic sites in the city by following the streets decorated with lanterns, but you do not have to follow it with a single stroke. However, due to the limited budget, it is necessary to minimize the number of lanterns to be installed.

Create a program that reads the data on the street connecting the historic sites and outputs the minimum number of lanterns required. However, the distance between historic sites is greater than or equal to 200 m and is given in multiples of 100. The distance from each historic site to the nearest lantern is 100 m, and there are less than 100 historic sites in the city. There is no need to install a lantern on the historic site itself.

<image>


(* 1) The Shinsengumi was established in the form of the Aizu clan's entrustment, participated in the Aizu Boshin War known for the tragedy of Byakkotai, and Toshizo Hijikata built the grave of Isami Kondo at Tenningji Temple in the city.



Input

Given multiple datasets. Each dataset is given in the following format:


n
m
a1, b1, d1
a2, b2, d2
::
am, bm, dm


The first line of each dataset is given the number of historic sites n. It is then given a few meters of streets connecting the historic sites. The following m lines are given the three comma-separated numbers ai, bi, and di. ai and bi are historic site numbers. Historic sites are numbered from 0 to n-1. ai bi indicates that there is a street connecting them, and di represents the distance of the road between ai bi.

When n is 0, it is the last input. The number of datasets does not exceed 20.

Output

For each dataset, output the minimum number of lanterns required on one line.

Example

Input

4
4
0,1,1500
0,2,2000
1,2,600
1,3,500
0


Output

23

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The good times at Heidi's library are over. Marmots finally got their internet connections and stopped coming to the library altogether. Not only that, but the bookstore has begun charging extortionate prices for some books. Namely, whereas in the previous versions each book could be bought for 1 CHF, now the price of book *i* is *c**i* CHF.

Input Specification:
The first line of input will contain two integers *n* and *k* (). The second line will contain *n* integers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=*n*) – the sequence of book requests. The third line contains *n* integers *c*1,<=*c*2,<=...,<=*c**n* (0<=≤<=*c**i*<=≤<=106) – the costs of the books.

Output Specification:
On a single line print the minimum cost of buying books at the store so as to satisfy all requests.

Demo Input:
['4 80\n1 2 2 1\n1 1 1 1\n', '4 1\n1 2 2 1\n1 1 1 1\n', '4 2\n1 2 3 1\n1 1 1 1\n', '7 2\n1 2 3 1 1 1 2\n1 10 1 0 0 0 0\n']

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

Note:
The first three sample cases are repeated, but the fourth one is new.

In the fourth test case, when buying book 3, Heidi should discard either book 1 or 2. Even though book 2 will be requested later than book 1, she should keep it, because it is so expensive to buy again.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef has recently learned about number bases and is becoming fascinated.
Chef learned that for bases greater than ten, new digit symbols need to be introduced, and that the convention is to use the first few letters of the English alphabet. For example, in base 16, the digits are 0123456789ABCDEF. Chef thought that this is unsustainable; the English alphabet only has 26 letters, so this scheme can only work up to base 36. But this is no problem for Chef, because Chef is very creative and can just invent new digit symbols when she needs them. (Chef is very creative.)
Chef also noticed that in base two, all positive integers start with the digit 1! However, this is the only base where this is true. So naturally, Chef wonders: Given some integer N, how many bases b are there such that the base-b representation of N starts with a 1?

-----Input-----
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
Each test case consists of one line containing a single integer N (in base ten).

-----Output-----
For each test case, output a single line containing the number of bases b, or INFINITY if there are an infinite number of them.

-----Constraints-----

-----Subtasks-----Subtask #1 (16 points):
- 1 ≤ T ≤ 103
- 0 ≤ N < 103
Subtask #2 (24 points):
- 1 ≤ T ≤ 103
- 0 ≤ N < 106
Subtask #3 (28 points):
- 1 ≤ T ≤ 103
- 0 ≤ N < 1012
Subtask #4 (32 points):
- 1 ≤ T ≤ 105
- 0 ≤ N < 1012

-----Example-----
Input:4
6
9
11
24

Output:4
7
8
14

-----Explanation-----
In the first test case, 6 has a leading digit 1 in bases 2, 4, 5 and 6: 610 = 1102 = 124 = 115 = 106.

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

  * r red balls, 
  * g green balls, 
  * b blue balls, 
  * w white balls. 



He allows you to do the following operation as many times as you want: 

  * Pick a red ball, a green ball, and a blue ball and then change their color to white. 



You should answer if it's possible to arrange all the balls into a palindrome after several (possibly zero) number of described operations. 

Input

The first line contains one integer T (1≤ T≤ 100) denoting the number of test cases.

For each of the next T cases, the first line contains four integers r, g, b and w (0≤ r,g,b,w≤ 10^9).

Output

For each test case, print "Yes" if it's possible to arrange all the balls into a palindrome after doing several (possibly zero) number of described operations. Otherwise, print "No".

Example

Input


4
0 1 1 1
8 1 9 3
0 0 0 0
1000000000 1000000000 1000000000 1000000000


Output


No
Yes
Yes
Yes

Note

In the first test case, you're not able to do any operation and you can never arrange three balls of distinct colors into a palindrome.

In the second test case, after doing one operation, changing (8,1,9,3) to (7,0,8,6), one of those possible palindromes may be "rrrwwwbbbbrbbbbwwwrrr".

A palindrome is a word, phrase, or sequence that reads the same backwards as forwards. For example, "rggbwbggr", "b", "gg" are palindromes while "rgbb", "gbbgr" are not. Notice that an empty word, phrase, or sequence is palindrome.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks.Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle.

However, there is a non-negative cooling interval n that means between two same tasks, there must be at least n intervals that CPU are doing different tasks or just be idle. 

You need to return the least number of intervals the CPU will take to finish all the given tasks.

Example 1:

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.



Note:

The number of tasks is in the range [1, 10000].
The integer n is in the range [0, 100].

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
Vasya plays the sleuth with his friends. The rules of the game are as follows: those who play for the first time, that is Vasya is the sleuth, he should investigate a "crime" and find out what is happening. He can ask any questions whatsoever that can be answered with "Yes" or "No". All the rest agree beforehand to answer the questions like that: if the question’s last letter is a vowel, they answer "Yes" and if the last letter is a consonant, they answer "No". Of course, the sleuth knows nothing about it and his task is to understand that.

Unfortunately, Vasya is not very smart. After 5 hours of endless stupid questions everybody except Vasya got bored. That’s why Vasya’s friends ask you to write a program that would give answers instead of them.

The English alphabet vowels are: A, E, I, O, U, Y

The English alphabet consonants are: B, C, D, F, G, H, J, K, L, M, N, P, Q, R, S, T, V, W, X, Z

Input Specification:
The single line contains a question represented by a non-empty line consisting of large and small Latin letters, spaces and a question mark. The line length does not exceed 100. It is guaranteed that the question mark occurs exactly once in the line — as the last symbol and that the line contains at least one letter.

Output Specification:
Print answer for the question in a single line: YES if the answer is "Yes", NO if the answer is "No".

Remember that in the reply to the question the last letter, not the last character counts. I. e. the spaces and the question mark do not count as letters.

Demo Input:
['Is it a melon?\n', 'Is it an apple?\n', 'Is     it a banana ?\n', 'Is   it an apple  and a  banana   simultaneouSLY?\n']

Demo Output:
['NO\n', 'YES\n', 'YES\n', 'YES\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are going to eat X red apples and Y green apples.

You have A red apples of deliciousness p_1,p_2, \dots, p_A, B green apples of deliciousness q_1,q_2, \dots, q_B, and C colorless apples of deliciousness r_1,r_2, \dots, r_C.

Before eating a colorless apple, you can paint it red or green, and it will count as a red or green apple, respectively.

From the apples above, you will choose the apples to eat while making the sum of the deliciousness of the eaten apples as large as possible.

Find the maximum possible sum of the deliciousness of the eaten apples that can be achieved when optimally coloring zero or more colorless apples.

-----Constraints-----
 - 1 \leq X \leq A \leq 10^5
 - 1 \leq Y \leq B \leq 10^5
 - 1 \leq C \leq 10^5
 - 1 \leq p_i \leq 10^9
 - 1 \leq q_i \leq 10^9
 - 1 \leq r_i \leq 10^9
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
X Y A B C
p_1 p_2 ... p_A
q_1 q_2 ... q_B
r_1 r_2 ... r_C

-----Output-----
Print the maximum possible sum of the deliciousness of the eaten apples.

-----Sample Input-----
1 2 2 2 1
2 4
5 1
3

-----Sample Output-----
12

The maximum possible sum of the deliciousness of the eaten apples can be achieved as follows:
 - Eat the 2-nd red apple.
 - Eat the 1-st green apple.
 - Paint the 1-st colorless apple green and eat it.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Brian the Rabbit adores chess. Not long ago he argued with Stewie the Rabbit that a knight is better than a king. To prove his point he tries to show that the knight is very fast but Stewie doesn't accept statements without evidence. He constructed an infinite chessboard for Brian, where he deleted several squares to add some more interest to the game. Brian only needs to count how many different board squares a knight standing on a square with coordinates of (0, 0) can reach in no more than k moves. Naturally, it is forbidden to move to the deleted squares.

Brian doesn't very much like exact sciences himself and is not acquainted with programming, that's why he will hardly be able to get ahead of Stewie who has already started solving the problem. Help Brian to solve the problem faster than Stewie.

Input

The first line contains two integers k and n (0 ≤ k ≤ 1018, 0 ≤ n ≤ 440) which are correspondingly the maximal number of moves a knight can make and the number of deleted cells. Then follow n lines, each giving the coordinates of a deleted square in the form (xi, yi) (|xi| ≤ 10, |yi| ≤ 10). All the numbers are integer, the deleted squares are different and it is guaranteed that the square (0, 0) is not deleted.

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

Output

You must print the answer on a single line. As it can be rather long, you should print it modulo 1000000007.

Examples

Input

1 0


Output

9


Input

2 7
-1 2
1 2
2 1
2 -1
1 -2
-1 -2
-2 -1


Output

9

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have unweighted tree of $n$ vertices. You have to assign a positive weight to each edge so that the following condition would hold:

  For every two different leaves $v_{1}$ and $v_{2}$ of this tree, bitwise XOR of weights of all edges on the simple path between $v_{1}$ and $v_{2}$ has to be equal to $0$. 

Note that you can put very large positive integers (like $10^{(10^{10})}$).

It's guaranteed that such assignment always exists under given constraints. Now let's define $f$ as the number of distinct weights in assignment.

 [Image] In this example, assignment is valid, because bitwise XOR of all edge weights between every pair of leaves is $0$. $f$ value is $2$ here, because there are $2$ distinct edge weights($4$ and $5$).

[Image] In this example, assignment is invalid, because bitwise XOR of all edge weights between vertex $1$ and vertex $6$ ($3, 4, 5, 4$) is not $0$. 

What are the minimum and the maximum possible values of $f$ for the given tree? Find and print both.


-----Input-----

The first line contains integer $n$ ($3 \le n \le 10^{5}$) — the number of vertices in given tree.

The $i$-th of the next $n-1$ lines contains two integers $a_{i}$ and $b_{i}$ ($1 \le a_{i} \lt b_{i} \le n$) — it means there is an edge between $a_{i}$ and $b_{i}$. It is guaranteed that given graph forms tree of $n$ vertices.


-----Output-----

Print two integers — the minimum and maximum possible value of $f$ can be made from valid assignment of given tree. Note that it's always possible to make an assignment under given constraints.


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

Output
1 4

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

Output
3 3

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

Output
1 6



-----Note-----

In the first example, possible assignments for each minimum and maximum are described in picture below. Of course, there are multiple possible assignments for each minimum and maximum.  [Image] 

In the second example, possible assignments for each minimum and maximum are described in picture below. The $f$ value of valid assignment of this tree is always $3$.  [Image] 

In the third example, possible assignments for each minimum and maximum are described in picture below. Of course, there are multiple possible assignments for each minimum and maximum.  [Image]

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