vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Given an integer number n, return the difference between the product of its digits and the sum of its digits.
 
Example 1:
Input: n = 234
Output: 15 
Explanation: 
Product of digits = 2 * 3 * 4 = 24 
Sum of digits = 2 + 3 + 4 = 9 
Result = 24 - 9 = 15

Example 2:
Input: n = 4421
Output: 21
Explanation: 
Product of digits = 4 * 4 * 2 * 1 = 32 
Sum of digits = 4 + 4 + 2 + 1 = 11 
Result = 32 - 11 = 21

 
Constraints:

1 <= n <= 10^5

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Nothing is eternal in the world, Kostya understood it on the 7-th of January when he saw partially dead four-color garland.

Now he has a goal to replace dead light bulbs, however he doesn't know how many light bulbs for each color are required. It is guaranteed that for each of four colors at least one light is working.

It is known that the garland contains light bulbs of four colors: red, blue, yellow and green. The garland is made as follows: if you take any four consecutive light bulbs then there will not be light bulbs with the same color among them. For example, the garland can look like "RYBGRYBGRY", "YBGRYBGRYBG", "BGRYB", but can not look like "BGRYG", "YBGRYBYGR" or "BGYBGY". Letters denote colors: 'R' — red, 'B' — blue, 'Y' — yellow, 'G' — green.

Using the information that for each color at least one light bulb still works count the number of dead light bulbs of each four colors.


-----Input-----

The first and the only line contains the string s (4 ≤ |s| ≤ 100), which describes the garland, the i-th symbol of which describes the color of the i-th light bulb in the order from the beginning of garland:   'R' — the light bulb is red,  'B' — the light bulb is blue,  'Y' — the light bulb is yellow,  'G' — the light bulb is green,  '!' — the light bulb is dead. 

The string s can not contain other symbols except those five which were described. 

It is guaranteed that in the given string at least once there is each of four letters 'R', 'B', 'Y' and 'G'. 

It is guaranteed that the string s is correct garland with some blown light bulbs, it means that for example the line "GRBY!!!B" can not be in the input data. 


-----Output-----

In the only line print four integers k_{r}, k_{b}, k_{y}, k_{g} — the number of dead light bulbs of red, blue, yellow and green colors accordingly.


-----Examples-----
Input
RYBGRYBGR

Output
0 0 0 0
Input
!RGYB

Output
0 1 0 0
Input
!!!!YGRB

Output
1 1 1 1
Input
!GB!RG!Y!

Output
2 1 1 0


-----Note-----

In the first example there are no dead light bulbs.

In the second example it is obvious that one blue bulb is blown, because it could not be light bulbs of other colors on its place according to the statements.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef's new friend hErd gave him two functions f and g.

The function f is defined over x (x≥ 1) as:  

f(x) = \begin{cases}
0, & \text{if } x = 1 \\
f( \frac{x}{2} ) + 1, & \text{if } x \text{ is even} \\
f( \lfloor \frac{x}{2} \rfloor ), & \text{if } x \text{ is odd} \\
\end{cases}

The function g is defined over x (x≥ 1) as:  

g(x) = \begin{cases}
1, & \text{if } x = 1 \\
2\cdot g( \frac{x}{2} ) + 1, & \text{if } x \text{ is even} \\
2\cdot g( \lfloor \frac{x}{2} \rfloor ), & \text{if } x \text{ is odd} \\
\end{cases}

where \lfloor z \rfloor, denotes the greatest integer less than or equal to z.

He also gave Chef two integers L and R. Chef has to find the maximum value of f(x)+g(x) for L ≤ x ≤ R.

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

- The first line of input will contain a single integer T, denoting the number of test cases.
- The only line of each test case contains two space-separated integers L and R, as mentioned in the statement.

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

For each test case, output on a new line the maximum value of f(x)+g(x) for L ≤ x ≤ R.

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

$1 ≤ T ≤ 10^{5}$
$1 ≤ L ≤ R ≤ 10^{9}$

----- Sample Input 1 ------ 
3
1 1
1 2
1 20
----- Sample Output 1 ------ 
1
4
35
----- explanation 1 ------ 
Test case $1$: $f(1)=0$ and $g(1)=1$. Hence, $f(x) + g(x) = 1$.

