vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Given a binary tree of size N, you have to count number of nodes in it. For example, count of nodes in below tree is 4.
        1
     /      \
   10      39
  /
5
Input:
First line of input contains the number of test cases T. For each test case, there will be only a single line of input which is a string representing the tree as described below: 
	
	The values in the string are in the order of level order traversal of the tree where, numbers denote node values, and a character “N” denotes NULL child.
	
	
	For example:
	
	For the above tree, the string will be: 1 2 3 N N 4 6 N 5 N N 7 N
	
Output:
For each testcase in new line, print the number of nodes.
User Task:
Since this is a functional problem you don't have to worry about input, you just have to complete the function getSize().
Constraints:
1 <= T <= 30
1 <= N <= 10^{4}
Example:
Input:
2
1 2 3
10 5 9 N 1 3 6 
Output:
3
6
Explanation:
Testcase 2: Given Tree is :
                                10
                             /        \
                           5          9
                             \       /     \
                              1    3       6
There are six nodes in the tree .

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
All Berland residents are waiting for an unprecedented tour of wizard in his Blue Helicopter over the cities of Berland!

It is well-known that there are n cities in Berland, some pairs of which are connected by bidirectional roads. Each pair of cities is connected by no more than one road. It is not guaranteed that the road network is connected, i.e. it is possible that you can't reach some city from some other.

The tour will contain several episodes. In each of the episodes:

  * the wizard will disembark at some city x from the Helicopter; 
  * he will give a performance and show a movie for free at the city x; 
  * he will drive to some neighboring city y using a road; 
  * he will give a performance and show a movie for free at the city y; 
  * he will drive to some neighboring to y city z; 
  * he will give a performance and show a movie for free at the city z; 
  * he will embark the Helicopter and fly away from the city z. 



It is known that the wizard doesn't like to use roads, so he agrees to use each road at most once (regardless of direction). In other words, for road between a and b he only can drive once from a to b, or drive once from b to a, or do not use this road at all.

The wizards wants to plan as many episodes as possible without violation the above rules. Help the wizard!

Please note that the wizard can visit the same city multiple times, the restriction is on roads only.

Input

The first line contains two integers n, m (1 ≤ n ≤ 2·105, 0 ≤ m ≤ 2·105) — the number of cities and the number of roads in Berland, respectively.

The roads description follow, one in each line. Each description is a pair of two integers ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi), where ai and bi are the ids of the cities connected by the i-th road. It is guaranteed that there are no two roads connecting the same pair of cities. Every road is bidirectional. The cities are numbered from 1 to n.

It is possible that the road network in Berland is not connected.

Output

In the first line print w — the maximum possible number of episodes. The next w lines should contain the episodes in format x, y, z — the three integers denoting the ids of the cities in the order of the wizard's visits.

Examples

Input

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


Output

2
1 4 2
4 3 2


Input

5 8
5 3
1 2
4 5
5 1
2 5
4 3
1 4
3 2


Output

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

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Snark and Philip are preparing the problemset for the upcoming pre-qualification round for semi-quarter-finals. They have a bank of n problems, and they want to select any non-empty subset of it as a problemset.

k experienced teams are participating in the contest. Some of these teams already know some of the problems. To make the contest interesting for them, each of the teams should know at most half of the selected problems.

Determine if Snark and Philip can make an interesting problemset!


-----Input-----

The first line contains two integers n, k (1 ≤ n ≤ 10^5, 1 ≤ k ≤ 4) — the number of problems and the number of experienced teams.

Each of the next n lines contains k integers, each equal to 0 or 1. The j-th number in the i-th line is 1 if j-th team knows i-th problem and 0 otherwise.


-----Output-----

Print "YES" (quotes for clarity), if it is possible to make an interesting problemset, and "NO" otherwise.

You can print each character either upper- or lowercase ("YeS" and "yes" are valid when the answer is "YES").


-----Examples-----
Input
5 3
1 0 1
1 1 0
1 0 0
1 0 0
1 0 0

Output
NO

Input
3 2
1 0
1 1
0 1

Output
YES



-----Note-----

In the first example you can't make any interesting problemset, because the first team knows all problems.

