vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
The Nordic Company of Passing Carriages is losing money at an alarming rate because most of their trains are empty. However, on some lines the passengers are complaining that they cannot fit in the cars and have to wait for the next train!

The authorities want to fix this situation. They asked their station masters to write down, for a given train, how many people left the train at their station, how many went in, and how many had to wait. Then they hired your company of highly paid consultants to assign properly sized trains to their routes.

You just received the measurements for a train, but before feeding them to your optimisation algorithm you remembered that they were collected on a snowy day, so any sensible station master would have preferred to stay inside their cabin and make up the numbers instead of going outside and counting.

Verify your hunch by checking whether the input is inconsistent, i.e., at every time the number of people in the train did not exceed the capacity nor was below $0$ and no passenger waited in vain (i.e., waited on the station when there was room in the train). The train should start and finish the journey empty, in particular passengers should not wait for the train at the last station.

-----Input-----
The first line contains two integers $C$ and $n$ ($1 \leq C \leq 10^9$, $2 \leq n \leq 100$), the total capacity and the number of stations the train stops in. The next $n$ lines contain three integers each, the number of people that left the train, entered the train, and had to stay at a station. Lines are given in the same order as the train visits each station. All integers are between $0$ and $10^9$ inclusive.

-----Output-----
One line containing one word: possible if the measurements are consistent, impossible otherwise.

-----Examples-----
Sample Input 1:
1 2
0 1 1
1 0 0
Sample Output 1:
possible

Sample Input 2:
1 2
1 0 0
0 1 0
Sample Output 2:
impossible

Sample Input 3:
1 2
0 1 0
1 0 1
Sample Output 3:
impossible

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Write a function that takes an arbitrary number of strings and interlaces them (combines them by alternating characters from each string).

For example `combineStrings('abc', '123')` should return `'a1b2c3'`.

If the strings are different lengths the function should interlace them until each string runs out, continuing to add characters from the remaining strings.

For example `combineStrings('abcd', '123')` should return `'a1b2c3d'`.

The function should take any number of arguments and combine them.

For example `combineStrings('abc', '123', '£$%')` should return `'a1£b2$c3%'`.

**Note: if only one argument is passed return only that string. If no arguments are passed return an empty string.**

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Per is repairing roads. The job is concentrated on roads with one lane in each direction. Thus, when Per closes down the lane in one direction, all traffic has to go through the other lane. This is done by allowing only one direction of travel at any time. Per is often assigned the task of directing the traffic through this lane.

No car drives before being given a “go” signal from Per, and all the cars drive through the maintained segment at the same speed. Because there is only one lane, cars in one direction must leave the segment before cars in the other direction can enter. For safety reasons, cars driving in the same direction have to keep a distance of at least $3$ seconds between each other.

For example, if cars A and B arrive at the west endpoint at second $10$, Per can let them go at earliest second $10$ and $13$ in the order they arrived. If it, in this example, takes $8$ seconds to pass and car C arrives at the east endpoint at second $17$, then car C has to wait $4$ seconds until Per lets it go at second $21$.

There is a problem of drivers getting irritated with Per; they think they have to stop for too long. Per has been logging how long they can bear to wait before they get irritated. One day, to be able to evaluate his work, Per noted down when the cars arrived at the two endpoints of the segment. Per’s question is the following: what is the least number of drivers that can be irritated? We assume that a driver gets irritated if the time between the moment he arrives at the maintained segment and the moment he is actually given the “go” exceeds his irritation time limit.

-----Input-----
The first line of the input contains two integers $t$ and $n$ ($4 \leq t \leq 180$ and $1\leq n\leq 250$), where $t$ is the time in seconds needed for a car to pass the segment under maintenance, and $n$ is the total number of cars arriving at the segment. The following $n$ lines describe the cars. The $i$-th line contains the description of the $i$-th car in the following format:
 - one character $d$, being W for cars arriving at the west endpoint of the segment, and E for the ones that arrive at the east endpoint; and
 - two integers $a$ and $r$ ($0 \leq a < 86400$ and $0 \leq r \leq 3600$), where $a$ denotes the arrival time in seconds after midnight, and $r$ denotes the time in seconds it takes for the driver to get irritated.

