vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
I need to save some money to buy a gift. I think I can do something like that:

First week (W0) I save nothing on Sunday, 1 on Monday, 2 on Tuesday... 6 on Saturday,
second week (W1) 2 on Monday... 7 on Saturday and so on according to the table below where the days are numbered from 0 to 6.

Can you tell me how much I will have for my gift on Saturday evening after I have saved 12? (Your function finance(6) should return 168 which is the sum of the savings in the table). 

Imagine now that we live on planet XY140Z-n where the days of the week are numbered from 0 to n (integer n > 0) and where
I save from week number 0 to week number n included (in the table below n = 6).

How much money would I have at the end of my financing plan on planet XY140Z-n?



  -- |Su|Mo|Tu|We|Th|Fr|Sa|
   --|--|--|--|--|--|--|--|
  W6 |  |  |  |  |  |  |12|
  W5 |  |  |  |  |  |10|11|
  W4 |  |  |  |  |8 |9 |10|
  W3 |  |  |  |6 |7 |8 |9 |
  W2 |  |  |4 |5 |6 |7 |8 |
  W1 |  |2 |3 |4 |5 |6 |7 |
  W0 |0 |1 |2 |3 |4 |5 |6 |
  
#Example:
```
finance(5) --> 105
finance(6) --> 168
finance(7) --> 252
finance(5000) --> 62537505000
```
#Hint: 
try to avoid nested loops

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The start of the new academic year brought about the problem of accommodation students into dormitories. One of such dormitories has a a × b square meter wonder room. The caretaker wants to accommodate exactly n students there. But the law says that there must be at least 6 square meters per student in a room (that is, the room for n students must have the area of at least 6n square meters). The caretaker can enlarge any (possibly both) side of the room by an arbitrary positive integer of meters. Help him change the room so as all n students could live in it and the total area of the room was as small as possible.


-----Input-----

The first line contains three space-separated integers n, a and b (1 ≤ n, a, b ≤ 10^9) — the number of students and the sizes of the room.


-----Output-----

Print three integers s, a_1 and b_1 (a ≤ a_1; b ≤ b_1) — the final area of the room and its sizes. If there are multiple optimal solutions, print any of them.


-----Examples-----
Input
3 3 5

Output
18
3 6

Input
2 4 4

Output
16
4 4

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
You've got an array, consisting of *n* integers *a*1,<=*a*2,<=...,<=*a**n*. Also, you've got *m* queries, the *i*-th query is described by two integers *l**i*,<=*r**i*. Numbers *l**i*,<=*r**i* define a subsegment of the original array, that is, the sequence of numbers *a**l**i*,<=*a**l**i*<=+<=1,<=*a**l**i*<=+<=2,<=...,<=*a**r**i*. For each query you should check whether the corresponding segment is a ladder. 

A ladder is a sequence of integers *b*1,<=*b*2,<=...,<=*b**k*, such that it first doesn't decrease, then doesn't increase. In other words, there is such integer *x* (1<=≤<=*x*<=≤<=*k*), that the following inequation fulfills: *b*1<=≤<=*b*2<=≤<=...<=≤<=*b**x*<=≥<=*b**x*<=+<=1<=≥<=*b**x*<=+<=2...<=≥<=*b**k*. Note that the non-decreasing and the non-increasing sequences are also considered ladders.

Input Specification:
The first line contains two integers *n* and *m* (1<=≤<=*n*,<=*m*<=≤<=105) — the number of array elements and the number of queries. The second line contains the sequence of integers *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=109), where number *a**i* stands for the *i*-th array element.

The following *m* lines contain the description of the queries. The *i*-th line contains the description of the *i*-th query, consisting of two integers *l**i*, *r**i* (1<=≤<=*l**i*<=≤<=*r**i*<=≤<=*n*) — the boundaries of the subsegment of the initial array.

The numbers in the lines are separated by single spaces.

Output Specification:
Print *m* lines, in the *i*-th line print word "Yes" (without the quotes), if the subsegment that corresponds to the *i*-th query is the ladder, or word "No" (without the quotes) otherwise.

Demo Input:
['8 6\n1 2 1 3 3 5 2 1\n1 3\n2 3\n2 4\n8 8\n1 4\n5 8\n']

