vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Each evening after the dinner the SIS's students gather together to play the game of Sport Mafia. 

For the tournament, Alya puts candies into the box, which will serve as a prize for a winner. To do that, she performs $n$ actions. The first action performed is to put a single candy into the box. For each of the remaining moves she can choose from two options:

  the first option, in case the box contains at least one candy, is to take exactly one candy out and eat it. This way the number of candies in the box decreased by $1$;  the second option is to put candies in the box. In this case, Alya will put $1$ more candy, than she put in the previous time. 

Thus, if the box is empty, then it can only use the second option.

For example, one possible sequence of Alya's actions look as follows:

  put one candy into the box;  put two candies into the box;  eat one candy from the box;  eat one candy from the box;  put three candies into the box;  eat one candy from the box;  put four candies into the box;  eat one candy from the box;  put five candies into the box; 

This way she will perform $9$ actions, the number of candies at the end will be $11$, while Alya will eat $4$ candies in total.

You know the total number of actions $n$ and the number of candies at the end $k$. You need to find the total number of sweets Alya ate. That is the number of moves of the first option. It's guaranteed, that for the given $n$ and $k$ the answer always exists.

Please note, that during an action of the first option, Alya takes out and eats exactly one candy.


-----Input-----

The first line contains two integers $n$ and $k$ ($1 \le n \le 10^9$; $0 \le k \le 10^9$) — the total number of moves and the number of candies in the box at the end. 

It's guaranteed, that for the given $n$ and $k$ the answer exists.


-----Output-----

Print a single integer — the number of candies, which Alya ate. Please note, that in this problem there aren't multiple possible answers — the answer is unique for any input data. 


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

Output
0
Input
9 11

Output
4
Input
5 0

Output
3
Input
3 2

Output
1


-----Note-----

In the first example, Alya has made one move only. According to the statement, the first move is always putting one candy in the box. Hence Alya ate $0$ candies.

In the second example the possible sequence of Alya's actions looks as follows:   put $1$ candy,  put $2$ candies,  eat a candy,  eat a candy,  put $3$ candies,  eat a candy,  put $4$ candies,  eat a candy,  put $5$ candies.  

This way, she will make exactly $n=9$ actions and in the end the box will contain $1+2-1-1+3-1+4-1+5=11$ candies. The answer is $4$, since she ate $4$ candies in total.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Lesha plays the recently published new version of the legendary game hacknet. In this version character skill mechanism was introduced. Now, each player character has exactly n skills. Each skill is represented by a non-negative integer a_{i} — the current skill level. All skills have the same maximum level A.

Along with the skills, global ranking of all players was added. Players are ranked according to the so-called Force. The Force of a player is the sum of the following values:  The number of skills that a character has perfected (i.e., such that a_{i} = A), multiplied by coefficient c_{f}. The minimum skill level among all skills (min a_{i}), multiplied by coefficient c_{m}. 

Now Lesha has m hacknetian currency units, which he is willing to spend. Each currency unit can increase the current level of any skill by 1 (if it's not equal to A yet). Help him spend his money in order to achieve the maximum possible value of the Force.


-----Input-----

The first line of the input contains five space-separated integers n, A, c_{f}, c_{m} and m (1 ≤ n ≤ 100 000, 1 ≤ A ≤ 10^9, 0 ≤ c_{f}, c_{m} ≤ 1000, 0 ≤ m ≤ 10^15).

The second line contains exactly n integers a_{i} (0 ≤ a_{i} ≤ A), separated by spaces, — the current levels of skills.


-----Output-----

On the first line print the maximum value of the Force that the character can achieve using no more than m currency units.

On the second line print n integers a'_{i} (a_{i} ≤ a'_{i} ≤ A), skill levels which one must achieve in order to reach the specified value of the Force, while using no more than m currency units. Numbers should be separated by spaces.


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

Output
12
2 5 2 

Input
3 5 10 1 339
1 3 1

Output
35
5 5 5 



-----Note-----

In the first test the optimal strategy is to increase the second skill to its maximum, and increase the two others by 1.