The cars arrive in the order specified in the input and they cannot overtake each other. In particular, a car whose driver is already irritated has to stay in the queue until eventually receiving the “go” and passing the maintained segment.

-----Output-----
Output one line with the least possible number of irritated drivers.

-----Examples-----
Sample Input:
8 3
W 10 0
W 10 3
E 17 4
Sample Output:
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Takaki Tono is a Computer Programmer in Tokyo. His boss at work shows him an online puzzle, which if solved would earn the solver a full expense paid trip to Los Angeles, California. Takaki really wants to solve this, as the love of his life, Akari, lives in Los Angeles and he hasn't met her since four years. Upon reading the puzzle he realizes that it is a query based problem. The problem is as follows :-

You are given a Tree T with N nodes numbered from 1 to N, with each node numbered z having a positive integer Az written on it. This integer denotes the value of the node. You have to process Q queries, of the following forms :- 
1) C x y : Report the closest two values in the unique path from x to y i.e compute min(|Ap - Aq|) where p and q are two distinct nodes on the unique path from x to y. 

2) F x y : Report the farthest two values in the unique path from x to y i.e. compute max(|Ap - Aq|) where p and q are two distinct nodes on the unique path from x to y.

It is also mentioned that x is not equal to y in any query and that no two nodes have the same value printed on them. Also, |x| denotes the absolute value of x. 

Takaki is perplexed and requires your help to solve this task? Can you help him out?

-----Input-----
The first line of the input contains an integer N denoting the number of nodes in tree T. 
The second line comprises N space separated integers denoting A, where the i-th integer denotes Ai. 
The next N-1 lines each comprise two space separated integers u and v, denoting that node u and node v
are connected by an edge. It is guaranteed that the final graph will be a connected tree.
The next line contains a single integer Q, denoting number of queries. 
The next Q lines comprise the queries. Each such line is of the format C x y or F x y. 

-----Output-----
For each query, print the required output as mentioned above. 

-----Constraints-----
- 2 ≤ N ≤ 35000
- 1 ≤ Ai ≤ 109
- 1 ≤ Q ≤ 35000
- 1 ≤ u, v ≤ N
- No two nodes have the same value printed on them.
- x is not equal to y in any query.

-----Subtasks-----

-----Subtasks-----Subtask #1 (15 points)
- N, Q ≤ 1000Subtask #2 (20 points)
- Only Type F queries are present.Subtask #3 (65 points)
- Original constraints

-----Example-----
Input:5
1 2 7 4 5
1 2
2 3
2 4
2 5
7
C 1 5
F 1 5
C 2 4
C 1 2
F 1 3
F 3 4
F 2 4

Output:1
4
2
1
6
5
2

-----Explanation-----
Given below is the tree corresponding to the sample input. Each node has two numbers written in it. 
The first number represents the node index and the second number indicates node value.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given two strings A and B. Find the minimum number of steps required to transform string A into string B. The only allowed operation for the transformation is selecting a character from string A and inserting it in the beginning of string A.
Example 1:
Input:
A = "abd"
B = "bad"
Output: 1
Explanation: The conversion can take place in
1 operation: Pick 'b' and place it at the front.
Example 2:
Input:
A = "GeeksForGeeks"
B = "ForGeeksGeeks"
Output: 3
Explanation: The conversion can take
place in 3 operations:
Pick 'r' and place it at the front.
A = "rGeeksFoGeeks"
Pick 'o' and place it at the front.
A = "orGeeksFGeeks"
Pick 'F' and place it at the front.
A = "ForGeeksGeeks"
Your Task:  
You dont need to read input or print anything. Complete the function transform() which takes two strings A and B as input parameters and returns the minimum number of steps required to transform A into B. If transformation is not possible return -1.
Expected Time Complexity: O(N) where N is max(length of A, length of B) 
Expected Auxiliary Space: O(1)  
Constraints:
1<= A.length(), B.length() <= 10^{4}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Shubham has an array a of size n, and wants to select exactly x elements from it, such that their sum is odd. These elements do not have to be consecutive. The elements of the array are not guaranteed to be distinct.

