vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Write a program which manipulates a weighted rooted tree $T$ with the following operations:

* $add(v,w)$: add $w$ to all edges from the root to node $u$

* $getSum(u)$: report the sum of weights of all edges from the root to node $u$



The given tree $T$ consists of $n$ nodes and every node has a unique ID from $0$ to $n-1$ respectively where ID of the root is $0$. Note that all weights are initialized to zero.

Constraints

* All the inputs are given in integers
* $ 2 \leq n \leq 100000 $
* $ c_j < c_{j+1} $   $( 1 \leq j \leq k-1 )$
* $ 2 \leq q \leq 200000 $
* $ 1 \leq u,v \leq n-1 $
* $ 1 \leq w \leq 10000 $

Input

The input is given in the following format.

$n$
$node_0$
$node_1$
$node_2$
$:$
$node_{n-1}$
$q$
$query_1$
$query_2$
$:$
$query_{q}$


The first line of the input includes an integer $n$, the number of nodes in the tree.

In the next $n$ lines,the information of node $i$ is given in the following format:


ki c1 c2 ... ck


$k_i$ is the number of children of node $i$, and $c_1$ $c_2$ ... $c_{k_i}$ are node IDs of 1st, ... $k$th child of node $i$.

In the next line, the number of queries $q$ is given. In the next $q$ lines, $i$th query is given in the following format:


0 v w


or


1 u


The first integer represents the type of queries.'0' denotes $add(v, w)$ and '1' denotes $getSum(u)$.

Output

For each $getSum$ query, print the sum in a line.

Examples

Input

6
2 1 2
2 3 5
0
0
0
1 4
7
1 1
0 3 10
1 2
0 4 20
1 3
0 5 40
1 4


Output

0
0
40
150


Input

4
1 1
1 2
1 3
0
6
0 3 1000
0 2 1000
0 1 1000
1 1
1 2
1 3


Output

3000
5000
6000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
A group of n merry programmers celebrate Robert Floyd's birthday. Polucarpus has got an honourable task of pouring Ber-Cola to everybody. Pouring the same amount of Ber-Cola to everybody is really important. In other words, the drink's volume in each of the n mugs must be the same.

Polycarpus has already began the process and he partially emptied the Ber-Cola bottle. Now the first mug has a1 milliliters of the drink, the second one has a2 milliliters and so on. The bottle has b milliliters left and Polycarpus plans to pour them into the mugs so that the main equation was fulfilled.

Write a program that would determine what volume of the drink Polycarpus needs to add into each mug to ensure that the following two conditions were fulfilled simultaneously: 

  * there were b milliliters poured in total. That is, the bottle need to be emptied; 
  * after the process is over, the volumes of the drink in the mugs should be equal. 

Input

The first line contains a pair of integers n, b (2 ≤ n ≤ 100, 1 ≤ b ≤ 100), where n is the total number of friends in the group and b is the current volume of drink in the bottle. The second line contains a sequence of integers a1, a2, ..., an (0 ≤ ai ≤ 100), where ai is the current volume of drink in the i-th mug.

Output

Print a single number "-1" (without the quotes), if there is no solution. Otherwise, print n float numbers c1, c2, ..., cn, where ci is the volume of the drink to add in the i-th mug. Print the numbers with no less than 6 digits after the decimal point, print each ci on a single line. Polycarpus proved that if a solution exists then it is unique.

Russian locale is installed by default on the testing computer. Make sure that your solution use the point to separate the integer part of a real number from the decimal, not a comma.

Examples

Input

5 50
1 2 3 4 5


Output

12.000000
11.000000
10.000000
9.000000
8.000000


Input

2 2
1 100


Output

-1

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Snuke has a favorite restaurant.
The price of any meal served at the restaurant is 800 yen (the currency of Japan), and each time a customer orders 15 meals, the restaurant pays 200 yen back to the customer.
So far, Snuke has ordered N meals at the restaurant.
Let the amount of money Snuke has paid to the restaurant be x yen, and let the amount of money the restaurant has paid back to Snuke be y yen.
Find x-y.

-----Constraints-----
 - 1 ≤ N ≤ 100

-----Input-----
The input is given from Standard Input in the following format:
N

-----Output-----
Print the answer.

-----Sample Input-----
20

-----Sample Output-----
15800

