vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
You have number a, whose decimal representation quite luckily contains digits 1, 6, 8, 9. Rearrange the digits in its decimal representation so that the resulting number will be divisible by 7.

Number a doesn't contain any leading zeroes and contains digits 1, 6, 8, 9 (it also can contain another digits). The resulting number also mustn't contain any leading zeroes.


-----Input-----

The first line contains positive integer a in the decimal record. It is guaranteed that the record of number a contains digits: 1, 6, 8, 9. Number a doesn't contain any leading zeroes. The decimal representation of number a contains at least 4 and at most 10^6 characters.


-----Output-----

Print a number in the decimal notation without leading zeroes — the result of the permutation.

If it is impossible to rearrange the digits of the number a in the required manner, print 0.


-----Examples-----
Input
1689

Output
1869

Input
18906

Output
18690

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Your task is to determine how many files of the copy queue you will be able to save into your Hard Disk Drive. The files must be saved in the order they appear in the queue. 

### Input:

* Array of file sizes `(0 <= s <= 100)`
* Capacity of the HD `(0 <= c <= 500)`

### Output:

* Number of files that can be fully saved in the HD. 

### Examples:

```
save([4,4,4,3,3], 12) -> 3
# 4+4+4 <= 12, but 4+4+4+3 > 12
```

```
save([4,4,4,3,3], 11) -> 2
# 4+4 <= 11, but 4+4+4 > 11
```

Do not expect any negative or invalid inputs.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a number in its binary form find if the given binary number is a multiple of 3. It is recommended to finish the task using one traversal of input binary number.
Example 1:
Input: S = "0011"
Output: 1
Explanation: "0011" is 3, which is divisible by 3.
Example 2:
Input: S = "100"
Output: 0
Explanation: "100"'s decimal equivalent is 4, which is not divisible by 3.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function isDivisible() which takes the string s as inputs and returns 1 if the given number is divisible by 3 otherwise 0.
Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ |S| ≤ 10^{5}

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string (`str`) containing a base-10 integer between `0` and `10000`, convert the integer to its binary representation. At that point, obtain a count of the maximum amount of consecutive 0s. From there, return the count in written form with a capital letter.

In the very first example, we have an argument of `"9"` which is being passed to the method. The binary representation of `9` is `1001` which can be read as: one, zero, zero, one. There are, at most, two consecutive 0s, resulting in the integer `2` as the value of the count. The output in the block of code above reflects the final step of taking `2` from standard form to the written form `"Two"` as prompted.

In the very last example, we have an argument of `"550"` which is being passed to the method. The binary representation of `550` is `1000100110` which can be read as: one, zero, zero, zero, one, zero, zero, one, one, zero. There are, at most, three consecutive 0s, resulting in the integer `3` as the value of the count. The output in the block of code above reflects the final step of taking `3` from standard form to the written form of `"Three"` as prompted.

One way, among many, to visualize the end of each step might look like:
```
max_consec_zeros("777")
1: "777"
2: 777
3: 1100001001
4: 4
5: "Four"
max_consec_zeros("777") => "Four"
```
Happy coding!

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Tavas is a strange creature. Usually "zzz" comes out of people's mouth while sleeping, but string s of length n comes out from Tavas' mouth instead. [Image] 

Today Tavas fell asleep in Malekas' place. While he was sleeping, Malekas did a little process on s. Malekas has a favorite string p. He determined all positions x_1 < x_2 < ... < x_{k} where p matches s. More formally, for each x_{i} (1 ≤ i ≤ k) he condition s_{x}_{i}s_{x}_{i} + 1... s_{x}_{i} + |p| - 1 = p is fullfilled.