Tell him whether he can do so.

Input

The first line of the input contains a single integer t (1≤ t ≤ 100) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers n and x (1 ≤ x ≤ n ≤ 1000) — the length of the array and the number of elements you need to choose.

The next line of each test case contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 1000) — elements of the array.

Output

For each test case, print "Yes" or "No" depending on whether it is possible to choose x elements such that their sum is odd.

You may print every letter in any case you want.

Example

Input


5
1 1
999
1 1
1000
2 1
51 50
2 2
51 50
3 3
101 102 103


Output


Yes
No
Yes
Yes
No

Note

For 1st case: We must select element 999, and the sum is odd.

For 2nd case: We must select element 1000, so overall sum is not odd.

For 3rd case: We can select element 51.

For 4th case: We must select both elements 50 and 51 — so overall sum is odd.

For 5th case: We must select all elements — but overall sum is not odd.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Lunar New Year is approaching, and Bob is struggling with his homework – a number division problem.

There are $n$ positive integers $a_1, a_2, \ldots, a_n$ on Bob's homework paper, where $n$ is always an even number. Bob is asked to divide those numbers into groups, where each group must contain at least $2$ numbers. Suppose the numbers are divided into $m$ groups, and the sum of the numbers in the $j$-th group is $s_j$. Bob's aim is to minimize the sum of the square of $s_j$, that is $$\sum_{j = 1}^{m} s_j^2.$$

Bob is puzzled by this hard problem. Could you please help him solve it?


-----Input-----

The first line contains an even integer $n$ ($2 \leq n \leq 3 \cdot 10^5$), denoting that there are $n$ integers on Bob's homework paper.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^4$), describing the numbers you need to deal with.


-----Output-----

A single line containing one integer, denoting the minimum of the sum of the square of $s_j$, which is $$\sum_{i = j}^{m} s_j^2,$$ where $m$ is the number of groups.


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

Output
164

Input
6
1 1 1 2 2 2

Output
27



-----Note-----

In the first sample, one of the optimal solutions is to divide those $4$ numbers into $2$ groups $\{2, 8\}, \{5, 3\}$. Thus the answer is $(2 + 8)^2 + (5 + 3)^2 = 164$.

In the second sample, one of the optimal solutions is to divide those $6$ numbers into $3$ groups $\{1, 2\}, \{1, 2\}, \{1, 2\}$. Thus the answer is $(1 + 2)^2 + (1 + 2)^2 + (1 + 2)^2 = 27$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Dante is engaged in a fight with "The Savior". Before he can fight it with his sword, he needs to break its shields. He has two guns, Ebony and Ivory, each of them is able to perform any non-negative number of shots.

For every bullet that hits the shield, Ebony deals a units of damage while Ivory deals b units of damage. In order to break the shield Dante has to deal exactly c units of damage. Find out if this is possible.

Input

The first line of the input contains three integers a, b, c (1 ≤ a, b ≤ 100, 1 ≤ c ≤ 10 000) — the number of units of damage dealt by Ebony gun and Ivory gun, and the total number of damage required to break the shield, respectively.

Output

Print "Yes" (without quotes) if Dante can deal exactly c damage to the shield and "No" (without quotes) otherwise.

Examples

Input

4 6 15


Output

No


Input

3 2 7


Output

Yes


Input

6 11 6


Output

Yes

Note

In the second sample, Dante can fire 1 bullet from Ebony and 2 from Ivory to deal exactly 1·3 + 2·2 = 7 damage. In the third sample, Dante can fire 1 bullet from ebony and no bullets from ivory to do 1·6 + 0·11 = 6 damage. 

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Appleman has n cards. Each card has an uppercase letter written on it. Toastman must choose k cards from Appleman's cards. Then Appleman should give Toastman some coins depending on the chosen cards. Formally, for each Toastman's card i you should calculate how much Toastman's cards have the letter equal to letter on ith, then sum up all these quantities, such a number of coins Appleman should give to Toastman.

