vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
#Unflatten a list (Easy)

There are several katas like "Flatten a list".
These katas are done by so many warriors, that the count of available list to flattin goes down!

So you have to build a method, that creates new arrays, that can be flattened!

#Shorter: You have to unflatten a list/an array.

You get an array of integers and have to unflatten it by these rules:
```
- You start at the first number.
- If this number x is smaller than 3, take this number x direct 
  for the new array and continue with the next number.
- If this number x is greater than 2, take the next x numbers (inclusive this number) as a 
  sub-array in the new array. Continue with the next number AFTER this taken numbers.
- If there are too few numbers to take by number, take the last available numbers.
```

The given array will always contain numbers. There will only be numbers > 0.

Example:
```
 [1,4,5,2,1,2,4,5,2,6,2,3,3] -> [1,[4,5,2,1],2,[4,5,2,6],2,[3,3]]

Steps: 
1. The 1 is added directly to the new array.
2. The next number is 4. So the next 4 numbers (4,5,2,1) are added as sub-array in the new array.
3. The 2 is added directly to the new array.
4. The next number is 4. So the next 4 numbers (4,5,2,6) are added as sub-array in the new array.
5. The 2 is added directly to the new array.
6. The next number is 3. So the next 3 numbers would be taken. There are only 2, 
   so take these (3,3) as sub-array in the new array.
```

There is a harder version of this kata!
Unflatten a list (Harder than easy)

Have fun coding it and please don't forget to vote and rank this kata! :-) 

I have created other katas. Have a look if you like coding and challenges.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Bit Vectors/Bitmaps
A bitmap is one way of efficiently representing sets of unique integers using single bits.
To see how this works, we can represent a set of unique integers between `0` and `< 20` using a vector/array of 20 bits:
```
var set = [3, 14, 2, 11, 16, 4, 6];```
```
var bitmap = [0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0];
```
As you can see, with a bitmap, the length of the vector represents the range of unique values in the set (in this case `0-20`), and the `0/1` represents whether or not the current index is equal to a value in the set.

Task:
Your task is to write a function `toBits` that will take in a set of uniqe integers and output a bit vector/bitmap (an array in javascript) using `1`s and `0`s to represent present and non-present values.
Input:
The function will be passed a set of unique integers in string form, in a random order, separated by line breaks.
Each integer can be expected to have a unique value `>= 0` and `< 5000`.
The input will look like this:
`let exampleInput = '3\n14\n5\n19\n18\n1\n8\n11\n2...'`
Output:
The function will be expected to output a 5000 bit vector (array) of bits, either `0` or `1`, for example:
`let exampleOutput = [0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0,...]`
More in-depth bitmap kata coming very soon, happy coding!
To learn more about bitmapping and to see the inspiration for making these kata, checkout the book Programming Pearls by Jon Bently.  It's a powerful resource for any programmer!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Title: Alena's Schedule

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Alena has successfully passed the entrance exams to the university and is now looking forward to start studying.

One two-hour lesson at the Russian university is traditionally called a pair, it lasts for two academic hours (an academic hour is equal to 45 minutes).

The University works in such a way that every day it holds exactly *n* lessons. Depending on the schedule of a particular group of students, on a given day, some pairs may actually contain classes, but some may be empty (such pairs are called breaks).

The official website of the university has already published the schedule for tomorrow for Alena's group. Thus, for each of the *n* pairs she knows if there will be a class at that time or not.

Alena's House is far from the university, so if there are breaks, she doesn't always go home. Alena has time to go home only if the break consists of at least two free pairs in a row, otherwise she waits for the next pair at the university.

Of course, Alena does not want to be sleepy during pairs, so she will sleep as long as possible, and will only come to the first pair that is presented in her schedule. Similarly, if there are no more pairs, then Alena immediately goes home.

Alena appreciates the time spent at home, so she always goes home when it is possible, and returns to the university only at the beginning of the next pair. Help Alena determine for how many pairs she will stay at the university. Note that during some pairs Alena may be at the university waiting for the upcoming pair.