Demo Output:
['Yes\nYes\nNo\nYes\nNo\nYes\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Note that the memory limit in this problem is less than usual.

Let's consider an array consisting of positive integers, some positions of which contain gaps.

We have a collection of numbers that can be used to fill the gaps. Each number from the given collection can be used at most once.

Your task is to determine such way of filling gaps that the longest increasing subsequence in the formed array has a maximum size.

Input

The first line contains a single integer n — the length of the array (1 ≤ n ≤ 105).

The second line contains n space-separated integers — the elements of the sequence. A gap is marked as "-1". The elements that are not gaps are positive integers not exceeding 109. It is guaranteed that the sequence contains 0 ≤ k ≤ 1000 gaps.

The third line contains a single positive integer m — the number of elements to fill the gaps (k ≤ m ≤ 105).

The fourth line contains m positive integers — the numbers to fill gaps. Each number is a positive integer not exceeding 109. Some numbers may be equal. 

Output

Print n space-separated numbers in a single line — the resulting sequence. If there are multiple possible answers, print any of them.

Examples

Input

3
1 2 3
1
10


Output

1 2 3 


Input

3
1 -1 3
3
1 2 3


Output

1 2 3 


Input

2
-1 2
2
2 4


Output

2 2 


Input

3
-1 -1 -1
5
1 1 1 1 2


Output

1 1 2 


Input

4
-1 -1 -1 2
4
1 1 2 2


Output

1 2 1 2 

Note

In the first sample there are no gaps, so the correct answer is the initial sequence.

In the second sample there is only one way to get an increasing subsequence of length 3.

In the third sample answer "4 2" would also be correct. Note that only strictly increasing subsequences are considered.

In the fifth sample the answer "1 1 1 2" is not considered correct, as number 1 can be used in replacing only two times.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string s, return the last substring of s in lexicographical order.
 
Example 1:
Input: "abab"
Output: "bab"
Explanation: The substrings are ["a", "ab", "aba", "abab", "b", "ba", "bab"]. The lexicographically maximum substring is "bab".

Example 2:
Input: "leetcode"
Output: "tcode"

 
Note:

1 <= s.length <= 4 * 10^5
s contains only lowercase English letters.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Lee just became Master in Codeforces, and so, he went out to buy some gifts for his friends. He bought $n$ integers, now it's time to distribute them between his friends rationally...

Lee has $n$ integers $a_1, a_2, \ldots, a_n$ in his backpack and he has $k$ friends. Lee would like to distribute all integers in his backpack between his friends, such that the $i$-th friend will get exactly $w_i$ integers and each integer will be handed over to exactly one friend.

Let's define the happiness of a friend as the sum of the maximum and the minimum integer he'll get.

Lee would like to make his friends as happy as possible, in other words, he'd like to maximize the sum of friends' happiness. Now he asks you to calculate the maximum sum of friends' happiness.


-----Input-----

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

Next $3t$ lines contain test cases — one per three lines.

The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$; $1 \le k \le n$) — the number of integers Lee has and the number of Lee's friends.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$) — the integers Lee has.

The third line contains $k$ integers $w_1, w_2, \ldots, w_k$ ($1 \le w_i \le n$; $w_1 + w_2 + \ldots + w_k = n$) — the number of integers Lee wants to give to each friend. 

It's guaranteed that the sum of $n$ over test cases is less than or equal to $2 \cdot 10^5$.


-----Output-----

For each test case, print a single integer — the maximum sum of happiness Lee can achieve.


-----Example-----
Input
3
4 2
1 13 7 17
1 3
6 2
10 10 10 10 11 11
3 3
4 4
1000000000 1000000000 1000000000 1000000000
1 1 1 1

Output
48
42
8000000000



-----Note-----

In the first test case, Lee should give the greatest integer to the first friend (his happiness will be $17 + 17$) and remaining integers to the second friend (his happiness will be $13 + 1$).

In the second test case, Lee should give $\{10, 10, 11\}$ to the first friend and to the second friend, so the total happiness will be equal to $(11 + 10) + (11 + 10)$

In the third test case, Lee has four friends and four integers, it doesn't matter how he distributes the integers between his friends.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Note that this is the second problem of the two similar problems. You can hack this problem if you solve it. But you can hack the previous problem only if you solve both problems.