In the second example you can choose the first and the third problems.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Fibonacci numbers are generated by setting F0 = 0, F1 = 1, and then using the formula:

# Fn = Fn-1 + Fn-2

Your task is to efficiently calculate the **n**th element in the Fibonacci sequence and then count the occurrence of each digit in the number. Return a list of integer pairs sorted in **descending** order.

10 ≤ n ≤ 100000

## Examples
```
f(10) = 55  # returns [(2, 5)], as there are two occurances of digit 5

f(10000)    # returns:
  [(254, 3),
   (228, 2),
   (217, 6),
   (217, 0),
   (202, 5),
   (199, 1),
   (198, 7),
   (197, 8),
   (194, 4),
   (184, 9)]
```
If two integers have the same count, sort them in descending order.

Your algorithm must be efficient.

~~~if:javascript
Solving this Kata in Javascript requires the use of the bignumber.js library. I have included starter code to assist you with using the library. Thanks to `kazk` for assisting with the translation.
~~~

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Story
Jumbo Juice makes a fresh juice out of fruits of your choice.Jumbo Juice charges $5 for regular fruits and $7 for special ones. Regular fruits are Banana, Orange, Apple, Lemon and Grapes. Special ones are Avocado, Strawberry and Mango. Others fruits that are not listed are also available upon request. Those extra special fruits cost $9 per each. There is no limit on how many fruits she/he picks.The price of a cup of juice is the mean of price of chosen fruits. In case of decimal number (ex. $5.99), output should be the nearest integer (use the standard rounding function of your language of choice). 

Input
The function will receive an array of strings, each with the name of a fruit. The recognition of names should be case insensitive. There is no case of an enmpty array input.  


Example

```
['Mango', 'Banana', 'Avocado'] //the price of this juice bottle is (7+5+7)/3 = $6($6.333333...)
```

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The city park of IT City contains *n* east to west paths and *n* north to south paths. Each east to west path crosses each north to south path, so there are *n*2 intersections.

The city funded purchase of five benches. To make it seems that there are many benches it was decided to place them on as many paths as possible. Obviously this requirement is satisfied by the following scheme: each bench is placed on a cross of paths and each path contains not more than one bench.

Help the park administration count the number of ways to place the benches.

Input Specification:
The only line of the input contains one integer *n* (5<=≤<=*n*<=≤<=100) — the number of east to west paths and north to south paths.

Output Specification:
Output one integer — the number of ways to place the benches.

Demo Input:
['5\n']

Demo Output:
['120']

Note:
none

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
Alas, finding one's true love is not easy. Masha has been unsuccessful in that yet. Her friend Dasha told Masha about a way to determine the phone number of one's Prince Charming through arithmancy. 

The phone number is divined like that. First one needs to write down one's own phone numbers. For example, let's suppose that Masha's phone number is 12345. After that one should write her favorite digit from 0 to 9 under the first digit of her number. That will be the first digit of the needed number. For example, Masha's favorite digit is 9. The second digit is determined as a half sum of the second digit of Masha's number and the already written down first digit from her beloved one's number. In this case the arithmetic average equals to (2<=+<=9)<=/<=2<==<=5.5. Masha can round the number up or down, depending on her wishes. For example, she chooses the digit 5. Having written down the resulting digit under the second digit of her number, Masha moves to finding the third digit in the same way, i.e. finding the half sum the the third digit of her number and the second digit of the new number. The result is (5<=+<=3)<=/<=2<==<=4. In this case the answer is unique. Thus, every *i*-th digit is determined as an arithmetic average of the *i*-th digit of Masha's number and the *i*<=-<=1-th digit of her true love's number. If needed, the digit can be rounded up or down. For example, Masha can get:

Input Specification:
The first line contains nonempty sequence consisting of digits from 0 to 9 — Masha's phone number. The sequence length does not exceed 50.

Output Specification:
Output the single number — the number of phone numbers Masha will dial.

Demo Input:
['12345\n', '09\n']