So far, Snuke has paid 16000 yen, and the restaurant has paid back 200 yen. Thus, the answer is 15800.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
The concept of "[smooth number](https://en.wikipedia.org/wiki/Smooth_number)" is applied to all those numbers whose prime factors are lesser than or equal to `7`: `60` is a smooth number (`2 * 2 * 3 * 5`), `111` is not (`3 * 37`).

More specifically, smooth numbers are classified by their highest prime factor and your are tasked with writing a `isSmooth`/`is_smooth` function that returns a string with this classification as it follows:

* 2-smooth numbers should be all defined as a `"power of 2"`, as they are merely that;
* 3-smooth numbers are to return a result of `"3-smooth"`;
* 5-smooth numbers will be labelled as `"Hamming number"`s (incidentally, you might appreciate [this nice kata on them](https://www.codewars.com/kata/hamming-numbers));
* 7-smooth numbers are classified as `"humble numbers"`s;
* for all the other numbers, just return `non-smooth`.

Examples:
```python
is_smooth(16) == "power of 2"
is_smooth(36) == "3-smooth"
is_smooth(60) == "Hamming number"
is_smooth(98) == "humble number"
is_smooth(111) == "non-smooth"
```
The provided input `n` is always going to be a positive number `> 1`.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
```if-not:sql
Implement a function that receives two IPv4 addresses, and returns the number of addresses between them (including the first one, excluding the last one).
```

```if:sql
Given a database of first and last IPv4 addresses, calculate the number of addresses between them (including the first one, excluding the last one).

## Input

~~~
---------------------------------
|     Table    | Column | Type  |
|--------------+--------+-------|
| ip_addresses | id     | int   |
|              | first  | text  |
|              | last   | text  |
---------------------------------
~~~

## Output

~~~
----------------------
|   Column    | Type |
|-------------+------|
| id          | int  |
| ips_between | int  |
----------------------
~~~
```

All inputs will be valid IPv4 addresses in the form of strings. The last address will always be greater than the first one.

___

## Examples

```python
ips_between("10.0.0.0", "10.0.0.50")  ==   50 
ips_between("10.0.0.0", "10.0.1.0")   ==  256 
ips_between("20.0.0.10", "20.0.1.0")  ==  246
```

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
We consider a positive integer perfect, if and only if the sum of its digits is exactly $10$. Given a positive integer $k$, your task is to find the $k$-th smallest perfect positive integer.


-----Input-----

A single line with a positive integer $k$ ($1 \leq k \leq 10\,000$).


-----Output-----

A single number, denoting the $k$-th smallest perfect integer.


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

Output
19

Input
2

Output
28



-----Note-----

The first perfect integer is $19$ and the second one is $28$.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In a 2 dimensional array grid, each value grid[i][j] represents the height of a building located there. We are allowed to increase the height of any number of buildings, by any amount (the amounts can be different for different buildings). Height 0 is considered to be a building as well. 
At the end, the "skyline" when viewed from all four directions of the grid, i.e. top, bottom, left, and right, must be the same as the skyline of the original grid. A city's skyline is the outer contour of the rectangles formed by all the buildings when viewed from a distance. See the following example.
What is the maximum total sum that the height of the buildings can be increased?
Example:
Input: grid = [[3,0,8,4],[2,4,5,7],[9,2,6,3],[0,3,1,0]]
Output: 35
Explanation: 
The grid is:
[ [3, 0, 8, 4], 
  [2, 4, 5, 7],
  [9, 2, 6, 3],
  [0, 3, 1, 0] ]

The skyline viewed from top or bottom is: [9, 4, 8, 7]
The skyline viewed from left or right is: [8, 7, 9, 3]

The grid after increasing the height of buildings without affecting skylines is:

gridNew = [ [8, 4, 8, 7],
            [7, 4, 7, 7],
            [9, 4, 8, 7],
            [3, 3, 3, 3] ]


Notes: 

1 < grid.length = grid[0].length <= 50.
All heights grid[i][j] are in the range [0, 100].
All buildings in grid[i][j] occupy the entire grid cell: that is, they are a 1 x 1 x grid[i][j] rectangular prism.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are competing in a ski slalom, and you need to select the best skis for the race. The format of the race is that there are $N$ pairs of left and right gates, where each right gate is $W$ metres to the right of its corresponding left gate, and you may neither pass to the left of the left gate nor to the right of the right gate. The $i$-th pair of gates occurs at distance $y_{i}$ down the hill, with the horizontal position of the $i$<sup>th</sup> left gate given by $x_{i}$. Each gate is further down the hill than the previous gate (i.e. $y_{i}$ < $y_{i+1}$ for all $i$). 

You may select from $S$ pairs of skis, where the $j$-th pair has speed $s_{j}$. Your movement is governed by the following rule: if you select a pair of skis with speed $s_{j}$, you move with a constant downward velocity of $s_{j}$ metres per second. Additionally, at any time you may move at a horizontal speed of at most $v_{h}$ metres per second.

You may start and finish at any two horizontal positions. Determine which pair of skis will allow you to get through the race course, passing through all the gates, in the shortest amount of time.

-----Input Specification-----
The first line of input contains the three integers $W$, $v_{h}$, and $N$, separated by spaces, with $1 <= W <= 10^8$, $1 \leq v_{h} \leq 10^6$, and $1 \leq N \leq 10^5$.

The following $N$ lines of input each contain two integers $x_{i}$ and $y_{i}$, the horizontal and vertical positions respectively of the $i$-th left gate, with $1 \leq x_{i},y_{i} \leq 10^8$.

The next line of input contains an integer $S$, the number of skis, with $1 \leq S \leq 10^6$.

The following $S$ lines of input each contain one integer $s_{j}$, the speed of the $j$-th pair of skis, with $1 \leq s_{j} \leq 10^6$.

-----Output Specification-----
If it is impossible to complete the race with any pair of skis, print the line IMPOSSIBLE. Otherwise, print the vertical speed $s_{j}$ of the pair of skis that allows you to get through the race course in the shortest time.

-----Examples-----
Sample Input:
3 2 3
1 1
5 2
1 3
3
3
2
1
Sample Output:
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
After a hard day Vitaly got very hungry and he wants to eat his favorite potato pie. But it's not that simple. Vitaly is in the first room of the house with n room located in a line and numbered starting from one from left to right. You can go from the first room to the second room, from the second room to the third room and so on — you can go from the (n - 1)-th room to the n-th room. Thus, you can go to room x only from room x - 1.

The potato pie is located in the n-th room and Vitaly needs to go there. 

Each pair of consecutive rooms has a door between them. In order to go to room x from room x - 1, you need to open the door between the rooms with the corresponding key. 

In total the house has several types of doors (represented by uppercase Latin letters) and several types of keys (represented by lowercase Latin letters). The key of type t can open the door of type T if and only if t and T are the same letter, written in different cases. For example, key f can open door F.

Each of the first n - 1 rooms contains exactly one key of some type that Vitaly can use to get to next rooms. Once the door is open with some key, Vitaly won't get the key from the keyhole but he will immediately run into the next room. In other words, each key can open no more than one door.

Vitaly realizes that he may end up in some room without the key that opens the door to the next room. Before the start his run for the potato pie Vitaly can buy any number of keys of any type that is guaranteed to get to room n.

Given the plan of the house, Vitaly wants to know what is the minimum number of keys he needs to buy to surely get to the room n, which has a delicious potato pie. Write a program that will help Vitaly find out this number.


-----Input-----

The first line of the input contains a positive integer n (2 ≤ n ≤ 10^5) — the number of rooms in the house.

The second line of the input contains string s of length 2·n - 2. Let's number the elements of the string from left to right, starting from one. 

The odd positions in the given string s contain lowercase Latin letters — the types of the keys that lie in the corresponding rooms. Thus, each odd position i of the given string s contains a lowercase Latin letter — the type of the key that lies in room number (i + 1) / 2.

The even positions in the given string contain uppercase Latin letters — the types of doors between the rooms. Thus, each even position i of the given string s contains an uppercase letter — the type of the door that leads from room i / 2 to room i / 2 + 1.


-----Output-----

Print the only integer — the minimum number of keys that Vitaly needs to buy to surely get from room one to room n.


-----Examples-----
Input
3
aAbB

Output
0

Input
4
aBaCaB

Output
3

Input
5
xYyXzZaZ

Output
2

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
itertools.permutations(iterable[, r])

This tool returns successive $\textbf{r}$ length permutations of elements in an iterable.  

If $\textbf{r}$ is not specified or is None, then $\textbf{r}$ defaults to the length of the iterable, and all possible full length permutations are generated.  

Permutations are printed in a lexicographic sorted order. So, if the input iterable is sorted, the permutation tuples will be produced in a sorted order.

Sample Code

>>> from itertools import permutations
>>> print permutations(['1','2','3'])
<itertools.permutations object at 0x02A45210>
>>> 
>>> print list(permutations(['1','2','3']))
[('1', '2', '3'), ('1', '3', '2'), ('2', '1', '3'), ('2', '3', '1'), ('3', '1', '2'), ('3', '2', '1')]
>>> 
>>> print list(permutations(['1','2','3'],2))
[('1', '2'), ('1', '3'), ('2', '1'), ('2', '3'), ('3', '1'), ('3', '2')]
>>>
>>> print list(permutations('abc',3))
[('a', 'b', 'c'), ('a', 'c', 'b'), ('b', 'a', 'c'), ('b', 'c', 'a'), ('c', 'a', 'b'), ('c', 'b', 'a')]

Task  

You are given a string $\mbox{S}$. 

Your task is to print all possible permutations of size $\boldsymbol{\mbox{k}}$ of the string in lexicographic sorted order.

Input Format

A single line containing the space separated string $\mbox{S}$ and the integer value $\boldsymbol{\mbox{k}}$.

Constraints

$0<k\leq len(S)$ 

The string contains only UPPERCASE characters.

Output Format

Print the permutations of the string $\mbox{S}$ on separate lines. 

Sample Input
HACK 2

Sample Output
AC
AH
AK
CA
CH
CK
HA
HC
HK
KA
KC
KH

Explanation

All possible size $2$ permutations of the string "HACK" are printed in lexicographic sorted order.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There is a row of N walls in Geeksland. The king of Geeksland ordered Alexa to color all the walls on the occasion of New Year. Alexa can color each wall with one of the K colors. The cost associated with coloring each wall with a particular color is represented by a 2D costs array of size N * K. For example, costs[0][0] is the cost of coloring wall 0 with color 0; costs[1][2] is the cost of coloring wall 1 with color 2, and so on... Find the minimum cost to color all the walls such that no two adjacent walls have the same color.
Note: If you are not able to paint all the walls, then you should return -1.
Example 1:
Input:
N = 4, K = 3
costs[][] = {{1, 5, 7},
             {5, 8, 4},
             {3, 2, 9},
             {1, 2, 4}}
Output:
8
Explanation:
Paint wall 0 with color 0. Cost = 1
Paint wall 1 with color 2. Cost = 4
Paint wall 2 with color 1. Cost = 2
Paint wall 3 with color 0. Cost = 1
Total Cost = 1 + 4 + 2 + 1 = 8
Example 2:
Input:
N = 5, K = 1
costs[][] = {{5},
             {4},
             {9},
             {2},
             {1}}
Output:
-1
Explanation:
It is not possible to color all the walls under the given conditions.
Your Task:
Your task is to complete the function minCost() which takes a 2D integer matrix costs as the only argument and returns an integer, representing the minimum cost to paint all the walls. If you are not able to paint all the walls, then you should return -1
Expected Time Complexity: O(N*K)
Expected Space Complexity: O(N*K)
Constraints:
	0 <= N <= 10^{3}
	0 <= K <= 10^{3}
	1 <= costs[i][j] <= 10^{5}

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

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Polycarp starts his own business. Tomorrow will be the first working day of his car repair shop. For now the car repair shop is very small and only one car can be repaired at a given time.

Polycarp is good at marketing, so he has already collected *n* requests from clients. The requests are numbered from 1 to *n* in order they came.

The *i*-th request is characterized by two values: *s**i* — the day when a client wants to start the repair of his car, *d**i* — duration (in days) to repair the car. The days are enumerated from 1, the first day is tomorrow, the second day is the day after tomorrow and so on.

Polycarp is making schedule by processing requests in the order from the first to the *n*-th request. He schedules the *i*-th request as follows:
 -  If the car repair shop is idle for *d**i* days starting from *s**i* (*s**i*,<=*s**i*<=+<=1,<=...,<=*s**i*<=+<=*d**i*<=-<=1), then these days are used to repair a car of the *i*-th client. -  Otherwise, Polycarp finds the first day *x* (from 1 and further) that there are *d**i* subsequent days when no repair is scheduled starting from *x*. In other words he chooses the smallest positive *x* that all days *x*,<=*x*<=+<=1,<=...,<=*x*<=+<=*d**i*<=-<=1 are not scheduled for repair of any car. So, the car of the *i*-th client will be repaired in the range [*x*,<=*x*<=+<=*d**i*<=-<=1]. It is possible that the day *x* when repair is scheduled to start will be less than *s**i*. 
Given *n* requests, you are asked to help Polycarp schedule all of them according to the rules above.

Input Specification:
The first line contains integer *n* (1<=≤<=*n*<=≤<=200) — the number of requests from clients.

The following *n* lines contain requests, one request per line. The *i*-th request is given as the pair of integers *s**i*,<=*d**i* (1<=≤<=*s**i*<=≤<=109, 1<=≤<=*d**i*<=≤<=5·106), where *s**i* is the preferred time to start repairing the *i*-th car, *d**i* is the number of days to repair the *i*-th car.

The requests should be processed in the order they are given in the input.

Output Specification:
Print *n* lines. The *i*-th line should contain two integers — the start day to repair the *i*-th car and the finish day to repair the *i*-th car.

Demo Input:
['3\n9 2\n7 3\n2 4\n', '4\n1000000000 1000000\n1000000000 1000000\n100000000 1000000\n1000000000 1000000\n']

Demo Output:
['9 10\n1 3\n4 7\n', '1000000000 1000999999\n1 1000000\n100000000 100999999\n1000001 2000000\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a Complete Binary Tree of ‘n’ depth, you can perform 4 types of mirror operation on the tree:-

Mirror on the right. The tree is mirrored to the right and rightmost node on every level is connected with the mirrored corresponding node.

Mirror on the left. The tree is mirrored to the left and leftmost node on every level is connected with the mirrored corresponding node.

Mirror on the top. The tree is mirrored to the top and topmost nodes are connected with corresponding nodes.

Mirror on the bottom. The tree is mirrored to the bottom and bottom most nodes are connected with the corresponding nodes.

See the image for details.   
Mirror Right:  

Mirror Bottom:   

You are given ‘q’ queries, each performing this type of operation or asking for the no of edges in the produced graph.

Queries are of the form “1 x” or “2” where x is 1 for right, 2 for left, 3 for top or 4 for bottom.

1 x:  Perform x operation on the result graph.

2:     Print the no of edges in the graph. Since it can be very large, print it modulo 1000000007.   

-----Input:-----
- First line will contain $n$, the depth of the initial tree and $q$, the number of queries.    
- Next $q$ lines contain queries of the form "1 $x$" or "2".

-----Output:-----
For each query of type "2", output a single line containing the no of edges in the graph modulo 1000000007.

-----Constraints-----
- $1 \leq n \leq 1000$
- $1 \leq q \leq 10^5$
- $1 \leq x \leq 4$

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

-----Sample Output:-----
38

-----EXPLANATION:-----
Initial no of edges = 6

After the operation 1 1, no of edges = 15

After the operation 1 4, no of edges = 38

At operation 2, we print the no of edges that is 38.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Chef recently learned about ratios and proportions. He wrote some positive integers a, b, c, d on a paper. Chef wants to know whether he can shuffle these numbers so as to make some proportion? Formally, four numbers x, y, z, w are said to make a proportion if ratio of x : y is same as that of z : w.

-----Input-----
Only line of the input contains four space separated positive integers - a, b, c, d.

-----Output-----
Print "Possible" if it is possible to shuffle a, b, c, d to make proportion, otherwise "Impossible" (without quotes).

-----Constraints-----
- 1 ≤ a, b, c, d  ≤ 1000

-----Example-----
Input:
1 2 4 2

Output:
Possible

-----Explanation-----
By swapping 4 and the second 2, we get 1 2 2 4. Note that 1 2 2 4 make proportion as 1 : 2 = 2 : 4. Hence answer is "Possible"

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string s containing only lower case English letters and the '?' character, convert all the '?' characters into lower case letters such that the final string does not contain any consecutive repeating characters. You cannot modify the non '?' characters.
It is guaranteed that there are no consecutive repeating characters in the given string except for '?'.
Return the final string after all the conversions (possibly zero) have been made. If there is more than one solution, return any of them. It can be shown that an answer is always possible with the given constraints.
 
Example 1:
Input: s = "?zs"
Output: "azs"
Explanation: There are 25 solutions for this problem. From "azs" to "yzs", all are valid. Only "z" is an invalid modification as the string will consist of consecutive repeating characters in "zzs".
Example 2:
Input: s = "ubv?w"
Output: "ubvaw"
Explanation: There are 24 solutions for this problem. Only "v" and "w" are invalid modifications as the strings will consist of consecutive repeating characters in "ubvvw" and "ubvww".

Example 3:
Input: s = "j?qg??b"
Output: "jaqgacb"

Example 4:
Input: s = "??yw?ipkj?"
Output: "acywaipkja"

 
Constraints:

1 <= s.length <= 100
s contains only lower case English letters and '?'.

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