In the second test one should increase all skills to maximum.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mr. Vincent works in a door mat manufacturing company. One day, he designed a new door mat with the following specifications: 

Mat size must be $N$X$\mbox{M}$. ($N$ is an odd natural number, and $\mbox{M}$ is $3$ times $N$.)
The design should have 'WELCOME' written in the center.
The design pattern should only use |, . and - characters.

Sample Designs

    Size: 7 x 21 
    ---------.|.---------
    ------.|..|..|.------
    ---.|..|..|..|..|.---
    -------WELCOME-------
    ---.|..|..|..|..|.---
    ------.|..|..|.------
    ---------.|.---------
    
    Size: 11 x 33
    ---------------.|.---------------
    ------------.|..|..|.------------
    ---------.|..|..|..|..|.---------
    ------.|..|..|..|..|..|..|.------
    ---.|..|..|..|..|..|..|..|..|.---
    -------------WELCOME-------------
    ---.|..|..|..|..|..|..|..|..|.---
    ------.|..|..|..|..|..|..|.------
    ---------.|..|..|..|..|.---------
    ------------.|..|..|.------------
    ---------------.|.---------------

Input Format

A single line containing the space separated values of $N$ and $\mbox{M}$.  

Constraints

$5<N<101$
$15<M<303$

Output Format

Output the design pattern.

Sample Input
9 27

Sample Output
------------.|.------------
---------.|..|..|.---------
------.|..|..|..|..|.------
---.|..|..|..|..|..|..|.---
----------WELCOME----------
---.|..|..|..|..|..|..|.---
------.|..|..|..|..|.------
---------.|..|..|.---------
------------.|.------------

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Mad scientist Mike entertains himself by arranging rows of dominoes. He doesn't need dominoes, though: he uses rectangular magnets instead. Each magnet has two poles, positive (a "plus") and negative (a "minus"). If two magnets are put together at a close distance, then the like poles will repel each other and the opposite poles will attract each other.

Mike starts by laying one magnet horizontally on the table. During each following step Mike adds one more magnet horizontally to the right end of the row. Depending on how Mike puts the magnet on the table, it is either attracted to the previous one (forming a group of multiple magnets linked together) or repelled by it (then Mike lays this magnet at some distance to the right from the previous one). We assume that a sole magnet not linked to others forms a group of its own. [Image] 

Mike arranged multiple magnets in a row. Determine the number of groups that the magnets formed.


-----Input-----

The first line of the input contains an integer n (1 ≤ n ≤ 100000) — the number of magnets. Then n lines follow. The i-th line (1 ≤ i ≤ n) contains either characters "01", if Mike put the i-th magnet in the "plus-minus" position, or characters "10", if Mike put the magnet in the "minus-plus" position.


-----Output-----

On the single line of the output print the number of groups of magnets.


-----Examples-----
Input
6
10
10
10
01
10
10

Output
3

Input
4
01
01
10
10

Output
2



-----Note-----

The first testcase corresponds to the figure. The testcase has three groups consisting of three, one and two magnets.

The second testcase has two groups, each consisting of two magnets.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Peter can see a clock in the mirror from the place he sits in the office.
When he saw the clock shows 12:22



1
2
3
4
5
6
7
8
9
10
11
12




He knows that the time is 11:38



1
2
3
4
5
6
7
8
9
10
11
12




in the same manner:

05:25 --> 06:35

01:50 --> 10:10

11:58 --> 12:02

12:01 --> 11:59

Please complete the function `WhatIsTheTime(timeInMirror)`, where `timeInMirror` is the mirrored time (what Peter sees) as string.

Return the _real_ time as a string.

Consider hours to be between 1 <= hour < 13.

So there is no 00:20, instead it is 12:20.

There is no 13:20, instead it is 01:20.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In this Kata, we will calculate the **minumum positive number that is not a possible sum** from a list of positive integers. 

```
solve([1,2,8,7]) = 4 => we can get 1, 2, 3 (from 1+2), but we cannot get 4. 4 is the minimum number not possible from the list. 
solve([4,1,2,3,12]) = 11. We can get 1, 2, 3, 4, 4+1=5, 4+2=6,4+3=7,4+3+1=8,4+3+2=9,4+3+2+1=10. But not 11. 
solve([2,3,2,3,4,2,12,3]) = 1. We cannot get 1.
```
More examples in test cases. 