Demo Output:
['48\n', '15\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an integer N, find the sum of GCD(i, N) where i = 1 to N. GCD denotes the greatest common divisor. Provide the answer modulus 10^{9} + 7.
Example 1:
Input: N = 2
Output: 3
Explanation:
GCD(1,2)+GCD(2,2) = 1 + 2 = 3
Ã¢â¬â¹Example 2:
Input: N = 10
Output: 27
Explanation:
GCD(1,10)+GCD(2,10)+...
+GCD(9, 10)+GCD(10, 10)=1+2+..+1+10=27
Your Task:  
You don't need to read input or print anything. Your task is to complete the function sumOfGCDofPairs() which takes N as inputs and returns the answer.
Expected Time Complexity: O(sqrt(N))
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{6}

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
An elephant decided to visit his friend. It turned out that the elephant's house is located at point 0 and his friend's house is located at point *x*(*x*<=&gt;<=0) of the coordinate line. In one step the elephant can move 1, 2, 3, 4 or 5 positions forward. Determine, what is the minimum number of steps he need to make in order to get to his friend's house.

Input Specification:
The first line of the input contains an integer *x* (1<=≤<=*x*<=≤<=1<=000<=000) — The coordinate of the friend's house.

Output Specification:
Print the minimum number of steps that elephant needs to make to get from point 0 to point *x*.

Demo Input:
['5\n', '12\n']

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

Note:
In the first sample the elephant needs to make one step of length 5 to reach the point *x*.

In the second sample the elephant can get to point *x* if he moves by 3, 5 and 4. There are other ways to get the optimal answer but the elephant cannot reach *x* in less than three moves.

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Lolek and Bolek are about to travel abroad by plane. The local airport has a special "Choose Your Plane" offer. The offer's conditions are as follows:
 -  it is up to a passenger to choose a plane to fly on; -  if the chosen plane has *x* (*x*<=&gt;<=0) empty seats at the given moment, then the ticket for such a plane costs *x* zlotys (units of Polish currency). 
The only ticket office of the airport already has a queue of *n* passengers in front of it. Lolek and Bolek have not stood in the queue yet, but they are already wondering what is the maximum and the minimum number of zlotys the airport administration can earn if all *n* passengers buy tickets according to the conditions of this offer?

The passengers buy tickets in turn, the first person in the queue goes first, then goes the second one, and so on up to *n*-th person.

Input Specification:
The first line contains two integers *n* and *m* (1<=≤<=*n*,<=*m*<=≤<=1000) — the number of passengers in the queue and the number of planes in the airport, correspondingly. The next line contains *m* integers *a*1,<=*a*2,<=...,<=*a**m* (1<=≤<=*a**i*<=≤<=1000) — *a**i* stands for the number of empty seats in the *i*-th plane before the ticket office starts selling tickets.

The numbers in the lines are separated by a space. It is guaranteed that there are at least *n* empty seats in total.

Output Specification:
Print two integers — the maximum and the minimum number of zlotys that the airport administration can earn, correspondingly.

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

Demo Output:
['5 5\n', '7 6\n']

Note:
In the first test sample the number of passengers is equal to the number of empty seats, so regardless of the way the planes are chosen, the administration will earn the same sum.

In the second sample the sum is maximized if the 1-st person in the queue buys a ticket to the 1-st plane, the 2-nd person — to the 2-nd plane, the 3-rd person — to the 3-rd plane, the 4-th person — to the 1-st plane. The sum is minimized if the 1-st person in the queue buys a ticket to the 1-st plane, the 2-nd person — to the 1-st plane, the 3-rd person — to the 2-nd plane, the 4-th person — to the 2-nd plane.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Flatland has recently introduced a new type of an eye check for the driver's licence. The check goes like that: there is a plane with mannequins standing on it. You should tell the value of the minimum angle with the vertex at the origin of coordinates and with all mannequins standing inside or on the boarder of this angle. 

As you spend lots of time "glued to the screen", your vision is impaired. So you have to write a program that will pass the check for you.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 10^5) — the number of mannequins.

Next n lines contain two space-separated integers each: x_{i}, y_{i} (|x_{i}|, |y_{i}| ≤ 1000) — the coordinates of the i-th mannequin. It is guaranteed that the origin of the coordinates has no mannequin. It is guaranteed that no two mannequins are located in the same point on the plane.


-----Output-----

Print a single real number — the value of the sought angle in degrees. The answer will be considered valid if the relative or absolute error doesn't exceed 10^{ - 6}. 


