vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Little Elephant from the Zoo of Lviv hates exams. Since Little Elephant lives in Ukraine, he is going to take exams called 'ZNO'. Help him.
There will be n tickets on the table. Each ticket has a number written on it. The i-th ticket can be numbered Ai with probability Pi percent and with probability 100-Pi percent it can be numbered Bi. It can not have any other number. A numbering of tickets on the table is correct if and only if all tickets have distinct ticket numbers.
Help Little Elephant find the probability that the numbering will be correct.

Input
The first line of the input contains a single integer T - the number of test cases. T test cases follow. The first line of each test case contains a single integer n - the number of tickets on the table. n lines will follow. Each of these lines contains three integers: Pi,  Ai and Bi.

Output
Output T lines, each containing a single real number - answer for the corresponding test case. Rounding errors less than 10^-6 will be ignored.


Constraints

1 <= T <= 10

1 <= n <= 50

1 <= Ai, Bi <= 16

0 <= Pi <= 100


Example

Input:
2
2
50 1 2
50 2 1
3
100 1 3
47 2 1
74 3 2

Output:
0.500000000
0.347800000

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
One day mum asked Petya to sort his toys and get rid of some of them. Petya found a whole box of toy spiders. They were quite dear to him and the boy didn't want to throw them away. Petya conjured a cunning plan: he will glue all the spiders together and attach them to the ceiling. Besides, Petya knows that the lower the spiders will hang, the more mum is going to like it and then she won't throw his favourite toys away. Help Petya carry out the plan.

A spider consists of *k* beads tied together by *k*<=-<=1 threads. Each thread connects two different beads, at that any pair of beads that make up a spider is either directly connected by a thread, or is connected via some chain of threads and beads.

Petya may glue spiders together directly gluing their beads. The length of each thread equals 1. The sizes of the beads can be neglected. That's why we can consider that gluing spiders happens by identifying some of the beads (see the picture). Besides, the construction resulting from the gluing process should also represent a spider, that is, it should have the given features. 

After Petya glues all spiders together, he measures the length of the resulting toy. The distance between a pair of beads is identified as the total length of the threads that connect these two beads. The length of the resulting construction is the largest distance between all pairs of beads. Petya wants to make the spider whose length is as much as possible.

The picture two shows two spiders from the second sample. We can glue to the bead number 2 of the first spider the bead number 1 of the second spider. The threads in the spiders that form the sequence of threads of maximum lengths are highlighted on the picture.

Input Specification:
The first input file line contains one integer *n* (1<=≤<=*n*<=≤<=100) — the number of spiders. Next *n* lines contain the descriptions of each spider: integer *n**i* (2<=≤<=*n**i*<=≤<=100) — the number of beads, then *n**i*<=-<=1 pairs of numbers denoting the numbers of the beads connected by threads. The beads that make up each spider are numbered from 1 to *n**i*.

Output Specification:
Print a single number — the length of the required construction.

Demo Input:
['1\n3 1 2 2 3\n', '2\n3 1 2 1 3\n4 1 2 2 3 2 4\n', '2\n5 1 2 2 3 3 4 3 5\n7 3 4 1 2 2 4 4 6 2 7 6 5\n']

