vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Chef has decided to join a Gym in ChefLand and if possible, also hire a personal trainer at the gym. The monthly cost of the gym is X and personal training will cost him an additional Y per month. Chef's total budget per month is only Z. Print 1 if Chef can only join the gym, 2 if he can also have a personal trainer, and 0 if he can't even join the gym.

Note that if Chef wants to hire a personal trainer, he *must* join the gym — he cannot hire the trainer without joining the gym.

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

- The first line of input will contain a single integer T, denoting the number of test cases. Then the test cases follow.
- Each test case consists of a single line of input containing three space-separated integers X, Y, Z.

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

For each test case, output in a single line 2 if Chef can go to the gym and have a trainer, 1 if Chef can only go to the gym, 0 if he can't even go to the gym.

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

$1 ≤ T ≤ 100$
$1 ≤ X,Y,Z ≤ 100$

----- Sample Input 1 ------ 
4
1 2 3
10 12 13
23 1 22
23 1 63
----- Sample Output 1 ------ 
2
1
0
2
----- explanation 1 ------ 
Test case $1$: Since the total cost of Chef getting a gym membership and a trainer is $1+2 = 3$ which is equal to his budget of $3$, Chef can get both a gym membership and a trainer.

Test case $2$: Since the total cost of Chef getting a gym membership and a trainer is $10+12 = 22$ which is greater than his budget of $13$, he can't get both a gym membership and a trainer. However, the cost of the gym membership is $10$ which is less than his budget of $13$, so Chef can get only a gym membership.

Test case $3$: Since the cost of Chef getting a gym membership is $23$ which is greater than his budget of $22$, Chef can't even get the gym membership.

Test case $4$: The same costs as the previous test, but this time Chef has enough money to afford both the membership and a personal trainer.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Little Petya likes arrays that consist of non-negative integers a lot. Recently his mom has presented him one such array consisting of n elements. Petya immediately decided to find there a segment of consecutive elements, such that the xor of all numbers from this segment was maximal possible. Help him with that.

The xor operation is the bitwise exclusive "OR", that is denoted as "xor" in Pascal and "^" in C/C++/Java.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 100) — the number of elements in the array. The second line contains the space-separated integers from the array. All numbers are non-negative integers strictly less than 2^30.


-----Output-----

Print a single integer — the required maximal xor of a segment of consecutive elements.


-----Examples-----
Input
5
1 2 1 1 2

Output
3

Input
3
1 2 7

Output
7

Input
4
4 2 4 8

Output
14



-----Note-----

In the first sample one of the optimal segments is the segment that consists of the first and the second array elements, if we consider the array elements indexed starting from one.

The second sample contains only one optimal segment, which contains exactly one array element (element with index three).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Angry Birds is a mobile game of a big craze all over the world. You were convinced that it was a waste of time to play the game, so you decided to create an automatic solver.

<image>

You are describing a routine that optimizes the white bird's strategy to defeat a pig (enemy) by hitting an egg bomb. The white bird follows a parabolic trajectory from the initial position, and it can vertically drop egg bombs on the way.

In order to make it easy to solve, the following conditions hold for the stages.

* N obstacles are put on the stage.
* Each obstacle is a rectangle whose sides are parallel to the coordinate axes.
* The pig is put on the point (X, Y).
* You can launch the white bird in any direction at an initial velocity V from the origin.
* If the white bird collides with an obstacle, it becomes unable to drop egg bombs.
* If the egg bomb collides with an obstacle, the egg bomb is vanished.



The acceleration of gravity is 9.8 {\rm m/s^2}. Gravity exerts a force on the objects in the decreasing direction of y-coordinate.



Input

A dataset follows the format shown below:

N V X Y
L_1 B_1 R_1 T_1
...
L_N B_N R_N T_N


All inputs are integer.

* N: the number of obstacles
* V: the initial speed of the white bird
* X, Y: the position of the pig



(0 \leq N \leq 50, 0 \leq V \leq 50, 0 \leq X, Y \leq 300, X \neq 0)

for 1 \leq i \leq N,