-----Examples-----
Input
2
2 0
0 2

Output
90.0000000000

Input
3
2 0
0 2
-2 2

Output
135.0000000000

Input
4
2 0
0 2
-2 0
0 -2

Output
270.0000000000

Input
2
2 1
1 2

Output
36.8698976458



-----Note-----

Solution for the first sample test is shown below:  [Image] 

Solution for the second sample test is shown below:  [Image] 

Solution for the third sample test is shown below:  [Image] 

Solution for the fourth sample test is shown below:  $\#$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is an interactive problem!

Ehab plays a game with Laggy. Ehab has 2 hidden integers (a,b). Laggy can ask a pair of integers (c,d) and Ehab will reply with:

  * 1 if a ⊕ c>b ⊕ d. 
  * 0 if a ⊕ c=b ⊕ d. 
  * -1 if a ⊕ c<b ⊕ d. 



Operation a ⊕ b is the [bitwise-xor operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) of two numbers a and b.

Laggy should guess (a,b) with at most 62 questions. You'll play this game. You're Laggy and the interactor is Ehab.

It's guaranteed that 0 ≤ a,b<2^{30}.

Input

See the interaction section.

Output

To print the answer, print "! a b" (without quotes). Don't forget to flush the output after printing the answer.

Interaction

To ask a question, print "? c d" (without quotes). Both c and d must be non-negative integers less than 2^{30}. Don't forget to flush the output after printing any question.

After each question, you should read the answer as mentioned in the legend. If the interactor replies with -2, that means you asked more than 62 queries and your program should terminate.

To flush the output, you can use:-

  * fflush(stdout) in C++. 
  * System.out.flush() in Java. 
  * stdout.flush() in Python. 
  * flush(output) in Pascal. 
  * See the documentation for other languages. 



Hacking:

To hack someone, print the 2 space-separated integers a and b (0 ≤ a,b<2^{30}).

Example

Input

1
-1
0

Output

? 2 1
? 1 2
? 2 0
! 3 1

Note

In the sample:

The hidden numbers are a=3 and b=1.

In the first query: 3 ⊕ 2 = 1 and 1 ⊕ 1 = 0, so the answer is 1.

In the second query: 3 ⊕ 1 = 2 and 1 ⊕ 2 = 3, so the answer is -1.

In the third query: 3 ⊕ 2 = 1 and 1 ⊕ 0 = 1, so the answer is 0.