Demo Output:
['2\n', '4\n', '7\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Let us define two functions f and g on positive integer numbers.  $f(n) = \text{product of non-zero digits of} n$

$g(n) = \left\{\begin{array}{ll}{n} & {\text{if} n < 10} \\{g(f(n))} & {\text{otherwise}} \end{array} \right.$ 

You need to process Q queries. In each query, you will be given three integers l, r and k. You need to print the number of integers x between l and r inclusive, such that g(x) = k. 


-----Input-----

The first line of the input contains an integer Q (1 ≤ Q ≤ 2 × 10^5) representing the number of queries. 

Q lines follow, each of which contains 3 integers l, r and k (1 ≤ l ≤ r ≤ 10^6, 1 ≤ k ≤ 9).


-----Output-----

For each query, print a single line containing the answer for that query.


-----Examples-----
Input
4
22 73 9
45 64 6
47 55 7
2 62 4

Output
1
4
0
8

Input
4
82 94 6
56 67 4
28 59 9
39 74 4

Output
3
1
1
5



-----Note-----

In the first example:  g(33) = 9 as g(33) = g(3 × 3) = g(9) = 9  g(47) = g(48) = g(60) = g(61) = 6  There are no such integers between 47 and 55.  g(4) = g(14) = g(22) = g(27) = g(39) = g(40) = g(41) = g(58) = 4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are working as a private teacher. Since you are giving lessons to many pupils, you are very busy, especially during examination seasons. This season is no exception in that regard.

You know days of the week convenient for each pupil, and also know how many lessons you have to give to him or her. You can give just one lesson only to one pupil on each day. Now, there are only a limited number of weeks left until the end of the examination. Can you finish all needed lessons?



Input

The input consists of multiple data sets. Each data set is given in the following format:


N W
t1 c1
list-of-days-of-the-week
t2 c2
list-of-days-of-the-week
...
tN cN
list-of-days-of-the-week


A data set begins with a line containing two integers N (0 < N ≤ 100) and W (0 < W ≤ 1010 ). N is the number of pupils. W is the number of remaining weeks. The following 2N lines describe information about the pupils. The information for each pupil is given in two lines. The first line contains two integers ti and ci. ti (0 < ti ≤ 1010 ) is the number of lessons that the i-th pupil needs. ci (0 < ci ≤ 7) is the number of days of the week convenient for the i-th pupil. The second line is the list of ci convenient days of the week (Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, and Saturday).

The end of input is indicated by a line that contains two zeros. This line should not be processed.

Output

For each data set, print “Yes” if you can finish all lessons, or “No” otherwise.

Example

Input

2 2
6 3
Monday Tuesday Wednesday
8 4
Thursday Friday Saturday Sunday
2 2
7 3
Monday Tuesday Wednesday
9 4
Thursday Friday Saturday Sunday
0 0


Output

Yes
No

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n cities in Berland, each of them has a unique id — an integer from 1 to n, the capital is the one with id 1. Now there is a serious problem in Berland with roads — there are no roads.

That is why there was a decision to build n - 1 roads so that there will be exactly one simple path between each pair of cities.

In the construction plan t integers a1, a2, ..., at were stated, where t equals to the distance from the capital to the most distant city, concerning new roads. ai equals the number of cities which should be at the distance i from the capital. The distance between two cities is the number of roads one has to pass on the way from one city to another. 

Also, it was decided that among all the cities except the capital there should be exactly k cities with exactly one road going from each of them. Such cities are dead-ends and can't be economically attractive. In calculation of these cities the capital is not taken into consideration regardless of the number of roads from it. 

Your task is to offer a plan of road's construction which satisfies all the described conditions or to inform that it is impossible.

Input

The first line contains three positive numbers n, t and k (2 ≤ n ≤ 2·105, 1 ≤ t, k < n) — the distance to the most distant city from the capital and the number of cities which should be dead-ends (the capital in this number is not taken into consideration). 

The second line contains a sequence of t integers a1, a2, ..., at (1 ≤ ai < n), the i-th number is the number of cities which should be at the distance i from the capital. It is guaranteed that the sum of all the values ai equals n - 1.

Output

If it is impossible to built roads which satisfy all conditions, print -1.

Otherwise, in the first line print one integer n — the number of cities in Berland. In the each of the next n - 1 line print two integers — the ids of cities that are connected by a road. Each road should be printed exactly once. You can print the roads and the cities connected by a road in any order.

If there are multiple answers, print any of them. Remember that the capital has id 1.

Examples

Input

7 3 3
2 3 1


Output

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


Input

14 5 6
4 4 2 2 1


Output

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


Input

3 1 1
2


Output

-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Little Petya likes trees a lot. Recently his mother has presented him a tree with 2n nodes. Petya immediately decided to place this tree on a rectangular table consisting of 2 rows and n columns so as to fulfill the following conditions:

  1. Each cell of the table corresponds to exactly one tree node and vice versa, each tree node corresponds to exactly one table cell. 
  2. If two tree nodes are connected by an edge, then the corresponding cells have a common side. 



Now Petya wonders how many ways are there to place his tree on the table. He calls two placements distinct if there is a tree node which corresponds to distinct table cells in these two placements. Since large numbers can scare Petya, print the answer modulo 1000000007 (109 + 7).

Input

The first line contains a single integer n (1 ≤ n ≤ 105). Next (2n - 1) lines contain two integers each ai and bi (1 ≤ ai, bi ≤ 2n; ai ≠ bi) that determine the numbers of the vertices connected by the corresponding edge. 

Consider the tree vertexes numbered by integers from 1 to 2n. It is guaranteed that the graph given in the input is a tree, that is, a connected acyclic undirected graph.

Output

Print a single integer — the required number of ways to place the tree on the table modulo 1000000007 (109 + 7).

Examples

Input

3
1 3
2 3
4 3
5 1
6 2


Output

12


Input

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


Output

28


Input

2
1 2
3 2
4 2


Output

0

Note

Note to the first sample (all 12 variants to place the tree on the table are given below):
    
    
      
    1-3-2    2-3-1    5 4 6    6 4 5  
    | | |    | | |    | | |    | | |  
    5 4 6    6 4 5    1-3-2    2-3-1  
      
    4-3-2    2-3-4    5-1 6    6 1-5  
      | |    | |        | |    | |  
    5-1 6    6 1-5    4-3-2    2-3-4  
      
    1-3-4    4-3-1    5 2-6    6-2 5  
    | |        | |    | |        | |  
    5 2-6    6-2 5    1-3-4    4-3-1  
    

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
One day, the Grasshopper was jumping on the lawn and found a piece of paper with a string. Grasshopper became interested what is the minimum jump ability he should have in order to be able to reach the far end of the string, jumping only on vowels of the English alphabet. Jump ability is the maximum possible length of his jump. 

Formally, consider that at the begginning the Grasshopper is located directly in front of the leftmost character of the string. His goal is to reach the position right after the rightmost character of the string. In one jump the Grasshopper could jump to the right any distance from 1 to the value of his jump ability. [Image] The picture corresponds to the first example. 

The following letters are vowels: 'A', 'E', 'I', 'O', 'U' and 'Y'.


-----Input-----

The first line contains non-empty string consisting of capital English letters. It is guaranteed that the length of the string does not exceed 100. 


-----Output-----

Print single integer a — the minimum jump ability of the Grasshopper (in the number of symbols) that is needed to overcome the given string, jumping only on vowels.


-----Examples-----
Input
ABABBBACFEYUKOTT

Output
4
Input
AAA

Output
1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given a weighted tree consisting of n vertices. Recall that a tree is a connected graph without cycles. Vertices u_i and v_i are connected by an edge with weight w_i.

You are given m queries. The i-th query is given as an integer q_i. In this query you need to calculate the number of pairs of vertices (u, v) (u < v) such that the maximum weight of an edge on a simple path between u and v doesn't exceed q_i.

Input

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 2 ⋅ 10^5) — the number of vertices in the tree and the number of queries.

Each of the next n - 1 lines describes an edge of the tree. Edge i is denoted by three integers u_i, v_i and w_i — the labels of vertices it connects (1 ≤ u_i, v_i ≤ n, u_i ≠ v_i) and the weight of the edge (1 ≤ w_i ≤ 2 ⋅ 10^5). It is guaranteed that the given edges form a tree.

The last line of the input contains m integers q_1, q_2, ..., q_m (1 ≤ q_i ≤ 2 ⋅ 10^5), where q_i is the maximum weight of an edge in the i-th query.

Output

Print m integers — the answers to the queries. The i-th value should be equal to the number of pairs of vertices (u, v) (u < v) such that the maximum weight of an edge on a simple path between u and v doesn't exceed q_i.

Queries are numbered from 1 to m in the order of the input.

Examples

Input


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


Output


21 7 15 21 3 


Input


1 2
1 2


Output


0 0 


Input


3 3
1 2 1
2 3 2
1 3 2


Output


1 3 3 

Note

The picture shows the tree from the first example: <image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
João wants to join the robotic football team of his university. However, since he knows little about robotics and mathematics, he decided to build a $2$-dimensional robotic arm to bootstrap his knowledge.

The robotic arm is composed of $N$ segments of various lengths. The segments can form any angle between them, including configurations that make it appear to self-intersect when viewed from above. The robotic arm works great, but it is not trivial to position the arm’s tip as close as possible to given $x$, $y$ target coordinates with so many joints to control. Can you help João?

-----Task-----
Given the robotic arm description and target coordinates relative to the arm’s origin, calculate a configuration that places the arm’s tip as close as possible to the target.

-----Input-----
The first line contains $N$, the number of segments composing the robotic arm. $N$ lines follow, each with an integer $L_ i$ describing the length of the $i$th segment from the fixed point until the arm’s tip. There is one more line with $2$ integers: the $x$, $y$ coordinates of the target point to reach.

-----Constraints-----

$1$

$\leq $

$N$

$\leq $

$20$

Number of segments in the robotic arm

$1$

$\leq $

$L_ i$

$\leq $

$1000$

Length of the $i$th segment

$-20000$

$\leq $

$x, y$

$\leq $

$20000$

Target coordinates to attempt to reach

-----Output-----
The output should contain $N$ lines, each containing two real numbers $x_ i$, $y_ i$ indicating the coordinates of the tip of the $i$th segment.

The length of the $i$th segment computed from the solution and input $L_ i$ may not differ by more than $0.01$. Similarly, the absolute error between the solution’s distance to the target and the minimum possible distance to the target cannot exceed $0.01$.

Note that, in general, there are many solutions. Your program may output any of them.

-----Explanation for Sample Input 1-----
Sample output 1 corresponds to the drawing on the left:



The drawing on the right corresponds to the following, equally acceptable output for sample input 1:

3.923 3.100
1.118 2.037
5.000 3.000


-----Explanation for Sample Input 2-----

-----Examples-----
Sample Input:
3
5
3
4
5 3
Sample Output:
4.114 -2.842
6.297 -0.784
5.000 3.000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string, find the minimum number of characters to be inserted to convert it to palindrome.
For Example:
ab: Number of insertions required is 1. bab or aba
aa: Number of insertions required is 0. aa
abcd: Number of insertions required is 3. dcbabcd
Example 1:
Input: str = "abcd"
Output: 3
Explanation: Inserted character marked
with bold characters in dcbabcd
Example 2:
Input: str = "aa"
Output: 0
Explanation:"aa" is already a palindrome.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function countMin() which takes the string str as inputs and returns the answer.
Expected Time Complexity: O(N^{2}), N = |str|
Expected Auxiliary Space: O(N^{2})
Constraints:
1 ≤ |str| ≤ 10^{3}
str contains only lower case alphabets.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
loglogloglog. Brandon Greg Jr. is sometimes a drowning combinatorist.

A permutation of length $n$ can be represented as some order of the integers $\{ 1,2,\ldots ,n\} $. A run of length $k$ in a permutation is $k$ consecutive elements that appear in increasing or decreasing order. For example, $[5,2,4,3,1]$ is a permutation of length $5$, where (among other runs), $[2,4]$ is a run of length $2$ and $[4,3,1]$ is a run of length $3$.

Brandon found a way to count the number of permutations of length $n$ that have runs of length at most $k$. He wants you to do the same so he could check his answers. Since the numbers get very large, Brandon will ask for it modulo some prime $p$ of his choice.

-----Input-----
The only line of input contains three space-separated integers $n, k, p$ ($1\le n\le 2000$, $2\le k\le 7$, $10^8<p\le 10^9+9$), where $n$ is the length of the permutations, $k$ is the maximum length of a run, and $p$ is the prime of Brandon’s choice.

-----Output-----
Output one integer representing the number of permutations of length $n$ that have runs of length at most $k$, modulo $p$.

-----Examples-----
Sample Input 1:
1 7 1000000007
Sample Output 1:
1

Sample Input 2:
3 2 1000000007
Sample Output 2:
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
While playing chess, Chef noticed that it is generally advantageous for him if his knight attacks two or more of his opponent's pieces simultaneously. To practice this skill, Chef decided to perform the following exercise:

Take an empty 8 \times 8 chessboard, and any two white pieces.
Choose two distinct cells (X_{1}, Y_{1}), (X_{2}, Y_{2}) and place the pieces on those cells (the cell at the intersection of the i-th row and j-th column is denoted (i, j)).
Check if there exists an empty cell where he can place a black knight in such a way that the knight attacks both the white pieces simultaneously.

Given the position of the two white pieces (X_{1}, Y_{1}), (X_{2}, Y_{2}), print 'YES' if there exists an empty cell where he can place a black knight in such a way that the knight attacks both the white pieces simultaneously, otherwise print NO.

For reference, a knight attacks a piece placed in a cell that is:
One square horizontally and two squares vertically away from it, or
One square vertically and two squares horizontally away from it

A visual description of this may be found [here]#Movement).

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

- The first line of input will contain an integer T — the number of test cases. The description of T test cases follows.
- The first line of each test case contains two space-separated integers X_{1} and Y_{1}, the position of first white piece.
- The second line of each test case contains two space-separated integers X_{2} and Y_{2}, the position of second white piece.

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

For each test case, output the answer on a new line — YES if there exists an empty cell where Chef can place a black knight in such a way that the knight attacks both the white pieces simultaneously, and NO otherwise.

You may print each character of YES and NO in either uppercase or lowercase (for example, yes, yEs, Yes will be considered identical). 

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

$1 ≤ T ≤ 5000$
$1 ≤ X_{1}, Y_{1} ≤ 8$
$1 ≤ X_{2}, Y_{2} ≤ 8$
- Both the cells are distinct

----- Sample Input 1 ------ 
4
1 1
1 2
1 1
1 3
1 1
1 4
1 1
1 5
----- Sample Output 1 ------ 
NO
YES
NO
YES

----- explanation 1 ------ 
Test case $2$: Chef can place a knight at $(3, 2)$, forking both pieces.

Test case $4$: Chef can place a knight at $(2, 3)$, forking both pieces.

In the other two cases it can be verified that there is no way to place a knight that attacks both pieces at the same time.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an array a of n integers.

You want to make all elements of a equal to zero by doing the following operation exactly three times:

  * Select a segment, for each number in this segment we can add a multiple of len to it, where len is the length of this segment (added integers can be different). 



It can be proven that it is always possible to make all elements of a equal to zero.

Input

The first line contains one integer n (1 ≤ n ≤ 100 000): the number of elements of the array.

The second line contains n elements of an array a separated by spaces: a_1, a_2, ..., a_n (-10^9 ≤ a_i ≤ 10^9).

Output

The output should contain six lines representing three operations.

For each operation, print two lines:

  * The first line contains two integers l, r (1 ≤ l ≤ r ≤ n): the bounds of the selected segment.

  * The second line contains r-l+1 integers b_l, b_{l+1}, ..., b_r (-10^{18} ≤ b_i ≤ 10^{18}): the numbers to add to a_l, a_{l+1}, …, a_r, respectively; b_i should be divisible by r - l + 1.

Example

Input


4
1 3 2 4


Output


1 1 
-1
3 4
4 2
2 4
-3 -6 -6

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a non-empty integer array of size n, find the minimum number of moves required to make all array elements equal, where a move is incrementing n - 1 elements by 1.

Example:

Input:
[1,2,3]

Output:
3

Explanation:
Only three moves are needed (remember each move increments two elements):

[1,2,3]  =>  [2,3,3]  =>  [3,4,3]  =>  [4,4,4]

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Recently, Anton has found a set. The set consists of small English letters. Anton carefully wrote out all the letters from the set in one line, separated by a comma. He also added an opening curved bracket at the beginning of the line and a closing curved bracket at the end of the line. 

Unfortunately, from time to time Anton would forget writing some letter and write it again. He asks you to count the total number of distinct letters in his set.

Input

The first and the single line contains the set of letters. The length of the line doesn't exceed 1000. It is guaranteed that the line starts from an opening curved bracket and ends with a closing curved bracket. Between them, small English letters are listed, separated by a comma. Each comma is followed by a space.

Output

Print a single number — the number of distinct letters in Anton's set.

Examples

Input

{a, b, c}


Output

3


Input

{b, a, b, a}


Output

2


Input

{}


Output

0

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