Then Malekas wrote down one of subsequences of x_1, x_2, ... x_{k} (possibly, he didn't write anything) on a piece of paper. Here a sequence b is a subsequence of sequence a if and only if we can turn a into b by removing some of its elements (maybe no one of them or all).

After Tavas woke up, Malekas told him everything. He couldn't remember string s, but he knew that both p and s only contains lowercase English letters and also he had the subsequence he had written on that piece of paper.

Tavas wonders, what is the number of possible values of s? He asked SaDDas, but he wasn't smart enough to solve this. So, Tavas asked you to calculate this number for him.

Answer can be very large, so Tavas wants you to print the answer modulo 10^9 + 7.


-----Input-----

The first line contains two integers n and m, the length of s and the length of the subsequence Malekas wrote down (1 ≤ n ≤ 10^6 and 0 ≤ m ≤ n - |p| + 1).

The second line contains string p (1 ≤ |p| ≤ n).

The next line contains m space separated integers y_1, y_2, ..., y_{m}, Malekas' subsequence (1 ≤ y_1 < y_2 < ... < y_{m} ≤ n - |p| + 1).


-----Output-----

In a single line print the answer modulo 1000 000 007.


-----Examples-----
Input
6 2
ioi
1 3

Output
26

Input
5 2
ioi
1 2

Output
0



-----Note-----

In the first sample test all strings of form "ioioi?" where the question mark replaces arbitrary English letter satisfy.

Here |x| denotes the length of string x.

Please note that it's possible that there is no such string (answer is 0).

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The board has got a painted tree graph, consisting of n nodes. Let us remind you that a non-directed graph is called a tree if it is connected and doesn't contain any cycles.

Each node of the graph is painted black or white in such a manner that there aren't two nodes of the same color, connected by an edge. Each edge contains its value written on it as a non-negative integer.

A bad boy Vasya came up to the board and wrote number sv near each node v — the sum of values of all edges that are incident to this node. Then Vasya removed the edges and their values from the board.

Your task is to restore the original tree by the node colors and numbers sv.

Input

The first line of the input contains a single integer n (2 ≤ n ≤ 105) — the number of nodes in the tree. Next n lines contain pairs of space-separated integers ci, si (0 ≤ ci ≤ 1, 0 ≤ si ≤ 109), where ci stands for the color of the i-th vertex (0 is for white, 1 is for black), and si represents the sum of values of the edges that are incident to the i-th vertex of the tree that is painted on the board.

Output

Print the description of n - 1 edges of the tree graph. Each description is a group of three integers vi, ui, wi (1 ≤ vi, ui ≤ n, vi ≠ ui, 0 ≤ wi ≤ 109), where vi and ui — are the numbers of the nodes that are connected by the i-th edge, and wi is its value. Note that the following condition must fulfill cvi ≠ cui.

It is guaranteed that for any input data there exists at least one graph that meets these data. If there are multiple solutions, print any of them. You are allowed to print the edges in any order. As you print the numbers, separate them with spaces.

Examples

Input

3
1 3
1 2
0 5


Output

3 1 3
3 2 2


Input

6
1 0
0 3
1 8
0 2
0 3
0 0


Output

2 3 3
5 3 3
4 3 2
1 6 0
2 1 0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are N towns numbered 1 to N and M roads. The i-th road connects Town A_i and Town B_i bidirectionally and has a length of C_i.
Takahashi will travel between these towns by car, passing through these roads. The fuel tank of his car can contain at most L liters of fuel, and one liter of fuel is consumed for each unit distance traveled. When visiting a town while traveling, he can full the tank (or choose not to do so). Travel that results in the tank becoming empty halfway on the road cannot be done.
Process the following Q queries:
 - The tank is now full. Find the minimum number of times he needs to full his tank while traveling from Town s_i to Town t_i. If Town t_i is unreachable, print -1.

-----Constraints-----
 - All values in input are integers.
 - 2 \leq N \leq 300
 - 0 \leq M \leq \frac{N(N-1)}{2}
 - 1 \leq L \leq 10^9
 - 1 \leq A_i, B_i \leq N
 - A_i \neq B_i
 - \left(A_i, B_i\right) \neq \left(A_j, B_j\right) (if i \neq j)
 - \left(A_i, B_i\right) \neq \left(B_j, A_j\right) (if i \neq j)
 - 1 \leq C_i \leq 10^9
 - 1 \leq Q \leq N\left(N-1\right)
 - 1 \leq s_i, t_i \leq N
 - s_i \neq t_i
 - \left(s_i, t_i\right) \neq \left(s_j, t_j\right) (if i \neq j)

-----Input-----
Input is given from Standard Input in the following format:
N M L
A_1 B_1 C_1
:
A_M B_M C_M
Q
s_1 t_1
:
s_Q t_Q

-----Output-----
Print Q lines.
The i-th line should contain the minimum number of times the tank needs to be fulled while traveling from Town s_i to Town t_i. If Town t_i is unreachable, the line should contain -1 instead.

-----Sample Input-----
3 2 5
1 2 3
2 3 3
2
3 2
1 3

-----Sample Output-----
0
1

To travel from Town 3 to Town 2, we can use the second road to reach Town 2 without fueling the tank on the way.
To travel from Town 1 to Town 3, we can first use the first road to get to Town 2, full the tank, and use the second road to reach Town 3.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an array of integers, find the length of the longest (strictly) increasing subsequence from the given array.
Example 1:
Input:
N = 16
A[]={0,8,4,12,2,10,6,14,1,9,5
     13,3,11,7,15}
Output: 6
Explanation:Longest increasing subsequence
0 2 6 9 13 15, which has length 6
Example 2:
Input:
N = 6
A[] = {5,8,3,7,9,1}
Output: 3
Explanation:Longest increasing subsequence
5 7 9, with length 3
Your Task:
Complete the function longestSubsequence() which takes the input array and its size as input parameters and returns the length of the longest increasing subsequence.
Expected Time Complexity : O( N*log(N) )
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{4}
0 ≤ A[i] ≤ 10^{6}

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

Time Limit: 2 seconds

Memory Limit: 64 megabytes

Problem Description:
Nowadays all circuses in Berland have a round arena with diameter 13 meters, but in the past things were different.

In Ancient Berland arenas in circuses were shaped as a regular (equiangular) polygon, the size and the number of angles could vary from one circus to another. In each corner of the arena there was a special pillar, and the rope strung between the pillars marked the arena edges.

Recently the scientists from Berland have discovered the remains of the ancient circus arena. They found only three pillars, the others were destroyed by the time.

You are given the coordinates of these three pillars. Find out what is the smallest area that the arena could have.

Input Specification:
The input file consists of three lines, each of them contains a pair of numbers –– coordinates of the pillar. Any coordinate doesn't exceed 1000 by absolute value, and is given with at most six digits after decimal point.

Output Specification:
Output the smallest possible area of the ancient arena. This number should be accurate to at least 6 digits after the decimal point. It's guaranteed that the number of angles in the optimal polygon is not larger than 100.

Demo Input:
['0.000000 0.000000\n1.000000 1.000000\n0.000000 1.000000\n']

Demo Output:
['1.00000000\n']



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

Digital Cypher assigns to each letter of the alphabet unique number. For example:

```
 a  b  c  d  e  f  g  h  i  j  k  l  m
 1  2  3  4  5  6  7  8  9 10 11 12 13
 n  o  p  q  r  s  t  u  v  w  x  y  z
14 15 16 17 18 19 20 21 22 23 24 25 26
```

Instead of letters in encrypted word we write the corresponding number, eg. The word scout:

```
 s  c  o  u  t
19  3 15 21 20
```
Then we add to each obtained digit consecutive digits from the key. For example. In case of key equal to `1939` :

```
   s  c  o  u  t
  19  3 15 21 20
 + 1  9  3  9  1
 ---------------
  20 12 18 30 21
  
   m  a  s  t  e  r  p  i  e  c  e
  13  1 19 20  5 18 16  9  5  3  5
+  1  9  3  9  1  9  3  9  1  9  3
  --------------------------------
  14 10 22 29  6 27 19 18  6  12 8
```

# Task

Write a function that accepts an array of integers `code` and a `key` number. As the result, it should return string containg a decoded message from the `code`.

# Input / Output

The `code` is a array of positive integers.
The `key` input is a positive integer.

# Example

``` javascript
decode([ 20, 12, 18, 30, 21],1939);  ==> "scout"
decode([ 14, 10, 22, 29, 6, 27, 19, 18, 6, 12, 8],1939);  ==>  "masterpiece"
```

# Digital cypher series
- [Digital cypher vol 1](https://www.codewars.com/kata/592e830e043b99888600002d)
- [Digital cypher vol 2](https://www.codewars.com/kata/592edfda5be407b9640000b2)
- [Digital cypher vol 3 - missing key](https://www.codewars.com/kata/5930d8a4b8c2d9e11500002a)

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
N players will participate in a tennis tournament. We will call them Player 1, Player 2, \ldots, Player N.
The tournament is round-robin format, and there will be N(N-1)/2 matches in total.
Is it possible to schedule these matches so that all of the following conditions are satisfied? If the answer is yes, also find the minimum number of days required.
 - Each player plays at most one matches in a day.
 - Each player i (1 \leq i \leq N) plays one match against Player A_{i, 1}, A_{i, 2}, \ldots, A_{i, N-1} in this order.

-----Constraints-----
 - 3 \leq N \leq 1000
 - 1 \leq A_{i, j} \leq N
 - A_{i, j} \neq i
 - A_{i, 1}, A_{i, 2}, \ldots, A_{i, N-1} are all different.

-----Input-----
Input is given from Standard Input in the following format:
N
A_{1, 1} A_{1, 2} \ldots A_{1, N-1}
A_{2, 1} A_{2, 2} \ldots A_{2, N-1}
:
A_{N, 1} A_{N, 2} \ldots A_{N, N-1}

-----Output-----
If it is possible to schedule all the matches so that all of the conditions are satisfied, print the minimum number of days required; if it is impossible, print -1.

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

-----Sample Output-----
3

All the conditions can be satisfied if the matches are scheduled for three days as follows:
 - Day 1: Player 1 vs Player 2
 - Day 2: Player 1 vs Player 3
 - Day 3: Player 2 vs Player 3
This is the minimum number of days required.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a long decimal number $a$ consisting of $n$ digits from $1$ to $9$. You also have a function $f$ that maps every digit from $1$ to $9$ to some (possibly the same) digit from $1$ to $9$.

You can perform the following operation no more than once: choose a non-empty contiguous subsegment of digits in $a$, and replace each digit $x$ from this segment with $f(x)$. For example, if $a = 1337$, $f(1) = 1$, $f(3) = 5$, $f(7) = 3$, and you choose the segment consisting of three rightmost digits, you get $1553$ as the result.

What is the maximum possible number you can obtain applying this operation no more than once?


-----Input-----

The first line contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of digits in $a$.

The second line contains a string of $n$ characters, denoting the number $a$. Each character is a decimal digit from $1$ to $9$.

The third line contains exactly $9$ integers $f(1)$, $f(2)$, ..., $f(9)$ ($1 \le f(i) \le 9$).


-----Output-----

Print the maximum number you can get after applying the operation described in the statement no more than once.


-----Examples-----
Input
4
1337
1 2 5 4 6 6 3 1 9

Output
1557

Input
5
11111
9 8 7 6 5 4 3 2 1

Output
99999

Input
2
33
1 1 1 1 1 1 1 1 1

Output
33

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You will be given N strings. You need to add them. String contains {[a-z][A-Z][0-9]}.
Order of value of each character is 0 < 1 < 2 < ... < 9 < a < b < ... < z.
Also, a=A, b=B, c=C, ... , z=Z.

Input Format:
First line gives T, number of test cases.
Each test case has a number N in first line.
Next N lines has a string each.

Output Format:
For each test case, print a resultant sum of strings in new line. Print exact number of characters as in the value of sum. No leading zeros should be printed. Output string should only have characters from set {[a-z][0-9]}.

Constraints:
1 ≤ T ≤ 500
1 ≤ N ≤ 100
1 ≤ |S| ≤ 100
Si ∈ {[a-z][A-Z][0-9]}

SAMPLE INPUT
2
2
123
abc
2
111
Xyz

SAMPLE OUTPUT
bdf
z00

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a positive (greater than zero) integer n.

You have to represent n as the sum of integers (possibly negative) consisting only of ones (digits '1'). For example, 24 = 11 + 11 + 1 + 1 and 102 = 111 - 11 + 1 + 1. 

Among all possible representations, you have to find the one that uses the minimum number of ones in total.

Input

The single line contains one integer n (1 ≤ n < 10^{50}).

Output

Print one integer x — the minimum number of ones, such that there exist a representation of n as the sum of integers (possibly negative) that uses x ones in total.

Examples

Input


24


Output


6


Input


102


Output


7

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
> If you've finished this kata, you can try the [more difficult version](https://www.codewars.com/kata/5b256145a454c8a6990000b5).


## Taking a walk
A promenade is a way of uniquely representing a fraction by a succession of “left or right” choices. 

For example, the promenade `"LRLL"` represents the fraction `4/7`.

Each successive choice (`L` or `R`) changes the value of the promenade by combining the values of the
promenade before the most recent left choice with the value before the most recent right choice. If the value before the most recent left choice was *l/m* and the value before the most recent right choice
was r/s then the new value will be *(l+r) / (m+s)*. 

If there has never been a left choice we use *l=1* and *m=0*;  
if there has never been a right choice we use *r=0* and *s=1*.


So let's take a walk.

* `""` An empty promenade has never had a left choice nor a right choice. Therefore we use *(l=1 and m=0)* and *(r=0 and s=1)*.  
So the value of `""` is *(1+0) / (0+1) = 1/1*.
* `"L"`. Before the most recent left choice we have `""`, which equals *1/1*. There still has never been a right choice, so *(r=0 and s=1)*. So the value of `"L"` is *(1+0)/(1+1) = 1/2*
* `"LR"` = 2/3 as we use the values of `""` (before the left choice) and `"L"` (before the right choice)
* `"LRL"` = 3/5 as we use the values of `"LR"` and `"L"`
* `"LRLL"` = 4/7 as we use the values of `"LRL"` and `"L"` 


Fractions are allowed to have a larger than b.


## Your task

Implement the `promenade` function, which takes an promenade as input (represented as a string), and returns 
the corresponding fraction (represented as a tuple, containing the numerator and the denominator).

```Python
promenade("") == (1,1)
promenade("LR") == (2,3)
promenade("LRLL") == (4,7)
```
```Java
Return the Fraction as an int-Array:
promenade("") == [1,1]
promenade("LR") == [2,3]
promenade("LRLL") == [4,7]
```


*adapted from the 2016 British Informatics Olympiad*

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let N be an even number.

There is a tree with N vertices. The vertices are numbered 1, 2, ..., N. For each i (1 \leq i \leq N - 1), the i-th edge connects Vertex x_i and y_i.

Snuke would like to decorate the tree with ribbons, as follows.

First, he will divide the N vertices into N / 2 pairs. Here, each vertex must belong to exactly one pair. Then, for each pair (u, v), put a ribbon through all the edges contained in the shortest path between u and v.

Snuke is trying to divide the vertices into pairs so that the following condition is satisfied: "for every edge, there is at least one ribbon going through it." How many ways are there to divide the vertices into pairs, satisfying this condition? Find the count modulo 10^9 + 7. Here, two ways to divide the vertices into pairs are considered different when there is a pair that is contained in one of the two ways but not in the other.

Constraints

* N is an even number.
* 2 \leq N \leq 5000
* 1 \leq x_i, y_i \leq N
* The given graph is a tree.

Input

Input is given from Standard Input in the following format:


N
x_1 y_1
x_2 y_2
:
x_{N - 1} y_{N - 1}


Output

Print the number of the ways to divide the vertices into pairs, satisfying the condition, modulo 10^9 + 7.

Examples

Input

4
1 2
2 3
3 4


Output

2


Input

4
1 2
1 3
1 4


Output

3


Input

6
1 2
1 3
3 4
1 5
5 6


Output

10


Input

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


Output

672

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given $n$ integers $a_1, a_2, \ldots, a_n$. You choose any subset of the given numbers (possibly, none or all numbers) and negate these numbers (i. e. change $x \to (-x)$). What is the maximum number of different values in the array you can achieve?


-----Input-----

The first line of input contains one integer $t$ ($1 \leq t \leq 100$): the number of test cases.

The next lines contain the description of the $t$ test cases, two lines per a test case.

In the first line you are given one integer $n$ ($1 \leq n \leq 100$): the number of integers in the array.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-100 \leq a_i \leq 100$).


-----Output-----

For each test case, print one integer: the maximum number of different elements in the array that you can achieve negating numbers in the array.


-----Examples-----

Input
3
4
1 1 2 2
3
1 2 3
2
0 0
Output
4
3
1


-----Note-----

In the first example we can, for example, negate the first and the last numbers, achieving the array $[-1, 1, 2, -2]$ with four different values.

In the second example all three numbers are already different.

In the third example negation does not change anything.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given an integer, take the (mean) average of each pair of consecutive digits. Repeat this process until you have a single integer, then return that integer. e.g.

Note: if the average of two digits is not an integer, round the result **up** (e.g. the average of 8 and 9 will be 9)

## Examples

```
digitsAverage(246)  ==>  4

original: 2   4   6
           \ / \ /
1st iter:   3   5
             \ /
2nd iter:     4


digitsAverage(89)  ==>  9

original: 8   9
           \ /
1st iter:   9
```

p.s. for a bigger challenge, check out the [one line version](https://www.codewars.com/kata/one-line-task-digits-average) of this kata by myjinxin2015!

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