You are given a tree with n nodes. In the beginning, 0 is written on all edges. In one operation, you can choose any 2 distinct leaves u, v and any integer number x and add x to values written on all edges on the simple path between u and v. Note that in previous subtask x was allowed to be any real, here it has to be integer.

For example, on the picture below you can see the result of applying two operations to the graph: adding 2 on the path from 7 to 6, and then adding -1 on the path from 4 to 5. 

<image>

You are given some configuration of nonnegative integer pairwise different even numbers, written on the edges. For a given configuration determine if it is possible to achieve it with these operations, and, if it is possible, output the sequence of operations that leads to the given configuration. Constraints on the operations are listed in the output format section.

Leave is a node of a tree of degree 1. Simple path is a path that doesn't contain any node twice.

Input

The first line contains a single integer n (2 ≤ n ≤ 1000) — the number of nodes in a tree.

Each of the next n-1 lines contains three integers u, v, val (1 ≤ u, v ≤ n, u ≠ v, 0 ≤ val ≤ 10 000), meaning that there is an edge between nodes u and v with val written on it. It is guaranteed that these edges form a tree. It is guaranteed that all val numbers are pairwise different and even. 

Output

If there aren't any sequences of operations which lead to the given configuration, output "NO".

If it exists, output "YES" in the first line. In the second line output m — number of operations you are going to apply (0 ≤ m ≤ 10^5). Note that you don't have to minimize the number of the operations!

In the next m lines output the operations in the following format:

u, v, x (1 ≤ u, v ≤ n, u not = v, x — integer, -10^9 ≤ x ≤ 10^9), where u, v — leaves, x — number we are adding. 

It is guaranteed that if there exists a sequence of operations producing given configuration, then there exists a sequence of operations producing given configuration, satisfying all the conditions above.

Examples

Input


5
1 2 2
2 3 4
3 4 10
3 5 18


Output


NO

Input


6
1 2 6
1 3 8
1 4 12
2 5 2
2 6 4


Output


YES
4
3 6 1
4 6 3
3 4 7
4 5 2

Note

The configuration from the first sample is drawn below, and it is impossible to achieve.

<image>

The sequence of operations from the second sample is illustrated below.

<image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Note that this is the first problem of the two similar problems. You can hack this problem only if you solve both problems.

You are given a tree with $n$ nodes. In the beginning, $0$ is written on all edges. In one operation, you can choose any $2$ distinct leaves $u$, $v$ and any real number $x$ and add $x$ to values written on all edges on the simple path between $u$ and $v$.

For example, on the picture below you can see the result of applying two operations to the graph: adding $2$ on the path from $7$ to $6$, and then adding $-0.5$ on the path from $4$ to $5$. 

 [Image] 

Is it true that for any configuration of real numbers written on edges, we can achieve it with a finite number of operations?

Leaf is a node of a tree of degree $1$. Simple path is a path that doesn't contain any node twice.


-----Input-----

The first line contains a single integer $n$ ($2 \le n \le 10^5$) — the number of nodes.

Each of the next $n-1$ lines contains two integers $u$ and $v$ ($1 \le u, v \le n$, $u \neq v$), meaning that there is an edge between nodes $u$ and $v$. It is guaranteed that these edges form a tree.


-----Output-----

If there is a configuration of real numbers written on edges of the tree that we can't achieve by performing the operations, output "NO". 

Otherwise, output "YES". 

You can print each letter in any case (upper or lower).


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

Output
YES
Input
3
1 2
2 3

Output
NO
Input
5
1 2
1 3
1 4
2 5

Output
NO
Input
6
1 2
1 3
1 4
2 5
2 6

Output
YES


-----Note-----

In the first example, we can add any real $x$ to the value written on the only edge $(1, 2)$.

 [Image] 

In the second example, one of configurations that we can't reach is $0$ written on $(1, 2)$ and $1$ written on $(2, 3)$.

 $8$ 

Below you can see graphs from examples $3$, $4$:

 [Image] 

 [Image]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Petya has k matches, placed in n matchboxes lying in a line from left to right. We know that k is divisible by n. Petya wants all boxes to have the same number of matches inside. For that, he can move a match from its box to the adjacent one in one move. How many such moves does he need to achieve the desired configuration?


-----Input-----