Input Specification:
The first line of the input contains a positive integer *n* (1<=≤<=*n*<=≤<=100) — the number of lessons at the university. 

The second line contains *n* numbers *a**i* (0<=≤<=*a**i*<=≤<=1). Number *a**i* equals 0, if Alena doesn't have the *i*-th pairs, otherwise it is equal to 1. Numbers *a*1,<=*a*2,<=...,<=*a**n* are separated by spaces.

Output Specification:
Print a single number — the number of pairs during which Alena stays at the university.

Demo Input:
['5\n0 1 0 1 1\n', '7\n1 0 1 0 0 1 0\n', '1\n0\n']

Demo Output:
['4\n', '4\n', '0\n']

Note:
In the first sample Alena stays at the university from the second to the fifth pair, inclusive, during the third pair she will be it the university waiting for the next pair. 

In the last sample Alena doesn't have a single pair, so she spends all the time at home.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
J - Tree Reconstruction

Problem Statement

You have a directed graph. Some non-negative value is assigned on each edge of the graph. You know that the value of the graph satisfies the flow conservation law That is, for every node v, the sum of values on edges incoming to v equals to the sum of values of edges outgoing from v. For example, the following directed graph satisfies the flow conservation law.

<image>


Suppose that you choose a subset of edges in the graph, denoted by E', and then you erase all the values on edges other than E'. Now you want to recover the erased values by seeing only remaining information. Due to the flow conservation law, it may be possible to recover all the erased values. Your task is to calculate the smallest possible size for such E'.

For example, the smallest subset E' for the above graph will be green edges in the following figure. By the flow conservation law, we can recover values on gray edges.

<image>


Input

The input consists of multiple test cases. The format of each test case is as follows.


N M
s_1 t_1
...
s_M t_M


The first line contains two integers N (1 \leq N \leq 500) and M (0 \leq M \leq 3,000) that indicate the number of nodes and edges, respectively. Each of the following M lines consists of two integers s_i and t_i (1 \leq s_i, t_i \leq N). This means that there is an edge from s_i to t_i in the graph.

You may assume that the given graph is simple:

* There are no self-loops: s_i \neq t_i.
* There are no multi-edges: for all i < j, \\{s_i, t_i\\} \neq \\{s_j, t_j\\}.



Also, it is guaranteed that each component of the given graph is strongly connected. That is, for every pair of nodes v and u, if there exist a path from v to u, then there exists a path from u to v.

Note that you are NOT given information of values on edges because it does not effect the answer.

Output

For each test case, print an answer in one line.

Sample Input 1


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


Output for the Sample Input 1


5


Sample Input 2


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


Output for the Sample Input 2


3


Sample Input 3


4 4
1 2
2 1
3 4
4 3


Output for the Sample Input 3


2






Example

Input

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


Output

5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp has a strict daily schedule. He has n alarms set for each day, and the i-th alarm rings each day at the same time during exactly one minute.

Determine the longest time segment when Polycarp can sleep, i. e. no alarm rings in that period. It is possible that Polycarp begins to sleep in one day, and wakes up in another.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 100) — the number of alarms.

Each of the next n lines contains a description of one alarm. Each description has a format "hh:mm", where hh is the hour when the alarm rings, and mm is the minute of that hour when the alarm rings. The number of hours is between 0 and 23, and the number of minutes is between 0 and 59. All alarm times are distinct. The order of the alarms is arbitrary.

Each alarm starts ringing in the beginning of the corresponding minute and rings for exactly one minute (i. e. stops ringing in the beginning of the next minute). Polycarp can start sleeping instantly when no alarm is ringing, and he wakes up at the moment when some alarm starts ringing.


-----Output-----

Print a line in format "hh:mm", denoting the maximum time Polycarp can sleep continuously. hh denotes the number of hours, and mm denotes the number of minutes. The number of minutes should be between 0 and 59. Look through examples to understand the format better.


-----Examples-----
Input
1
05:43

Output
23:59

Input
4
22:00
03:21
16:03
09:59

Output
06:37



-----Note-----