Given the description of Appleman's cards. What is the maximum number of coins Toastman can get?


-----Input-----

The first line contains two integers n and k (1 ≤ k ≤ n ≤ 10^5). The next line contains n uppercase letters without spaces — the i-th letter describes the i-th card of the Appleman.


-----Output-----

Print a single integer – the answer to the problem.


-----Examples-----
Input
15 10
DZFDFZDFDDDDDDF

Output
82

Input
6 4
YJSNPI

Output
4



-----Note-----

In the first test example Toastman can choose nine cards with letter D and one additional card with any letter. For each card with D he will get 9 coins and for the additional card he will get 1 coin.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef was bored staying at home in the lockdown. He wanted to go out for a change. Chef and Chefu are fond of eating Cakes,so they decided to go the Cake shop where cakes of all possible price are available .
They decided to purchase cakes of equal price and each of them will pay for their cakes. Chef only has coins of denomination $N$ whereas Chefu has that of denomination $M$.
So they want your help to find out the minimum amount to be spent in order to purchase the cakes.

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- Each testcase contains of a single line of input, two integers $N, M$. 

-----Output:-----
For each testcase, output in a single line answer the minimum amount to be spent in order to purchase the cake.

-----Constraints-----
- $1 \leq T \leq 1000$
- $2 \leq N,M \leq 10^7$

-----Sample Input:-----
1
2 3

-----Sample Output:-----
6

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The number n is Evil if it has an even number of 1's in its binary representation.
The first few Evil numbers: 3, 5, 6, 9, 10, 12, 15, 17, 18, 20
The number n is Odious if it has an odd number of 1's in its binary representation.
The first few Odious numbers: 1, 2, 4, 7, 8, 11, 13, 14, 16, 19
You have to write a function that determine if a number is Evil of Odious, function should return "It's Evil!" in case of evil number and "It's Odious!" in case of odious number.

good luck :)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Theta likes to bake cookies for the upcoming holidays. She has a selection of cookie cutters of different shapes and sizes. She thinks it’s unfair that some shapes are larger than others – because even if everyone gets the same number of cookies, some will end up with more dough!

She comes up with a plan to enlarge (or shrink) the cookie cutters’ shapes – while retaining their proportions – so that all cookies will have the same weight.

Your task in this problem is to help her draw the plans the new cookie cutters will be based on!

-----Input-----
The input is a single test case, consisting of one cookie cutter outline. Cookie cutters are modeled as simple polygons. (Simple polygons do not self-intersect.) The first line of input contains a number $N$ ($3 \le N \le 50$) denoting the number of corners of the polygon. This is followed by $N$ lines containing two floating point numbers $X$ and $Y$ ($-500 \le X, Y \le 500$), each describing a set of coordinates of a polygon point. Each floating point number will have at most $6$ digits after the period. The coordinates are given in counter-clockwise order.

The next line will contain an integer number $A$ ($0 < A \le 10000000$) denoting the size of the desired area to which the polygon should be grown or shrunk. (Since the dough is rolled out precisely to an even height everywhere, we can use area to represent weight.) The resized polygon must be similar to the original polygon, that is, all interior angles must be congruent and all corresponding sides must have the same ratio.

-----Output-----
Output $N$ lines with the $X$, $Y$ coordinates of the expanded/shrunk polygon. Because these coordinates will be used to draw a new cookie cutter, your new polygon should lie in the north-east quadrant ($x, y \ge 0$) and it should touch the $x$- and $y$-axes in at least one point. More precisely, you must move the resized polygon horizontally and/or vertically so that $\min x_ i = \min y_ j = 0$. You may not, however, rotate or skew the polygon in any way.

Provide your answers as floating point numbers. Your answer will be considered correct if none of the $x, y$ coordinates have an absolute or relative error larger than $10^{-4}$.