The first line contains integer n (1 ≤ n ≤ 50000). The second line contains n non-negative numbers that do not exceed 10^9, the i-th written number is the number of matches in the i-th matchbox. It is guaranteed that the total number of matches is divisible by n.


-----Output-----

Print the total minimum number of moves.


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

Output
12

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Having gained some experience with Prime Numbers, Robin now seeks Revenge from Bruce. So, while they are on their way from the Airport to the Summit, Robin comes up with a new Prime based Puzzle for Bruce.

He asks him to find rad(n) for t numbers which he lists before Bruce and then form a sorted table on the values of rad(n) (in ascending order) and he defines rad(n) as the product of the distinct prime factors of n. He then asks him to find E(k) which he defines as the kth element in the sorted table. Bruce has got to prepare for the Summit and so he seeks your help. Help him solve this puzzle to maintain his status as the The Dark Knight of Gotham.

Input:
First line contains t, the number of testcases, and t lines follow after it each containing a single integer k.

Output: Display E(k) for each value of n in a separate line

Constraints:

t ≤ 500

k ≤ 10000

Table is made for n values till 10000SAMPLE INPUT
5
1
3
5
6
10

SAMPLE OUTPUT
1
4
3
9
10

Explanation

Refer the table for n values till 10 in the question description and Cross-Reference it with the sample input/output.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Fibonacci numbers have the following form F1=1, F2=1, F3=2 ... 
Fn=Fn-1 +Fn-2 .

We have an array { a1,a2,...,aN} which contains N elements. We want to find gcd(F{a1},F{a2},F{a3},...,F{aN}).

InputFormat

The first line contains N, where N denotes size of the array.
Each of the next N lines contains a number: the i  line contains  ai.

Output Format

Print a single integer—the remainder of the division of the resulting number by 1000000007. 

Constraints

1 ≤ N ≤ 2*10^5

1 ≤ ai ≤ 10^12

Sample Input

3

2

3

5

Sample Output

11

Explanation

F2=1

F3=2

F5=5

gcd(1,2,5)=1

SampleInput

2

3

6

Sample Output

2

Explanation

F3=2

F6=8

gcd(2,8)=2

SAMPLE INPUT
3
2
3
5

SAMPLE OUTPUT
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Old MacDonald had a farm, and on that farm she had a square-shaped pasture, and on that pasture she had a cow that was prone to escape. So now Old MacDonald wants to set up a fence around the pasture. Given the area of the pasture, how long a fence does Old MacDonald need to buy? 

-----Input-----
The input consists of a single integer $a$ ($1 \le a \le 10^{18}$), the area in square meters of Old MacDonald’s pasture.

-----Output-----
Output the total length of fence needed for the pasture, in meters. The length should be accurate to an absolute or relative error of at most $10^{-6}$.

-----Examples-----
Sample Input:
16
Sample Output:
16

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Filya just learned new geometry object — rectangle. He is given a field consisting of *n*<=×<=*n* unit cells. Rows are numbered from bottom to top with integer from 1 to *n*. Columns are numbered from left to right with integers from 1 to *n*. Cell, located at the intersection of the row *r* and column *c* is denoted as (*r*,<=*c*). Filya has painted two rectangles, such that their sides are parallel to coordinate axes and each cell lies fully inside or fully outside each of them. Moreover, no cell lies in both rectangles.

Later, hedgehog Filya became interested in the location of his rectangles but was unable to find the sheet of paper they were painted on. They were taken by Sonya and now she wants to play a little game with Filya. He tells her a query rectangle and she replies with the number of initial rectangles that lie fully inside the given query rectangle. The query rectangle should match the same conditions as initial rectangles. Rectangle lies fully inside the query if each o its cells lies inside the query.

Filya knows Sonya really well, so is sure that if he asks more than 200 questions she will stop to reply.

Input Specification:
The first line of the input contains an integer *n* (2<=≤<=*n*<=≤<=216) — size of the field.

For each query an integer between 0 and 2 is returned — the number of initial rectangles that lie fully inside the query rectangle.

Output Specification:
To make a query you have to print "? *x*1 *y*1 *x*2 *y*2" (without quotes) (1<=≤<=*x*1<=≤<=*x*2<=≤<=*n*, 1<=≤<=*y*1<=≤<=*y*2<=≤<=*n*), where (*x*1,<=*y*1) stands for the position of the bottom left cell of the query and (*x*2,<=*y*2) stands for the up right cell of the query. You are allowed to ask no more than 200 queries. After each query you should perform "flush" operation and read the answer.