Good luck!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
As the guys fried the radio station facilities, the school principal gave them tasks as a punishment. Dustin's task was to add comments to nginx configuration for school's website. The school has n servers. Each server has a name and an ip (names aren't necessarily unique, but ips are). Dustin knows the ip and name of each server. For simplicity, we'll assume that an nginx command is of form "command ip;" where command is a string consisting of English lowercase letter only, and ip is the ip of one of school servers.

 [Image] 

Each ip is of form "a.b.c.d" where a, b, c and d are non-negative integers less than or equal to 255 (with no leading zeros). The nginx configuration file Dustin has to add comments to has m commands. Nobody ever memorizes the ips of servers, so to understand the configuration better, Dustin has to comment the name of server that the ip belongs to at the end of each line (after each command). More formally, if a line is "command ip;" Dustin has to replace it with "command ip; #name" where name is the name of the server with ip equal to ip.

Dustin doesn't know anything about nginx, so he panicked again and his friends asked you to do his task for him.


-----Input-----

The first line of input contains two integers n and m (1 ≤ n, m ≤ 1000).

The next n lines contain the names and ips of the servers. Each line contains a string name, name of the server and a string ip, ip of the server, separated by space (1 ≤ |name| ≤ 10, name only consists of English lowercase letters). It is guaranteed that all ip are distinct.

The next m lines contain the commands in the configuration file. Each line is of form "command ip;" (1 ≤ |command| ≤ 10, command only consists of English lowercase letters). It is guaranteed that ip belongs to one of the n school servers.


-----Output-----

Print m lines, the commands in the configuration file after Dustin did his task.


-----Examples-----
Input
2 2
main 192.168.0.2
replica 192.168.0.1
block 192.168.0.1;
proxy 192.168.0.2;

Output
block 192.168.0.1; #replica
proxy 192.168.0.2; #main

Input
3 5
google 8.8.8.8
codeforces 212.193.33.27
server 138.197.64.57
redirect 138.197.64.57;
block 8.8.8.8;
cf 212.193.33.27;
unblock 8.8.8.8;
check 138.197.64.57;

Output
redirect 138.197.64.57; #server
block 8.8.8.8; #google
cf 212.193.33.27; #codeforces
unblock 8.8.8.8; #google
check 138.197.64.57; #server

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a sequence $A_1, A_2, \ldots, A_N$. You should select a (not necessarily contiguous) subsequence of $A$ and reverse it. In other words, if you select a subsequence $A_{i_1}, A_{i_2}, \ldots, A_{i_K}$ ($1 \le i_1 < \ldots < i_K \le N$), then for each valid $j$, the $i_j$-th element of the resulting sequence is equal to the $i_{K+1-j}$-th element of the original sequence; all other elements are the same as in the original sequence.
In the resulting sequence, you want to calculate the maximum sum of a contiguous subsequence (possibly an empty sequence, with sum $0$). Find its maximum possible value and a subsequence which you should select in order to obtain this maximum value. If there are multiple solutions, you may find any one of them.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains a single integer $N$.
- The second line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.

-----Output-----
For each test case, print two lines.
- The first of these lines should contain a single integer ― the maximum possible sum of a contiguous subsequence.
- The second line should contain an integer $K$ followed by a space and $K$ space-separated integers $i_1, i_2, \ldots, i_K$.

-----Constraints-----
- $1 \le T \le 2,000$
- $2 \le N \le 10^5$
- $|A_i| \le 10^9$ for each valid $i$
- the sum of $N$ over all test cases does not exceed $2 \cdot 10^6$

-----Example Input-----
2
5
-4 2 -4 3 -5
3
-3 -2 -1

-----Example Output-----
5
2 2 3
0
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Today is Vasya's birthday. On this special occasion, he has organized a party for all of his friends. These friends are enumerated by integers from 1 to N. Each of Vasya's friends has a Knowledge Level. In addition, each of them knows an arbitrary number of other people at the party. This friendship is bidirectional and transitive in nature, i.e if person A knows person B and person B knows person C, then we consider that person A knows person C. All these people who know each other come together and form a single group of friends.  

Now, they decide to play a game. In this game, among all groups of friends, the one with the highest knowledge level within each group is elected to represent the group during the game. Let's call this person the leader of the group.  If there are multiple candidates to be the leader of a group, you can select any of them arbitrarily. The game is then played after selecting these leaders.

Now, Vasya wants to find the number of distinct ways the game can be played. He finds this task too hard and wants you to help him. As this number can be large, print it Modulo 10^9+7.   

Input Format:

The first line contains two integers N and M denoting the number of people Vasya has invited to the party and the number of relations between these people. The next line contains N space separated integers denoting the where the i^{th} integer denotes the knowledge level of person i. Each of the next M lines contains 2 space separated integers u and v denoting that person u knows person v and vice-versa.  

Output Format

Print the required answer on a single line. As the answer may be large, print it Modulo 10^9+7 

Constraints

 1 ≤ N ≤ 10^5 

 0 ≤ M ≤ 10^5 

 0 ≤ A[i] ≤ 10^9  

 1 ≤ u,v ≤ N   

 M ≤ (N*(N-1))/2     

Note:

There can be self loops, i.e edges from and to the same person and multple edges from one person to another. 

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

SAMPLE OUTPUT
1

Explanation

Here, all the people at the party know each other. Among this group the person with the highest knowledge is person 5. Hence, there is only one way.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Queries on a String

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You are given a string *s* and should process *m* queries. Each query is described by two 1-based indices *l**i*, *r**i* and integer *k**i*. It means that you should cyclically shift the substring *s*[*l**i*... *r**i*] *k**i* times. The queries should be processed one after another in the order they are given.

One operation of a cyclic shift (rotation) is equivalent to moving the last character to the position of the first character and shifting all other characters one position to the right.

For example, if the string *s* is abacaba and the query is *l*1<==<=3,<=*r*1<==<=6,<=*k*1<==<=1 then the answer is abbacaa. If after that we would process the query *l*2<==<=1,<=*r*2<==<=4,<=*k*2<==<=2 then we would get the string baabcaa.

Input Specification:
The first line of the input contains the string *s* (1<=≤<=|*s*|<=≤<=10<=000) in its initial state, where |*s*| stands for the length of *s*. It contains only lowercase English letters.

Second line contains a single integer *m* (1<=≤<=*m*<=≤<=300) — the number of queries.

The *i*-th of the next *m* lines contains three integers *l**i*, *r**i* and *k**i* (1<=≤<=*l**i*<=≤<=*r**i*<=≤<=|*s*|,<=1<=≤<=*k**i*<=≤<=1<=000<=000) — the description of the *i*-th query.

Output Specification:
Print the resulting string *s* after processing all *m* queries.

Demo Input:
['abacaba\n2\n3 6 1\n1 4 2\n']

Demo Output:
['baabcaa\n']

Note:
The sample is described in problem statement.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given <var>Q</var> tuples of integers <var>(L_i, A_i, B_i, M_i)</var>. For each tuple, answer the following question. 
There is an arithmetic progression with L terms: s_0, s_1, s_2, ... , s_{L-1}.
The initial term is A, and the common difference is B. That is, s_i = A + B \times i holds.
Consider the integer obtained by concatenating the terms written in base ten without leading zeros. For example, the sequence 3, 7, 11, 15, 19 would be concatenated into 37111519. What is the remainder when that integer is divided by M?

-----Constraints-----
 - All values in input are integers.
 - 1 \leq L, A, B < 10^{18}
 - 2 \leq M \leq 10^9
 - All terms in the arithmetic progression are less than 10^{18}.

-----Input-----
Input is given from Standard Input in the following format:
L A B M

-----Output-----
Print the remainder when the integer obtained by concatenating the terms is divided by M.

-----Sample Input-----
5 3 4 10007

-----Sample Output-----
5563

Our arithmetic progression is 3, 7, 11, 15, 19, so the answer is 37111519 mod 10007, that is, 5563.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
This is a harder version of the problem. The difference is only in constraints.

You are given a rectangular n × m matrix a. In one move you can choose any column and cyclically shift elements in this column. You can perform this operation as many times as you want (possibly zero). You can perform this operation to a column multiple times.

After you are done with cyclical shifts, you compute for every row the maximal value in it. Suppose that for i-th row it is equal r_i. What is the maximal possible value of r_1+r_2+…+r_n?

Input

The first line contains an integer t (1 ≤ t ≤ 40), the number of test cases in the input.

The first line of each test case contains integers n and m (1 ≤ n ≤ 12, 1 ≤ m ≤ 2000) — the number of rows and the number of columns in the given matrix a. 

Each of the following n lines contains m integers, the elements of a (1 ≤ a_{i, j} ≤ 10^5).

Output

Print t integers: answers for all test cases in the order they are given in the input.

Example

Input


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


Output


12
29
27

Note

In the first test case you can shift the third column down by one, this way there will be r_1 = 5 and r_2 = 7.

In the second case you can don't rotate anything at all, this way there will be r_1 = r_2 = 10 and r_3 = 9.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Misha and Vasya participated in a Codeforces contest. Unfortunately, each of them solved only one problem, though successfully submitted it at the first attempt. Misha solved the problem that costs a points and Vasya solved the problem that costs b points. Besides, Misha submitted the problem c minutes after the contest started and Vasya submitted the problem d minutes after the contest started. As you know, on Codeforces the cost of a problem reduces as a round continues. That is, if you submit a problem that costs p points t minutes after the contest started, you get $\operatorname{max}(\frac{3p}{10}, p - \frac{p}{250} \times t)$ points. 

Misha and Vasya are having an argument trying to find out who got more points. Help them to find out the truth.


-----Input-----

The first line contains four integers a, b, c, d (250 ≤ a, b ≤ 3500, 0 ≤ c, d ≤ 180). 

It is guaranteed that numbers a and b are divisible by 250 (just like on any real Codeforces round).


-----Output-----

Output on a single line: 

"Misha" (without the quotes), if Misha got more points than Vasya.

"Vasya" (without the quotes), if Vasya got more points than Misha.

"Tie" (without the quotes), if both of them got the same number of points.


-----Examples-----
Input
500 1000 20 30

Output
Vasya

Input
1000 1000 1 1

Output
Tie

Input
1500 1000 176 177

Output
Misha

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let F_k denote the k-th term of Fibonacci sequence, defined as below:

  * F_0 = F_1 = 1
  * for any integer n ≥ 0, F_{n+2} = F_{n+1} + F_n



You are given a tree with n vertices. Recall that a tree is a connected undirected graph without cycles.

We call a tree a Fib-tree, if its number of vertices equals F_k for some k, and at least one of the following conditions holds:

  * The tree consists of only 1 vertex;
  * You can divide it into two Fib-trees by removing some edge of the tree. 



Determine whether the given tree is a Fib-tree or not.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the number of vertices in the tree.

Then n-1 lines follow, each of which contains two integers u and v (1≤ u,v ≤ n, u ≠ v), representing an edge between vertices u and v. It's guaranteed that given edges form a tree.

Output

Print "YES" if the given tree is a Fib-tree, or "NO" otherwise.

You can print your answer in any case. For example, if the answer is "YES", then the output "Yes" or "yeS" will also be considered as correct answer.

Examples

Input


3
1 2
2 3


Output


YES


Input


5
1 2
1 3
1 4
1 5


Output


NO


Input


5
1 3
1 2
4 5
3 4


Output


YES

Note

In the first sample, we can cut the edge (1, 2), and the tree will be split into 2 trees of sizes 1 and 2 correspondently. Any tree of size 2 is a Fib-tree, as it can be split into 2 trees of size 1.

In the second sample, no matter what edge we cut, the tree will be split into 2 trees of sizes 1 and 4. As 4 isn't F_k for any k, it's not Fib-tree.

In the third sample, here is one possible order of cutting the edges so that all the trees in the process are Fib-trees: (1, 3), (1, 2), (4, 5), (3, 4). 

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