Test case $2$: There are $2$ possible values of $x$.
- $x = 1$: $f(1)+g(1)=1$ 
- $x = 2$: $f(2)+g(2)=(f(1) + 1) + (2\cdot g(1) + 1) = 1 + 3 = 4$.

Hence the maximum value of $f(x) + g(x) = 4$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The chef is trying to solve some pattern problems, Chef wants your help to code it. Chef has one number K to form a new pattern. Help the chef to code this pattern problem.

-----Input:-----
- First-line will contain $T$, the number of test cases. Then the test cases follow. 
- Each test case contains a single line of input, one integer $K$. 

-----Output:-----
For each test case, output as the pattern.

-----Constraints-----
- $1 \leq T \leq 100$
- $1 \leq K \leq 100$

-----Sample Input:-----
3
2
3
4

-----Sample Output:-----
21
1
123
21
1
4321
123
21
1

-----EXPLANATION:-----
No need, else pattern can be decode easily.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Implement the recursive function given by the following rules and print the last 3 digits:

F(x, y) = {
  y + 1 when x = 0,
  F(x - 1, 1) when x > 0 and y = 0,
  F(x - 1, F(x, y - 1)) when x > 0 and y > 0
}  

Input Format
A single line containing two integers X,Y
1 ≤ X,Y ≤ 100000  

Output Format
The last three digits  

Input Constraints
X and Y are non-negative integers.
Problem Setter: Practo Tech Team

SAMPLE INPUT
1 100

SAMPLE OUTPUT
102

Explanation

Note: x and y are non-negative integers

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Tracy loves Donuts. She purchased a lots of Donuts for her birthday party. She learnt to calculate the area of the circle a few days back and she is fascinated to know the area of the donuts as well !! Help her finding the area of the Donuts…..

-----Input:-----
- First line will contain, number of testcases. Then the testcases follow. 
- Each testcase contains of a single line of input, where in you have to provide the RADIUS of the Donuts. 

-----Output:-----
For each testcase, output in a single line answer is the AREA of the Donut.

-----Constraints-----
1 <= Radius <= 20.

-----Sample Input:-----
2
5 
12

-----Sample Output:-----
78.5

452.16

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Dave recently mastered the problem of placing N queens on a chessboard so
that no two queens attack eachother.
Now he wants to see how many knights he can place on a chessboard so
that no two knights attack eachother.
Normally this would be a simple task, but some of the squares of the
chessboard have been marked as unusable and hence cannot have a knight placed
on them.
Recall that a knight can attack another knight if their vertical distance
is 2 and their horizontal distance is 1, or if their vertical distance is 1 and
their horizontal distance is 2.  Only one knight may be placed on each square
of the chessboard

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