Then, we printed the answer.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Rose- a car manufacturer finds herself as the mayor of TreeTop. The city of TreeTop is in the form of a tree with N nodes and N-1 roads joining them. For each pair of nodes u and v that are connected, the distance between them is 1 unit, however it takes c(u, v) litres of petrol to cross it (weird, isn't it?). Each node in TreeTop has a petrol pump in which one can fill the tank of their car to the fullest. The fact that there is a pump in every node means that the tank of the car only needs to have that c(u, v) litres of petrol to cross the edge u-v.    

Rose also has K dollars. She has to decide a certain capacity for the tank of the car. Given a certain capacity for the tank, results in certain roads not being crossed (for example. if the tank's capacity is 6 litres and c(u,v) is 10 then the car can't go from u to v or vice versa). Of Course, when some roads can't be crossed, TreeTop decomposes into a forest (number of disjoint trees). For each tree in the forest, Rose has to assign some node in that tree as a centre. The cost of assigning a particular node as a centre is the sum of the distances of all nodes in that tree from the centre. Rose has to ensure that the cost of setting up centres in all the trees in the forest is less than or equal to K dollars.

Rose wants to choose the maximum capacity of the petrol tank so that the cost of setting up centres is not more than K. Also, the maximum capacity that the car can have is 10^9 litres. You have to output this maximum capacity.

Input

The first line contains 2 integers- N the number of nodes in TreeTop and K, the amount of money in dollars that Rose has.
The next N-1 lines are of the form : u v c(u, v) - denoting there is an edge between u and v of length 1 and takes c(u, v) litres of petrol to cross.  

Output

Print a single integer - the maximum capacity of the car's tank.  

Constraints

1 ≤ N ≤ 10^5
1 ≤ u, v ≤ N
1 ≤ K ≤ 10^15
1 ≤c (u, v) ≤ 10^9 
It is guaranteed that the graph in the input is a tree, without multiple edges or self-loops.

SAMPLE INPUT
5 3
3 1 8
3 4 7
2 4 6
5 3 7

SAMPLE OUTPUT
6

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array $a$ consisting of $n$ integers $a_1, a_2, \dots , a_n$.

In one operation you can choose two elements of the array and replace them with the element equal to their sum (it does not matter where you insert the new element). For example, from the array $[2, 1, 4]$ you can obtain the following arrays: $[3, 4]$, $[1, 6]$ and $[2, 5]$.

Your task is to find the maximum possible number of elements divisible by $3$ that are in the array after performing this operation an arbitrary (possibly, zero) number of times.

You have to answer $t$ independent queries.


-----Input-----

The first line contains one integer $t$ ($1 \le t \le 1000$) — the number of queries.

The first line of each query contains one integer $n$ ($1 \le n \le 100$).

The second line of each query contains $n$ integers $a_1, a_2, \dots , a_n$ ($1 \le a_i \le 10^9$). 


-----Output-----

For each query print one integer in a single line — the maximum possible number of elements divisible by $3$ that are in the array after performing described operation an arbitrary (possibly, zero) number of times.


-----Example-----
Input
2
5
3 1 2 3 1
7
1 1 1 1 1 2 2

Output
3
3



-----Note-----

In the first query of the example you can apply the following sequence of operations to obtain $3$ elements divisible by $3$: $[3, 1, 2, 3, 1] \rightarrow [3, 3, 3, 1]$.

In the second query you can obtain $3$ elements divisible by $3$ with the following sequence of operations: $[1, 1, 1, 1, 1, 2, 2] \rightarrow [1, 1, 1, 1, 2, 3] \rightarrow [1, 1, 1, 3, 3] \rightarrow [2, 1, 3, 3] \rightarrow [3, 3, 3]$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
JJ has an array A of size N. He can perform the following operations on the array at most K times:

Set A_{i} := A_{i + 1} where 1 ≤ i ≤ N - 1
Set A_{i} := A_{i - 1} where 2 ≤ i ≤ N

He wants to maximize the value of the minimum element of the array A. Formally, he wants to maximize the value of \min\limits_{1 ≤ i ≤ N} A_{i}.

Can you help him do so?

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

- The first line contains a single integer T - the number of test cases. Then the test cases follow.
- The first line of each test case contains two integers N and K - the size of the array A and the maximum number of operations allowed respectively.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \dots, A_{N} denoting the array A.

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

For each test case, output the maximum value of the minimum element of the array A that can be obtained after applying the given operation at most K times.

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

$1 ≤ T ≤ 100$
$2 ≤ N ≤ 10^{5}$
$0 ≤K ≤10^{5}$
$1 ≤A_{i} ≤10^{9}$
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$

----- Sample Input 1 ------ 
4
5 4
5 4 3 2 1
6 1
8 2 3 9 6 10
5 2
4 3 4 3 5
5 1000
4 3 4 3 5

----- Sample Output 1 ------ 
5
3
4
5

----- explanation 1 ------ 
Test Case 1: We can perform the following operations (in the following order):
- Set $A_{2} := A_{1}$. Array $A$ becomes $[5, 5, 3, 2, 1]$ 
- Set $A_{3} := A_{2}$. Array $A$ becomes $[5, 5, 5, 2, 1]$ 
- Set $A_{4} := A_{3}$. Array $A$ becomes $[5, 5, 5, 5, 1]$
- Set $A_{5} := A_{4}$. Array $A$ becomes $[5, 5, 5, 5, 5]$

Therefore the answer is $5$.

Test Case 2: We can perform the following operations (in the following order):
- Set $A_{2} := A_{3}$. Array $A$ becomes $[8, 3, 3, 9, 6, 10]$

Therefore the answer is $3$.

Test Case 3: We can perform the following operations (in the following order):
- Set $A_{2} := A_{3}$. Array $A$ becomes $[4, 4, 4, 3, 5]$
- Set $A_{4} := A_{3}$. Array $A$ becomes $[4, 4, 4, 4, 5]$

Therefore the answer is $4$.

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