-----Examples-----
Sample Input:
3
0 0
1 1
0 2
4
Sample Output:
0.0 0.0
2.0 2.0
0.0 4.0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Arkady wants to have a dinner. He has just returned from a shop where he has bought a semifinished cutlet. He only needs to fry it. The cutlet should be fried for 2n seconds, in particular, it should be fried for n seconds on one side and n seconds on the other side. Arkady has already got a frying pan and turn on fire, but understood that maybe he won't be able to flip the cutlet exactly after n seconds after the beginning of cooking.

Arkady is too busy with sorting sticker packs in his favorite messenger and can flip the cutlet only in some periods of time. Namely, there are k periods of time in which he can do it, the i-th of them is an interval of time from li seconds after he starts cooking till ri seconds, inclusive. Arkady decided that it's not required to flip the cutlet exactly in the middle of cooking, instead, he will flip it several times in such a way that the cutlet will be fried exactly n seconds on one side and n seconds on the other side in total.

Help Arkady and find out if it's possible for him to cook the cutlet, if he is able to flip the cutlet only in given periods of time; and if yes, find the minimum number of flips he needs to cook the cutlet.

Input

The first line contains two integers n and k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ 100) — the number of seconds the cutlet should be cooked on each side and number of periods of time in which Arkady can flip it.

The next k lines contain descriptions of these intervals. Each line contains two integers li and ri (0 ≤ li ≤ ri ≤ 2·n), meaning that Arkady can flip the cutlet in any moment starting from li seconds after the beginning of cooking and finishing at ri seconds after beginning of cooking. In particular, if li = ri then Arkady can flip the cutlet only in the moment li = ri. It's guaranteed that li > ri - 1 for all 2 ≤ i ≤ k.

Output

Output "Hungry" if Arkady won't be able to fry the cutlet for exactly n seconds on one side and exactly n seconds on the other side.

Otherwise, output "Full" in the first line, and the minimum number of times he should flip the cutlet in the second line.

Examples

Input

10 2
3 5
11 13


Output

Full
2


Input

10 3
3 5
9 10
11 13


Output

Full
1


Input

20 1
3 19


Output

Hungry

Note

In the first example Arkady should flip the cutlet in time moment 3 seconds after he starts cooking and in time moment 13 seconds after he starts cooking.

In the second example, Arkady can flip the cutlet at 10 seconds after he starts cooking.

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

The city of IOI, where JOI lives, has a rectangular shape with H sections in the north-south direction and W sections in the east-west direction, and is divided into H x W sections. The i-th section from the north and the j-th section from the west are represented as (i, j). A large-scale festival is currently being held to commemorate the international programming contest held in IOI City. There are food stalls in some areas, each selling different types of sweets. There are no food stalls in plots (1, 1), plots (H, W) and the plots adjacent to them north, south, east and west.

JOI moves from compartment (1, 1) to compartment (H, W). To shorten the travel time, JOI travels only to the east or south. JOI likes sweets, so he takes the following actions in order each time he enters a section.

1. If there is a stall selling sweets that you have not bought yet in the current section, buy sweets at that stall.
2. If there are food stalls selling sweets that you have not bought yet in the area adjacent to the north, south, east, and west of the current area, call a salesperson from all the stalls except one of those stalls. Buy sweets.



JOI never buys the same kind of sweets more than once.

Given the size of the IOI city, the location of the stalls, and the price of the sweets at each stall, the sweets that JOI buys while moving from parcel (1, 1) to parcel (H, W). Find the minimum value of the total amount of.





Example

Input

5 5
..483
.59.9
3.866
79...
4.8..


Output

20

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Square1001 has seen an electric bulletin board displaying the integer 1.
He can perform the following operations A and B to change this value:
 - Operation A: The displayed value is doubled.
 - Operation B: The displayed value increases by K.
Square1001 needs to perform these operations N times in total.
Find the minimum possible value displayed in the board after N operations.

-----Constraints-----
 - 1 \leq N, K \leq 10
 - All input values are integers.

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

-----Output-----
Print the minimum possible value displayed in the board after N operations.

-----Sample Input-----
4
3

-----Sample Output-----
10

The value will be minimized when the operations are performed in the following order: A, A, B, B.

In this case, the value will change as follows: 1 → 2 → 4 → 7 → 10.

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