The first line of input contains an integer T (0
Each test case will begin with a line containing 2 integers M and N (0

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

For each test case, output on a single line the maximum number of knights that may be placed
on the chessboard such that no two attack each other.

----- Sample Input 1 ------ 
2
2 4
....
....
5 5
..#..
#..#.
##...
...##
.....
----- Sample Output 1 ------ 
4
11
----- explanation 1 ------ 
The following image represents the chessboard and a possible solution to the second test case:

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
The All-Berland National Olympiad in Informatics has just ended! Now Vladimir wants to upload the contest from the Olympiad as a gym to a popular Codehorses website.

Unfortunately, the archive with Olympiad's data is a mess. For example, the files with tests are named arbitrary without any logic.

Vladimir wants to rename the files with tests so that their names are distinct integers starting from 1 without any gaps, namely, "1", "2", ..., "*n*', where *n* is the total number of tests.

Some of the files contain tests from statements (examples), while others contain regular tests. It is possible that there are no examples, and it is possible that all tests are examples. Vladimir wants to rename the files so that the examples are the first several tests, all all the next files contain regular tests only.

The only operation Vladimir can perform is the "move" command. Vladimir wants to write a script file, each of the lines in which is "move file_1 file_2", that means that the file "file_1" is to be renamed to "file_2". If there is a file "file_2" at the moment of this line being run, then this file is to be rewritten. After the line "move file_1 file_2" the file "file_1" doesn't exist, but there is a file "file_2" with content equal to the content of "file_1" before the "move" command.

Help Vladimir to write the script file with the minimum possible number of lines so that after this script is run:
 -  all examples are the first several tests having filenames "1", "2", ..., "*e*", where *e* is the total number of examples; -  all other files contain regular tests with filenames "*e*<=+<=1", "*e*<=+<=2", ..., "*n*", where *n* is the total number of all tests.

Input Specification:
The first line contains single integer *n* (1<=≤<=*n*<=≤<=105) — the number of files with tests.

*n* lines follow, each describing a file with test. Each line has a form of "name_i type_i", where "name_i" is the filename, and "type_i" equals "1", if the *i*-th file contains an example test, and "0" if it contains a regular test. Filenames of each file are strings of digits and small English letters with length from 1 to 6 characters. The filenames are guaranteed to be distinct.

Output Specification:
In the first line print the minimum number of lines in Vladimir's script file.

After that print the script file, each line should be "move file_1 file_2", where "file_1" is an existing at the moment of this line being run filename, and "file_2" — is a string of digits and small English letters with length from 1 to 6.

Demo Input:
['5\n01 0\n2 1\n2extra 0\n3 1\n99 0\n', '2\n1 0\n2 1\n', '5\n1 0\n11 1\n111 0\n1111 1\n11111 0\n']

Demo Output:
['4\nmove 3 1\nmove 01 5\nmove 2extra 4\nmove 99 3\n', '3\nmove 1 3\nmove 2 1\nmove 3 2', '5\nmove 1 5\nmove 11 1\nmove 1111 2\nmove 111 4\nmove 11111 3\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Raavan gave a problem to his son, Indrajeet, and asked him to solve the problem to prove his intelligence and power. The Problem was like: Given 3 integers, $N$, $K$, and $X$, produce an array $A$ of length $N$, in which the XOR of all elements of each contiguous sub-array, of length $K$, is exactly equal to $X$. Indrajeet found this problem very tricky and difficult, so, help him to solve this problem.

-----Note:-----
- $A$i must be an integer between $0$ to $10$$18$ (both inclusive), where $A$i denotes the $i$$th$ element of the array, $A$.
- If there are multiple solutions, satisfying the problem condition(s), you can print any "one" solution.

-----Input:-----
- First line will contain $T$, number of testcases. Then, the testcases follow. 
- Each testcase, contains a single line of input, of 3 integers, $N$, $K$, and $X$.

-----Output:-----
For each testcase, output in a single line, an array $A$ of $N$ integers, where each element of the array is between $0$ to $10$$18$ (both inclusive), satisfying the conditions of the problem, given by Raavan to his son.

-----Constraints:-----
- $1 \leq T \leq 1000$
- $1 \leq N \leq 10^3$
- $1 \leq K \leq N$
- $0 \leq X \leq 10$$18$

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

-----Sample Output:-----
4 4 4 4 4
3 7 3 7 3
11 6 9 11 6

-----Explanation:-----
$Sample$ $Case$ $-$ $1$: Since, we can see, the XOR of all elements of all sub-arrays of length $1$, is equal to $4$, hence, the array {$4,4,4,4,4$}, is a valid solution to the $Sample$ $Case$ $-$ $1$. All contiguous sub-arrays of length $1$, of the output array $A$, are as follows:
[1,1]: {4} - XOR([1,1]) = $4$
[2,2]: {4} - XOR([2,2]) = $4$
[3,3]: {4} - XOR([3,3]) = $4$
[4,4]: {4} - XOR([4,4]) = $4$
[5,5]: {4} - XOR([5,5]) = $4$

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
For $n$ lists $L_i$ $(i = 0, 1, ..., n-1)$, perform a sequence of the following operations.

* insert($t$, $x$): Insert an integer $x$ at the end of $L_t$.
* dump($t$): Print all elements in $L_t$.
* splice($s$, $t$): Transfer elements of $L_s$ to the end of $L_t$. $L_s$ becomes empty.



In the initial state, $L_i$ $(i = 0, 1, ..., n-1)$ are empty.

Constraints

* $1 \leq n \leq 1,000$
* $1 \leq q \leq 500,000$
* For a splice operation, $s \ne t$
* For a splice operation, $L_s$ is not empty
* The total number of elements printed by dump operations do not exceed 1,000,000
* $-1,000,000,000 \leq x \leq 1,000,000,000$

Input

The input is given in the following format.


$n \; q$
$query_1$
$query_2$
:
$query_q$


Each query $query_i$ is given by


0 $t$ $x$


or


1 $t$


or


2 $s$ $t$


where the first digits 0, 1 and 2 represent insert, dump and splice operations respectively.

Output

For each dump operation, print elements of the corresponding list in a line. Separete adjacency elements by a space character (do not print the space after the last element). Note that, if the list is empty, an empty line should be printed.

Example

Input

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


Output

1 2 3 4 5

6

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
< PREVIOUS KATA
NEXT KATA >
 
###Task:

You have to write a function `pattern` which returns the following Pattern(See Examples) upto (3n-2) rows, where n is parameter.

* Note:`Returning` the pattern is not the same as `Printing` the pattern.

####Rules/Note:
* The pattern should be created using only unit digits.
* If `n < 1` then it should return "" i.e. empty string.
* `The length of each line is same`, and is equal to the length of longest line in the pattern i.e. `length = (3n-2)`.
* Range of Parameters (for the sake of CW Compiler) :
  + `n ∈ (-∞,50]`

###Examples:

  + pattern(5) :

            11111    
            22222    
            33333    
            44444    
        1234555554321
        1234555554321
        1234555554321
        1234555554321
        1234555554321
            44444    
            33333    
            22222    
            11111    
        
  + pattern(11):

                  11111111111          
                  22222222222          
                  33333333333          
                  44444444444          
                  55555555555          
                  66666666666          
                  77777777777          
                  88888888888          
                  99999999999          
                  00000000000          
        1234567890111111111110987654321
        1234567890111111111110987654321
        1234567890111111111110987654321
        1234567890111111111110987654321
        1234567890111111111110987654321
        1234567890111111111110987654321
        1234567890111111111110987654321
        1234567890111111111110987654321
        1234567890111111111110987654321
        1234567890111111111110987654321
        1234567890111111111110987654321
                  00000000000          
                  99999999999          
                  88888888888          
                  77777777777          
                  66666666666          
                  55555555555          
                  44444444444          
                  33333333333          
                  22222222222          
                  11111111111          
                  
>>>LIST OF ALL MY KATAS<<<

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
On the way home, Karen decided to stop by the supermarket to buy some groceries.

She needs to buy a lot of goods, but since she is a student her budget is still quite limited. In fact, she can only spend up to *b* dollars.

The supermarket sells *n* goods. The *i*-th good can be bought for *c**i* dollars. Of course, each good can only be bought once.

Lately, the supermarket has been trying to increase its business. Karen, being a loyal customer, was given *n* coupons. If Karen purchases the *i*-th good, she can use the *i*-th coupon to decrease its price by *d**i*. Of course, a coupon cannot be used without buying the corresponding good.

There is, however, a constraint with the coupons. For all *i*<=≥<=2, in order to use the *i*-th coupon, Karen must also use the *x**i*-th coupon (which may mean using even more coupons to satisfy the requirement for that coupon).

Karen wants to know the following. What is the maximum number of goods she can buy, without exceeding her budget *b*?

Input Specification:
The first line of input contains two integers *n* and *b* (1<=≤<=*n*<=≤<=5000, 1<=≤<=*b*<=≤<=109), the number of goods in the store and the amount of money Karen has, respectively.

The next *n* lines describe the items. Specifically:
 -  The *i*-th line among these starts with two integers, *c**i* and *d**i* (1<=≤<=*d**i*<=&lt;<=*c**i*<=≤<=109), the price of the *i*-th good and the discount when using the coupon for the *i*-th good, respectively. -  If *i*<=≥<=2, this is followed by another integer, *x**i* (1<=≤<=*x**i*<=&lt;<=*i*), denoting that the *x**i*-th coupon must also be used before this coupon can be used.

Output Specification:
Output a single integer on a line by itself, the number of different goods Karen can buy, without exceeding her budget.

Demo Input:
['6 16\n10 9\n10 5 1\n12 2 1\n20 18 3\n10 2 3\n2 1 5\n', '5 10\n3 1\n3 1 1\n3 1 2\n3 1 3\n3 1 4\n']

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

Note:
In the first test case, Karen can purchase the following 4 items:
 -  Use the first coupon to buy the first item for 10 - 9 = 1 dollar. -  Use the third coupon to buy the third item for 12 - 2 = 10 dollars. -  Use the fourth coupon to buy the fourth item for 20 - 18 = 2 dollars. -  Buy the sixth item for 2 dollars. 
The total cost of these goods is 15, which falls within her budget. Note, for example, that she cannot use the coupon on the sixth item, because then she should have also used the fifth coupon to buy the fifth item, which she did not do here.

In the second test case, Karen has enough money to use all the coupons and purchase everything.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Some country consists of n cities, connected by a railroad network. The transport communication of the country is so advanced that the network consists of a minimum required number of (n - 1) bidirectional roads (in the other words, the graph of roads is a tree). The i-th road that directly connects cities ai and bi, has the length of li kilometers.

The transport network is served by a state transporting company FRR (Fabulous Rail Roads). In order to simplify the price policy, it offers a single ride fare on the train. In order to follow the route of length t kilometers, you need to pay <image> burles. Note that it is forbidden to split a long route into short segments and pay them separately (a special railroad police, or RRP, controls that the law doesn't get violated).

A Large Software Company decided to organize a programming tournament. Having conducted several online rounds, the company employees determined a list of finalists and sent it to the logistical department to find a place where to conduct finals. The Large Software Company can easily organize the tournament finals in any of the n cities of the country, so the the main factor in choosing the city for the last stage of the tournament is the total cost of buying tickets for all the finalists. We know that the i-th city of the country has wi cup finalists living there.

Help the company employees find the city such that the total cost of travel of all the participants to it is minimum.

Input

The first line of the input contains number n (1 ≤ n ≤ 200 000) — the number of cities in the country.

The next line contains n integers w1, w2, ..., wn (0 ≤ wi ≤ 108) — the number of finalists living in each city of the country.

Next (n - 1) lines contain the descriptions of the railroad, the i-th line contains three integers, ai, bi, li (1 ≤ ai, bi ≤ n, ai ≠ bi, 1 ≤ li ≤ 1000).

Output

Print two numbers — an integer f that is the number of the optimal city to conduct the competition, and the real number c, equal to the minimum total cost of transporting all the finalists to the competition. Your answer will be considered correct if two conditions are fulfilled at the same time: 

  1. The absolute or relative error of the printed number c in comparison with the cost of setting up a final in city f doesn't exceed 10 - 6; 
  2. Absolute or relative error of the printed number c in comparison to the answer of the jury doesn't exceed 10 - 6. 



If there are multiple answers, you are allowed to print any of them.

Examples

Input

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


Output

3 192.0

Input

2
5 5
1 2 2


Output

1 14.142135623730951000

Note

In the sample test an optimal variant of choosing a city to conduct the finals of the competition is 3. At such choice the cost of conducting is <image> burles.

In the second sample test, whatever city you would choose, you will need to pay for the transport for five participants, so you will need to pay <image> burles for each one of them.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Kostya likes Codeforces contests very much. However, he is very disappointed that his solutions are frequently hacked. That's why he decided to obfuscate (intentionally make less readable) his code before upcoming contest.

To obfuscate the code, Kostya first looks at the first variable name used in his program and replaces all its occurrences with a single symbol a, then he looks at the second variable name that has not been replaced yet, and replaces all its occurrences with b, and so on. Kostya is well-mannered, so he doesn't use any one-letter names before obfuscation. Moreover, there are at most 26 unique identifiers in his programs.

You are given a list of identifiers of some program with removed spaces and line breaks. Check if this program can be a result of Kostya's obfuscation.


-----Input-----

In the only line of input there is a string S of lowercase English letters (1 ≤ |S| ≤ 500) — the identifiers of a program with removed whitespace characters.


-----Output-----

If this program can be a result of Kostya's obfuscation, print "YES" (without quotes), otherwise print "NO".


-----Examples-----
Input
abacaba

Output
YES

Input
jinotega

Output
NO



-----Note-----

In the first sample case, one possible list of identifiers would be "number string number character number string number". Here how Kostya would obfuscate the program:



 replace all occurences of number with a, the result would be "a string a character a string a",

 replace all occurences of string with b, the result would be "a b a character a b a",

 replace all occurences of character with c, the result would be "a b a c a b a",

 all identifiers have been replaced, thus the obfuscation is finished.

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