* L_i: the x-coordinate of the left side of the i-th obstacle
* B_i: the y-coordinate of the bottom side of the i-th obstacle
* R_i: the x-coordinate of the right side of the i-th obstacle
* T_i: the y-coordinate of the top side of the i-th obstacle



(0 \leq L_i, B_i, R_i, T_i \leq 300)

It is guaranteed that the answer remains unaffected by a change of L_i, B_i, R_i and T_i in 10^{-6}.

Output

Yes/No


You should answer whether the white bird can drop an egg bomb toward the pig.

Examples

Input

0 7 3 1


Output

Yes


Input

1 7 3 1
1 1 2 2


Output

No


Input

1 7 2 2
0 1 1 2


Output

No

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp is making a quest for his friends. He has already made n tasks, for each task the boy evaluated how interesting it is as an integer q_{i}, and the time t_{i} in minutes needed to complete the task. 

An interesting feature of his quest is: each participant should get the task that is best suited for him, depending on his preferences. The task is chosen based on an interactive quiz that consists of some questions. The player should answer these questions with "yes" or "no". Depending on the answer to the question, the participant either moves to another question or goes to one of the tasks that are in the quest. In other words, the quest is a binary tree, its nodes contain questions and its leaves contain tasks. 

We know that answering any of the questions that are asked before getting a task takes exactly one minute from the quest player. Polycarp knows that his friends are busy people and they can't participate in the quest for more than T minutes. Polycarp wants to choose some of the n tasks he made, invent the corresponding set of questions for them and use them to form an interactive quiz as a binary tree so that no matter how the player answers quiz questions, he spends at most T minutes on completing the whole quest (that is, answering all the questions and completing the task). Specifically, the quest can contain zero questions and go straight to the task. Each task can only be used once (i.e., the people who give different answers to questions should get different tasks).

Polycarp wants the total "interest" value of the tasks involved in the quest to be as large as possible. Help him determine the maximum possible total interest value of the task considering that the quest should be completed in T minutes at any variant of answering questions.


-----Input-----

The first line contains two integers n and T (1 ≤ n ≤ 1000, 1 ≤ T ≤ 100) — the number of tasks made by Polycarp and the maximum time a quest player should fit into.

Next n lines contain two integers t_{i}, q_{i} (1 ≤ t_{i} ≤ T, 1 ≤ q_{i} ≤ 1000) each — the time in minutes needed to complete the i-th task and its interest value.


-----Output-----

Print a single integer — the maximum possible total interest value of all the tasks in the quest.


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

Output
11

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

Output
9

Input
2 2
1 1
2 10

Output
10



-----Note-----

In the first sample test all the five tasks can be complemented with four questions and joined into one quest.

In the second sample test it is impossible to use all the five tasks, but you can take two of them, the most interesting ones.

In the third sample test the optimal strategy is to include only the second task into the quest.