In the first example there is only one alarm which rings during one minute of a day, and then rings again on the next day, 23 hours and 59 minutes later. Polycarp can sleep all this time.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In the mysterious country of Byteland, everything is quite different from what you'd 

normally expect. In most places, if you were approached by two mobsters in a dark alley, they would 

probably tell you to give them all the money that you have. If you refused, or didn't have any - 

they might even beat you up.

In Byteland the government decided that even the slightest chance of someone getting injured has to be ruled out. So, they introduced a strict policy. When a mobster approaches you in a dark 

alley, he asks you for a specific amount of money. You are obliged to show him all the money that 

you have, but you only need to pay up if he can find a subset of your banknotes whose total value 

matches his demand. Since banknotes in Byteland can have any positive integer value smaller than 

one thousand you are quite likely to get off without paying.

Both the citizens and the gangsters of Byteland have very positive feelings about the system. No one ever 

gets hurt, the gangsters don't lose their jobs, and there are quite a few rules that minimize that 
probability of getting mugged (the first one is: don't go into dark alleys - and this one is said to work in other places also).

------ Input ------ 

The first line contains integer t, the number of test cases (about 100). Then t test cases follow. Each test case starts with n, the 

number of banknotes in your wallet, and m, the amount of money the muggers asked of you. Then n 

numbers follow, representing values of your banknotes. Your wallet does not hold more than 20 banknotes, and the value of a single banknote is never more than 1000.

------ Output ------ 

For each test case output a single line with the word 'Yes' if there is a subset of your banknotes that sums  to m, and 'No' otherwise.

----- Sample Input 1 ------ 
5
3 3
1
1
1
5 11
1
2
4
8
16
5 23
1
2
4
8
16
5 13
1
5
5
10
10
20 132
17
6
4
998
254
137
259
153
154
3
28
19
123
542
857
23
687
35
99
999
----- Sample Output 1 ------ 
Yes
Yes
Yes
No
Yes
----- explanation 1 ------ 
For example, in the last case you have to pay up, since: 6+3+123=132.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Today Patrick waits for a visit from his friend Spongebob. To prepare for the visit, Patrick needs to buy some goodies in two stores located near his house. There is a d_1 meter long road between his house and the first shop and a d_2 meter long road between his house and the second shop. Also, there is a road of length d_3 directly connecting these two shops to each other. Help Patrick calculate the minimum distance that he needs to walk in order to go to both shops and return to his house. [Image] 

Patrick always starts at his house. He should visit both shops moving only along the three existing roads and return back to his house. He doesn't mind visiting the same shop or passing the same road multiple times. The only goal is to minimize the total distance traveled.


-----Input-----

The first line of the input contains three integers d_1, d_2, d_3 (1 ≤ d_1, d_2, d_3 ≤ 10^8) — the lengths of the paths.   d_1 is the length of the path connecting Patrick's house and the first shop;  d_2 is the length of the path connecting Patrick's house and the second shop;  d_3 is the length of the path connecting both shops. 


-----Output-----

Print the minimum distance that Patrick will have to walk in order to visit both shops and return to his house.


-----Examples-----
Input
10 20 30

Output
60

Input
1 1 5

Output
4



-----Note-----

The first sample is shown on the picture in the problem statement. One of the optimal routes is: house $\rightarrow$ first shop $\rightarrow$ second shop $\rightarrow$ house.

In the second sample one of the optimal routes is: house $\rightarrow$ first shop $\rightarrow$ house $\rightarrow$ second shop $\rightarrow$ house.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Xenia lives in a city that has n houses built along the main ringroad. The ringroad houses are numbered 1 through n in the clockwise order. The ringroad traffic is one way and also is clockwise.

Xenia has recently moved into the ringroad house number 1. As a result, she's got m things to do. In order to complete the i-th task, she needs to be in the house number a_{i} and complete all tasks with numbers less than i. Initially, Xenia is in the house number 1, find the minimum time she needs to complete all her tasks if moving from a house to a neighboring one along the ringroad takes one unit of time.


-----Input-----

The first line contains two integers n and m (2 ≤ n ≤ 10^5, 1 ≤ m ≤ 10^5). The second line contains m integers a_1, a_2, ..., a_{m} (1 ≤ a_{i} ≤ n). Note that Xenia can have multiple consecutive tasks in one house.


-----Output-----

Print a single integer — the time Xenia needs to complete all tasks.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.


-----Examples-----
Input
4 3
3 2 3

Output
6

Input
4 3
2 3 3

Output
2



-----Note-----

In the first test example the sequence of Xenia's moves along the ringroad looks as follows: 1 → 2 → 3 → 4 → 1 → 2 → 3. This is optimal sequence. So, she needs 6 time units.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A system of n vessels with water is given. Several pairs of vessels are connected by tubes with transfusion mechanisms. One may transfer an integer amount of liters of water between two vessels connected by such tube (tube works in both directions). There might be multiple tubes between two vessels. Total number of tubes equals e. Volume of each vessel equals v liters. Of course, the amount of the water in any vessel cannot exceed v liters in the process of transfusions.

Given the initial amounts ai of water in the vessels and the desired amounts bi find a sequence of transfusions that deals with the task. Total number of transfusions must not exceed 2·n2.

Input

First line of the input contains integers n, v, e (1 ≤ n ≤ 300, 1 ≤ v ≤ 109, 0 ≤ e ≤ 50000).

Next two lines contain n integers each: initial ai and the desired amounts bi of water in corresponding vessels (0 ≤ ai, bi ≤ v).

Next e lines describe one tube each in the format x y (1 ≤ x, y ≤ n, x ≠ y) for a tube between vessels number x and y. There might be multiple tubes between two vessels. You may assume that vessels are numbered from 1 to n in some way.

Output

Print "NO" (without quotes), if such sequence of transfusions does not exist.

Otherwise print any suitable sequence in the following format. On the first line print the total number of transfusions k (k should not exceed 2·n2). In the following k lines print transfusions in the format x y d (transfusion of d liters from the vessel number x to the vessel number y, x and y must be distinct). For all transfusions d must be a non-negative integer.

Examples

Input

2 10 1
1 9
5 5
1 2


Output

1
2 1 4


Input

2 10 0
5 2
4 2


Output

NO


Input

2 10 0
4 2
4 2


Output

0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We call a positive integer x a k-beautiful integer if and only if it is possible to split the multiset of its digits in the decimal representation into two subsets such that the difference between the sum of digits in one subset and the sum of digits in the other subset is less than or equal to k. Each digit should belong to exactly one subset after the split.

There are n queries for you. Each query is described with three integers l, r and k, which mean that you are asked how many integers x between l and r (inclusive) are k-beautiful.

Input

The first line contains a single integer n (1 ≤ n ≤ 5·104), indicating the number of queries.

Each of the next n lines describes a query, containing three integers l, r and k (1 ≤ l ≤ r ≤ 1018, 0 ≤ k ≤ 9).

Output

For each query print a single number — the answer to the query.

Examples

Input

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


Output

9
28
44
58
70
80
88
94
98
100


Input

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


Output

135
380
573
721
830
906
955
983
996
1000

Note

If 1 ≤ x ≤ 9, integer x is k-beautiful if and only if x ≤ k.

If 10 ≤ x ≤ 99, integer x = 10a + b is k-beautiful if and only if |a - b| ≤ k, where a and b are integers between 0 and 9, inclusive.

100 is k-beautiful if and only if k ≥ 1.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A positive integer x is called a power of two if it can be represented as x = 2^y, where y is a non-negative integer. So, the powers of two are 1, 2, 4, 8, 16, ....

You are given two positive integers n and k. Your task is to represent n as the sum of exactly k powers of two.

Input

The only line of the input contains two integers n and k (1 ≤ n ≤ 10^9, 1 ≤ k ≤ 2 ⋅ 10^5).

Output

If it is impossible to represent n as the sum of k powers of two, print NO.

Otherwise, print YES, and then print k positive integers b_1, b_2, ..., b_k such that each of b_i is a power of two, and ∑ _{i = 1}^{k} b_i = n. If there are multiple answers, you may print any of them.

Examples

Input


9 4


Output


YES
1 2 2 4 


Input


8 1


Output


YES
8 


Input


5 1


Output


NO


Input


3 7


Output


NO

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The Little Elephant has array *a*, consisting of *n* positive integers, indexed from 1 to *n*. Let's denote the number with index *i* as *a**i*.

The Little Elephant wants to count, how many pairs of integers *l* and *r* are there, such that 1<=≤<=*l*<=&lt;<=*r*<=≤<=*n* and sequence *b*<==<=*a*1*a*2... *a**l**a**r**a**r*<=+<=1... *a**n* has no more than *k* inversions. 

An inversion in sequence *b* is a pair of elements of the sequence *b*, that change their relative order after a stable sorting of the sequence. In other words, an inversion is a pair of integers *i* and *j*, such that 1<=≤<=*i*<=&lt;<=*j*<=≤<=|*b*| and *b**i*<=&gt;<=*b**j*, where |*b*| is the length of sequence *b*, and *b**j* is its *j*-th element.

Help the Little Elephant and count the number of the described pairs.

Input Specification:
The first line contains two integers *n* and *k* (2<=≤<=*n*<=≤<=105,<=0<=≤<=*k*<=≤<=1018) — the size of array *a* and the maximum allowed number of inversions respectively. The next line contains *n* positive integers, separated by single spaces, *a*1,<=*a*2,<=...,<=*a**n* (1<=≤<=*a**i*<=≤<=109) — elements of array *a*.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specifier.

Output Specification:
In a single line print a single number — the answer to the problem.

Demo Input:
['3 1\n1 3 2\n', '5 2\n1 3 2 1 7\n']

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

Note:
none

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

Given a positive integer `n`, calculate the following sum: 

```
n + n/2 + n/4 + n/8 + ...
``` 

All elements of the sum are the results of integer division.

## Example

```
25  =>  25 + 12 + 6 + 3 + 1 = 47
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Dreamoon is standing at the position 0 on a number line. Drazil is sending a list of commands through Wi-Fi to Dreamoon's smartphone and Dreamoon follows them.

Each command is one of the following two types: 

  1. Go 1 unit towards the positive direction, denoted as '+'
  2. Go 1 unit towards the negative direction, denoted as '-'



But the Wi-Fi condition is so poor that Dreamoon's smartphone reports some of the commands can't be recognized and Dreamoon knows that some of them might even be wrong though successfully recognized. Dreamoon decides to follow every recognized command and toss a fair coin to decide those unrecognized ones (that means, he moves to the 1 unit to the negative or positive direction with the same probability 0.5). 

You are given an original list of commands sent by Drazil and list received by Dreamoon. What is the probability that Dreamoon ends in the position originally supposed to be final by Drazil's commands?

Input

The first line contains a string s1 — the commands Drazil sends to Dreamoon, this string consists of only the characters in the set {'+', '-'}. 

The second line contains a string s2 — the commands Dreamoon's smartphone recognizes, this string consists of only the characters in the set {'+', '-', '?'}. '?' denotes an unrecognized command.

Lengths of two strings are equal and do not exceed 10.

Output

Output a single real number corresponding to the probability. The answer will be considered correct if its relative or absolute error doesn't exceed 10 - 9.

Examples

Input

++-+-
+-+-+


Output

1.000000000000


Input

+-+-
+-??


Output

0.500000000000


Input

+++
??-


Output

0.000000000000

Note

For the first sample, both s1 and s2 will lead Dreamoon to finish at the same position  + 1. 

For the second sample, s1 will lead Dreamoon to finish at position 0, while there are four possibilites for s2: {"+-++", "+-+-", "+--+", "+---"} with ending position {+2, 0, 0, -2} respectively. So there are 2 correct cases out of 4, so the probability of finishing at the correct position is 0.5. 

For the third sample, s2 could only lead us to finish at positions {+1, -1, -3}, so the probability to finish at the correct position  + 3 is 0.

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