In case you suppose you've already determined the location of two rectangles (or run out of queries) you should print "! *x*11 *y*11 *x*12 *y*12 *x*21 *y*21 *x*22 *y*22" (without quotes), where first four integers describe the bottom left and up right cells of the first rectangle, and following four describe the corresponding cells of the second rectangle. You can print the rectangles in an arbitrary order. After you have printed the answer, print the end of the line and perform "flush". Your program should terminate immediately after it print the answer.

Demo Input:
['5\n2\n1\n0\n1\n1\n1\n0\n1\n']

Demo Output:
['? 1 1 5 5\n? 1 1 3 3\n? 1 1 3 1\n? 2 2 2 2\n? 3 3 5 5\n? 3 3 3 5\n? 3 3 3 4\n? 3 4 3 5\n! 2 2 2 2 3 4 3 5\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Takahashi has an ability to generate a tree using a permutation (p_1,p_2,...,p_n) of (1,2,...,n), in the following process:
First, prepare Vertex 1, Vertex 2, ..., Vertex N.
For each i=1,2,...,n, perform the following operation:
 - If p_i = 1, do nothing.
 - If p_i \neq 1, let j' be the largest j such that p_j < p_i. Span an edge between Vertex i and Vertex j'.
Takahashi is trying to make his favorite tree with this ability.
His favorite tree has n vertices from Vertex 1 through Vertex n, and its i-th edge connects Vertex v_i and w_i.
Determine if he can make a tree isomorphic to his favorite tree by using a proper permutation.
If he can do so, find the lexicographically smallest such permutation.

-----Notes-----
For the definition of isomorphism of trees, see wikipedia. Intuitively, two trees are isomorphic when they are the "same" if we disregard the indices of their vertices.

-----Constraints-----
 - 2 \leq n \leq 10^5
 - 1 \leq v_i, w_i \leq n
 - The given graph is a tree.

-----Input-----
Input is given from Standard Input in the following format:
n
v_1 w_1
v_2 w_2
:
v_{n-1} w_{n-1}

-----Output-----
If there is no permutation that can generate a tree isomorphic to Takahashi's favorite tree, print -1.
If it exists, print the lexicographically smallest such permutation, with spaces in between.

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

-----Sample Output-----
1 2 4 5 3 6

If the permutation (1, 2, 4, 5, 3, 6) is used to generate a tree, it looks as follows:

This is isomorphic to the given graph.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
It's not the rivers that you might be thinking about. The question revolves around the concept of digital rivers.
A digital river is a sequence of numbers where the number 
following n is n plus the sum of its digits.
FOR EXAMPLE

12345 is followed by 12360 since 1+2+3+4+5=15 and so
  12345 + 15 gives 12360.
similarly 145 is followed by 155.

  If the unit's digit of a digital river is 'M' we will call it river 'M' .for example 231 would be called river 1.

river 480 is the sequence beginning {480,492,507,519....} 
river 483 is the sequence beginning 
  {483,498,519,....}.

  normal streams and rivers can meet, and the same is true for digital rivers . This happens when two digital rivers share some of the same values.
FOR EXAMPLE:

river 480 meets river 483 at 519.
river 480 meets river 507 at 507 and never meets river 481.

  Every digital river will eventually meet river 1,river 3 or river 9.
  Write a program that can determine for a given integer n the value where river n first meets one of these three rivers.

Input
  
 The input may contain multiple test cases. Each test case occupies a separate line and contains an integer n (1 ≤ n ≤ 16384). A test case with value of 0 for n terminates the input and this test case must not be processed.

Output
  
For each test case in the input first output the test case number(starting from 1)as shown in the sample output. Then on a separate line output the line "first meets river x at y".Here y is the lowest value where river n first meets river x (x= 1 or 3 or 9).If river n meets river x at y for more than one value of x,output the lowest value.print a blank line between two consecutive test cases.

  Input:
  86
  12345
  0
  
  Output:
  Case #1
  first meets river 1 at 101
  
  Case #2
  first meets river 3 at 12423

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