Here is the picture that illustrates the answers to the sample tests. The blue circles represent the questions, the two arrows that go from every circle represent where a person goes depending on his answer to that question. The tasks are the red ovals. [Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
- Kids drink toddy.
- Teens drink coke.
- Young adults drink beer.
- Adults drink whisky.

Make a function that receive age, and return what they drink.

**Rules:**

- Children under 14 old.
- Teens under 18 old.
- Young under 21 old.
- Adults have 21 or more.

**Examples:**

```python
people_with_age_drink(13) == "drink toddy"
people_with_age_drink(17) == "drink coke"
people_with_age_drink(18) == "drink beer"
people_with_age_drink(20) == "drink beer"
people_with_age_drink(30) == "drink whisky"
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an integer N, determine the number of pairs (A, B) such that:

1 ≤ A, B ≤ N;
A + B is odd.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of a single integer N.

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

For each test case, output the number of required pairs.

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

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 10^{9}$

----- Sample Input 1 ------ 
5
1
2
3
100
199

----- Sample Output 1 ------ 
0
2
4
5000
19800

----- explanation 1 ------ 
Test case $1$: There are no pairs satisfying the given conditions.

Test case $2$: The pairs satisfying both conditions are: $(1, 2)$ and $(2, 1)$.

Test case $3$: The pairs satisfying both conditions are: $(1, 2), (2, 1), (2, 3),$ and $(3, 2)$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a forest that we model as a plane and live $n$ rare animals. Animal number $i$ has its lair in the point $(x_{i}, y_{i})$. In order to protect them, a decision to build a nature reserve has been made.

The reserve must have a form of a circle containing all lairs. There is also a straight river flowing through the forest. All animals drink from this river, therefore it must have at least one common point with the reserve. On the other hand, ships constantly sail along the river, so the reserve must not have more than one common point with the river.

For convenience, scientists have made a transformation of coordinates so that the river is defined by $y = 0$. Check whether it is possible to build a reserve, and if possible, find the minimum possible radius of such a reserve.


-----Input-----

The first line contains one integer $n$ ($1 \le n \le 10^5$) — the number of animals. 

Each of the next $n$ lines contains two integers $x_{i}$, $y_{i}$ ($-10^7 \le x_{i}, y_{i} \le 10^7$) — the coordinates of the $i$-th animal's lair. It is guaranteed that $y_{i} \neq 0$. No two lairs coincide.


-----Output-----

If the reserve cannot be built, print $-1$. Otherwise print the minimum radius. Your answer will be accepted if absolute or relative error does not exceed $10^{-6}$.

Formally, let your answer be $a$, and the jury's answer be $b$. Your answer is considered correct if $\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$.


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

Output
0.5
Input
3
0 1
0 2
0 -3

Output
-1

Input
2
0 1
1 1

Output
0.625


-----Note-----

In the first sample it is optimal to build the reserve with the radius equal to $0.5$ and the center in $(0,\ 0.5)$.

In the second sample it is impossible to build a reserve.

In the third sample it is optimal to build the reserve with the radius equal to $\frac{5}{8}$ and the center in $(\frac{1}{2},\ \frac{5}{8})$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Two players play the following game. Initially, the players have a knife and a rectangular sheet of paper, divided into equal square grid cells of unit size. The players make moves in turn, the player who can't make a move loses. In one move, a player can take the knife and cut the paper along any segment of the grid line (not necessarily from border to border). The part of the paper, that touches the knife at least once, is considered cut. There is one limit not to turn the game into an infinite cycle: each move has to cut the paper, that is the knife has to touch the part of the paper that is not cut before.

Obviously, the game ends when the entire sheet is cut into 1 × 1 blocks. During the game, the pieces of the sheet are not allowed to move. It is also prohibited to cut along the border. The coordinates of the ends of each cut must be integers.

You are given an n × m piece of paper, somebody has already made k cuts there. Your task is to determine who will win if the players start to play on this sheet. You can consider that both players play optimally well. If the first player wins, you also need to find the winning first move.

Input

The first line contains three integers n, m, k (1 ≤ n, m ≤ 109, 0 ≤ k ≤ 105) — the sizes of the piece of paper and the number of cuts. Then follow k lines, each containing 4 integers xbi, ybi, xei, yei (0 ≤ xbi, xei ≤ n, 0 ≤ ybi, yei ≤ m) — the coordinates of the ends of the existing cuts. 

It is guaranteed that each cut has a non-zero length, is either vertical or horizontal and doesn't go along the sheet border.

The cuts may intersect, overlap and even be the same. That is, it is not guaranteed that the cuts were obtained during any correct game.

Output

If the second player wins, print "SECOND". Otherwise, in the first line print "FIRST", and in the second line print any winning move of the first player (the coordinates of the cut ends, follow input format to print them).

Examples

Input

2 1 0


Output

FIRST
1 0 1 1


Input

2 2 4
0 1 2 1
0 1 2 1
1 2 1 0
1 1 1 2


Output

SECOND

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A printer – who still uses moveable type – is preparing to print a set of pages for a book. These pages are to be numbered, as usual. The printer needs to know how many instances of each decimal digit will be required to set up the page numbers in the section of the book to be printed.

For example, if pages 10, 11, 12, 13, 14 and 15 are to be printed, computing the number of digits is relatively simple: just look at the page numbers that will appear, and count the number of times each digit appears. The digit 0 appears only once, the digit 1 appears 7 times, the digits 2, 3, 4 and 5 each appear once, and 6, 7, 8 and 9 don’t appear at all.

Your task in this problem is to provide the printer with the appropriate counts of the digits. You will be given the numbers of the two pages that identify the section of the book to be printed. You may safely assume that all pages in that section are to be numbered, that no leading zeroes will be printed, that page numbers are positive, and that no page will have more than three digits in its page number.

-----Input-----

There will be multiple cases to consider. The input for each case has two integers, A and B, each of which is guaranteed to be positive. These identify the pages to be printed. That is, each integer P between A and B, including A and B, is to be printed. A single zero will follow the input for the last case.

-----Output-----

For each input case, display the case number (1, 2, …) and the number of occurrences of each decimal digit 0 through 9 in the specified range of page numbers. Display your results in the format shown in the examples below.

-----Example-----
Input:

10 15
912 912
900 999
0

Output:

Case 1: 0:1 1:7 2:1 3:1 4:1 5:1 6:0 7:0 8:0 9:0
Case 2: 0:0 1:1 2:1 3:0 4:0 5:0 6:0 7:0 8:0 9:1
Case 3: 0:20 1:20 2:20 3:20 4:20 5:20 6:20 7:20 8:20 9:120

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given two numbers, hour and minutes. Return the smaller angle (in degrees) formed between the hour and the minute hand.
 
Example 1:

Input: hour = 12, minutes = 30
Output: 165

Example 2:

Input: hour = 3, minutes = 30
Output: 75

Example 3:

Input: hour = 3, minutes = 15
Output: 7.5

Example 4:
Input: hour = 4, minutes = 50
Output: 155

Example 5:
Input: hour = 12, minutes = 0
Output: 0

 
Constraints:

1 <= hour <= 12
0 <= minutes <= 59
Answers within 10^-5 of the actual value will be accepted as correct.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array of n integers. We need to count all values of ‘k’ such that
arr[0] % k = arr[1] % k = ....... = arr[n-1] % k 
 
Example 1:
Input:
N=3
arr[] = {38, 6, 34} 
Output: 3
Explanation:
We can have values of k as 
1, 2 and 4.  
Example 2:
Input:
N=2
arr[] = {3, 2} 
Output: 1
Your Task:
Since, this is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function printEqualModNumbers() that takes array arr and integer n as parameters and returns the desired output.
Note- If values of k are infinite return -1.
 
Expected Time Complexity: O(N^{3/2}).
Expected Auxiliary Space: O(N).
 
Constraints:
1 ≤ N ≤ 10^{5}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an integer array arr, remove a subarray (can be empty) from arr such that the remaining elements in arr are non-decreasing.
A subarray is a contiguous subsequence of the array.
Return the length of the shortest subarray to remove.
 
Example 1:
Input: arr = [1,2,3,10,4,2,3,5]
Output: 3
Explanation: The shortest subarray we can remove is [10,4,2] of length 3. The remaining elements after that will be [1,2,3,3,5] which are sorted.
Another correct solution is to remove the subarray [3,10,4].
Example 2:
Input: arr = [5,4,3,2,1]
Output: 4
Explanation: Since the array is strictly decreasing, we can only keep a single element. Therefore we need to remove a subarray of length 4, either [5,4,3,2] or [4,3,2,1].

Example 3:
Input: arr = [1,2,3]
Output: 0
Explanation: The array is already non-decreasing. We do not need to remove any elements.

Example 4:
Input: arr = [1]
Output: 0

 
Constraints:

1 <= arr.length <= 10^5
0 <= arr[i] <= 10^9

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This time Unseen gang has attack on "Island Nation". In Island Nation every city is located on an island, all the cities are connected by bridges (bidirectional). As per the plan of unseen gang, they have been successful in destroying all the bridges of the Island Nation connecting the cities. This has created terror among the peoples and government has decided to call Enigma Crew for help to maintain peace. Now, Enigma Crew has been assigned the task to construct bridges between cities, such that there exist a path between every city. As the distance between the cities vary, cost of building bridges also varies. As the economic times are not good enough, so Enigma Crew wants to minimise the total cost of construction. Now members of Enigma Crew has approached you for help in building the bridges such that cost is minimum. So given number of cities, number of bridges and cost of building that bridges, output the minimum cost for construction of bridges, such that there exist path between all the cities of Island Nation.

Input Format

First line of input contains two integers N and B, denoting number of cities and number of bridges connecting the cities respectively.
Next B lines contains, three integers a, b and c, where a and b are city names and c is the cost of bridge construction.

Output Format

Output the minimum cost of construction, fulfilling the condition that there a exist path from one city to every other cities of the Island Nation.

Constraints

1 ≤ N ≤ 100000  
1 ≤ B ≤ 100000 
1 ≤ c ≤ 100000  (cost of construction) 

SAMPLE INPUT
3 3
1 2 5
1 3 9
2 3 8

SAMPLE OUTPUT
13

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

Time Limit: 0 seconds

Memory Limit: 256 megabytes

Problem Description:
Email address in Berland is a string of the form *A*@*B*, where *A* and *B* are arbitrary strings consisting of small Latin letters. 

Bob is a system administrator in «Bersoft» company. He keeps a list of email addresses of the company's staff. This list is as a large string, where all addresses are written in arbitrary order, separated by commas. The same address can be written more than once.

Suddenly, because of unknown reasons, all commas in Bob's list disappeared. Now Bob has a string, where all addresses are written one after another without any separators, and there is impossible to determine, where the boundaries between addresses are. Unfortunately, on the same day his chief asked him to bring the initial list of addresses. Now Bob wants to disjoin addresses in some valid way. Help him to do that.

Input Specification:
The first line contains the list of addresses without separators. The length of this string is between 1 and 200, inclusive. The string consists only from small Latin letters and characters «@».

Output Specification:
If there is no list of the valid (according to the Berland rules) email addresses such that after removing all commas it coincides with the given string, output No solution. In the other case, output the list. The same address can be written in this list more than once. If there are several solutions, output any of them.

Demo Input:
['a@aa@a\n', 'a@a@a\n', '@aa@a\n']

Demo Output:
['a@a,a@a\n', 'No solution\n', 'No solution\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write a function `sumTimesTables` which sums the result of the sums of the elements specified in `tables` multiplied by all the numbers in between `min` and `max` including themselves.

For example, for `sumTimesTables([2,5],1,3)` the result should be the same as
```
2*1 + 2*2 + 2*3 +
5*1 + 5*2 + 5*3
```
i.e. the table of two from 1 to 3 plus the table of five from 1 to 3

All the numbers are integers but you must take in account:

* `tables` could be empty.
* `min` could be negative.
* `max` could be really big.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given n you have to find sum of count of divisors from1 to n.
 
Example 1:
Input: n = 2
Output: 3
Explanation: No. of Divisors of 1 = 1,
No of Divisors of 2 = 2(1, 2).
Example 2:
Input: n = 4
Output: 8
Explanation: No. of divisors of 1 = 1
No. of divisors of 2 = 2(1, 2)
No. of divisors of 3 = 2(1, 3)
No. of divisors of 4 = 3(1, 2, 4).
 
Your Task:
You don't need to read or print anything, Your task is to complete the function DivCountSum() which takes n as input parameter and returns the sum of count of divisors from 1 to n.
 
Expected Time Complexity: O(nlog(n))
Expected Space Complexity: O(n)
 
Constraints:
1 <= n <= 10^{5}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Ronny the robot is watching someone perform the Cups and Balls magic trick. The magician has one ball and three cups, he shows Ronny which cup he hides the ball under (b), he then mixes all the cups around by performing multiple two-cup switches (arr). Ronny can record the switches but can't work out where the ball is. Write a programme to help him do this. 

Rules: 
- There will only ever be three cups.
- Only two cups will be swapped at a time. 
- The cups and their switches will be refered to by their index in a row of three, beginning at one. So [[1,2]] means the cup at position one, is swapped with the cup at position two. 
- Arr will be an array of integers 1 - 3 organised in pairs. 
- There won't be any empty sub-arrays.
- If arr is just an empty array b should be returned.

Examples: 

(b) = 2, 
(arr) = [[1,2]]

The ball is under cup number : 1

-------

(b) = 1, 
(arr) = [[2,3],[1,2],[1,2]]

The ball is under cup number : 1

-------

(b) = 2, 
(arr) = [[1,3],[1,2],[2,1],[2,3]]

The ball is under cup number : 3

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