vgel/INTELLECT-2-RL-Dataset-Code-Only huggingface dataset:
Title: Gadgets for dollars and pounds

Time Limit: None seconds

Memory Limit: None megabytes

Problem Description:
Nura wants to buy *k* gadgets. She has only *s* burles for that. She can buy each gadget for dollars or for pounds. So each gadget is selling only for some type of currency. The type of currency and the cost in that currency are not changing.

Nura can buy gadgets for *n* days. For each day you know the exchange rates of dollar and pound, so you know the cost of conversion burles to dollars or to pounds.

Each day (from 1 to *n*) Nura can buy some gadgets by current exchange rate. Each day she can buy any gadgets she wants, but each gadget can be bought no more than once during *n* days.

Help Nura to find the minimum day index when she will have *k* gadgets. Nura always pays with burles, which are converted according to the exchange rate of the purchase day. Nura can't buy dollars or pounds, she always stores only burles. Gadgets are numbered with integers from 1 to *m* in order of their appearing in input.

Input Specification:
First line contains four integers *n*,<=*m*,<=*k*,<=*s* (1<=≤<=*n*<=≤<=2·105,<=1<=≤<=*k*<=≤<=*m*<=≤<=2·105,<=1<=≤<=*s*<=≤<=109) — number of days, total number and required number of gadgets, number of burles Nura has.

Second line contains *n* integers *a**i* (1<=≤<=*a**i*<=≤<=106) — the cost of one dollar in burles on *i*-th day.

Third line contains *n* integers *b**i* (1<=≤<=*b**i*<=≤<=106) — the cost of one pound in burles on *i*-th day.

Each of the next *m* lines contains two integers *t**i*,<=*c**i* (1<=≤<=*t**i*<=≤<=2,<=1<=≤<=*c**i*<=≤<=106) — type of the gadget and it's cost. For the gadgets of the first type cost is specified in dollars. For the gadgets of the second type cost is specified in pounds.

Output Specification:
If Nura can't buy *k* gadgets print the only line with the number -1.

Otherwise the first line should contain integer *d* — the minimum day index, when Nura will have *k* gadgets. On each of the next *k* lines print two integers *q**i*,<=*d**i* — the number of gadget and the day gadget should be bought. All values *q**i* should be different, but the values *d**i* can coincide (so Nura can buy several gadgets at one day). The days are numbered from 1 to *n*.

In case there are multiple possible solutions, print any of them.

Demo Input:
['5 4 2 2\n1 2 3 2 1\n3 2 1 2 3\n1 1\n2 1\n1 2\n2 2\n', '4 3 2 200\n69 70 71 72\n104 105 106 107\n1 1\n2 2\n1 2\n', '4 3 1 1000000000\n900000 910000 940000 990000\n990000 999000 999900 999990\n1 87654\n2 76543\n1 65432\n']

Demo Output:
['3\n1 1\n2 3\n', '-1\n', '-1\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Given a string, find the rank of the string amongst its permutations sorted lexicographically. 
Example 1:
Input:
S = "abc"
Output:
1
Explanation:
The order permutations with letters 
'a', 'c', and 'b' : 
abc
acb
bac
bca
cab
cba
Example 2:
Input:
S = "acb"
Output:
2
Your Task:
You don't need to read input or print anything. Your task is to complete the function findRank() which takes the string S as input parameter and returns the rank of the string amongst its permutations.
It is guaranteed no characters are repeated in the string.
Expected Time Complexity: O(|S|*26)
Expected Auxiliary Space: O(|S|)
Note: |S| represents the length of string S.
Constraints:
1 ≤ |S| ≤ 18

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In AtCoder Kingdom, Gregorian calendar is used, and dates are written in the "year-month-day" order, or the "month-day" order without the year.

For example, May 3, 2018 is written as 2018-5-3, or 5-3 without the year.  
In this country, a date is called Takahashi when the month and the day are equal as numbers. For example, 5-5 is Takahashi.

How many days from 2018-1-1 through 2018-a-b are Takahashi?

-----Constraints-----
 - a is an integer between 1 and 12 (inclusive).
 - b is an integer between 1 and 31 (inclusive).
 - 2018-a-b is a valid date in Gregorian calendar.

-----Input-----
Input is given from Standard Input in the following format:
a b

-----Output-----
Print the number of days from 2018-1-1 through 2018-a-b that are Takahashi.

-----Sample Input-----
5 5

-----Sample Output-----
5

There are five days that are Takahashi: 1-1, 2-2, 3-3, 4-4 and 5-5.

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

Time Limit: 2 seconds

Memory Limit: 256 megabytes

Problem Description:
Nowadays the one-way traffic is introduced all over the world in order to improve driving safety and reduce traffic jams. The government of Berland decided to keep up with new trends. Formerly all *n* cities of Berland were connected by *n* two-way roads in the ring, i. e. each city was connected directly to exactly two other cities, and from each city it was possible to get to any other city. Government of Berland introduced one-way traffic on all *n* roads, but it soon became clear that it's impossible to get from some of the cities to some others. Now for each road is known in which direction the traffic is directed at it, and the cost of redirecting the traffic. What is the smallest amount of money the government should spend on the redirecting of roads so that from every city you can get to any other?

Input Specification:
The first line contains integer *n* (3<=≤<=*n*<=≤<=100) — amount of cities (and roads) in Berland. Next *n* lines contain description of roads. Each road is described by three integers *a**i*, *b**i*, *c**i* (1<=≤<=*a**i*,<=*b**i*<=≤<=*n*,<=*a**i*<=≠<=*b**i*,<=1<=≤<=*c**i*<=≤<=100) — road is directed from city *a**i* to city *b**i*, redirecting the traffic costs *c**i*.

Output Specification:
Output single integer — the smallest amount of money the government should spend on the redirecting of roads so that from every city you can get to any other.

Demo Input:
['3\n1 3 1\n1 2 1\n3 2 1\n', '3\n1 3 1\n1 2 5\n3 2 1\n', '6\n1 5 4\n5 3 8\n2 4 15\n1 6 16\n2 3 23\n4 6 42\n', '4\n1 2 9\n2 3 8\n3 4 7\n4 1 5\n']

Demo Output:
['1\n', '2\n', '39\n', '0\n']

Note:
none

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Tim is an absolutely obsessive soda drinker, he simply cannot get enough. Most annoyingly though, he almost never has any money, so his only obvious legal way to obtain more soda is to take the money he gets when he recycles empty soda bottles to buy new ones. In addition to the empty bottles resulting from his own consumption he sometimes find empty bottles in the street. One day he was extra thirsty, so he actually drank sodas until he couldn’t afford a new one.

-----Input-----
Three non-negative integers $e,f,c$, where $e<1000$ equals the number of empty soda bottles in Tim’s possession at the start of the day, $f<1000$ the number of empty soda bottles found during the day, and $2 \le c<2000$ the number of empty bottles required to buy a new soda.

-----Output-----
How many sodas did Tim drink on his extra thirsty day?

-----Examples-----
Sample Input:
9 0 3
Sample Output:
4

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Victoria has a tree, $\mathbf{T}$, consisting of $N$ nodes numbered from $1$ to $N$. Each edge from node $U_i$ to $V_i$ in tree $\mathbf{T}$ has an integer weight, $W_i$.

Let's define the cost, $\mbox{C}$, of a path from some node $\mbox{X}$ to some other node $\mathbf{Y}$ as the maximum weight ($\mbox{w}$) for any edge in the unique path from node $\mbox{X}$ to node $\mathbf{Y}$.

Victoria wants your help processing $Q$ queries on tree $\mathbf{T}$, where each query contains $2$ integers, $\boldsymbol{\mbox{L}}$ and $\mbox{R}$, such that $L\leq R$. For each query, she wants to print the number of different paths in $\mathbf{T}$ that have a cost, $\mbox{C}$, in the inclusive range $[L,R]$.

It should be noted that path from some node $\mbox{X}$ to some other node $\mathbf{Y}$ is considered same as path from node $\mathbf{Y}$ to $\mbox{X}$ i.e $\{X,Y\}$ is same as $\{Y,X\}$. 

Input Format

The first line contains $2$ space-separated integers, $N$ (the number of nodes) and $Q$ (the number of queries), respectively. 

Each of the $N-1$ subsequent lines contain $3$ space-separated integers, $\mbox{U}$, $\mbox{V}$, and $\mbox{w}$, respectively, describing a bidirectional road between nodes $\mbox{U}$ and $\mbox{V}$ which has weight $\mbox{w}$. 

The $Q$ subsequent lines each contain $2$ space-separated integers denoting $\boldsymbol{\mbox{L}}$ and $\mbox{R}$.

Constraints

$1\leq N,Q\leq10^5$   
$1\leq U,V\leq N$   
$1\leq W\leq10^9$  
$1\leq L\leq R\leq10^9$ 

Scoring

$1\leq N,Q\leq10^3$ for $30\%$ of the test data.  
$1\leq N,Q\leq10^5$ for $\textbf{100\%}$ of the test data.

Output Format

For each of the $Q$ queries, print the number of paths in $\mathbf{T}$ having cost $\mbox{C}$ in the inclusive range $[L,R]$ on a new line.

Sample Input
5 5
1 2 3
1 4 2
2 5 6
3 4 1
1 1
1 2
2 3
2 5
1 6

Sample Output
1
3
5
5
10

Explanation

$Q_1$: $\{3,4\}$ 

$Q_2$: $\{1,3\},\{3,4\},\{1,4\}$ 

$Q_3$: $\{1,4\},\{1,2\},\{2,4\},\{1,3\},\{2,3\}$ 

$Q_4$: $\{1,4\},\{1,2\},\{2,4\},\{1,3\},\{2,3\}$ 

...etc.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Rule 30 is a one-dimensional binary cellular automaton. You can have some information here:  

* [https://en.wikipedia.org/wiki/Rule_30](https://en.wikipedia.org/wiki/Rule_30)

You have to write a function that takes as input an array of 0 and 1 and a positive integer that represents the number of iterations. This function has to performe the nth iteration of the **Rule 30** with the given input.

The rule to derive a cell from itself and its neigbour is:

Current cell  | 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111
:-------------|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:
 **New cell** |  0  |  1  |  1  |  1  |  1  |  0  |  0  |  0 
 

As you can see the new state of a certain cell depends on his neighborhood. In *Current cells* you have the *nth* cell with his left and right neighbor, for example the first configuration is **000**:

* left neighbor = 0
* current cell = 0
* right neighbor = 0

The result for the current cell is **0**, as reported in **New cell** row.

You also have to pay attention to the following things:

* the borders of the list are always 0
* values different from 0 and 1 must be considered as 0
* a negative number of iteration never changes the initial sequence
* you have to return an array of 0 and 1

Here a small example step by step, starting from the list **[1]** and iterating for 5 times:

* We have only one element so first of all we have to follow the rules adding the border, so the result will be **[0, 1, 0]**
* Now we can apply the rule 30 to all the elements and the result will be **[1, 1, 1]** (first iteration)
* Then, after continuing this way for 4 times, the result will be **[1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1]**

In Python, you can also use a support function to print the sequence named printRule30. This function takes as parameters the current list of 0 and 1 to print, the max level that you can reach (number of iterations) and the length of initial array.

```python
def printRule30(list_, maxLvl, startLen):
  ...
```

The last two parameters are optional and are useful if you are printing each line of the iteration to center the result like this:

░░▓░░  -> step 1  
░▓▓▓░  -> step 2  
▓▓░░▓  -> step 3  

If you pass only the array of 0 and 1 the previous result for each line will be like this:

▓ -> step 1   
▓▓▓ -> step 2  
▓▓░░▓ -> step 3 

**Note:** the function can print only the current list that you pass to it, so you have to use it in the proper way during the interactions of the rule 30.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
There are n glasses on the table numbered 1, …, n. The glass i can hold up to a_i units of water, and currently contains b_i units of water.

You would like to choose k glasses and collect as much water in them as possible. To that effect you can pour water from one glass to another as many times as you like. However, because of the glasses' awkward shape (and totally unrelated to your natural clumsiness), each time you try to transfer any amount of water, half of the amount is spilled on the floor.

Formally, suppose a glass i currently contains c_i units of water, and a glass j contains c_j units of water. Suppose you try to transfer x units from glass i to glass j (naturally, x can not exceed c_i). Then, x / 2 units is spilled on the floor. After the transfer is done, the glass i will contain c_i - x units, and the glass j will contain min(a_j, c_j + x / 2) units (excess water that doesn't fit in the glass is also spilled).

Each time you transfer water, you can arbitrarlly choose from which glass i to which glass j to pour, and also the amount x transferred can be any positive real number.

For each k = 1, …, n, determine the largest possible total amount of water that can be collected in arbitrarily chosen k glasses after transferring water between glasses zero or more times.

Input

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

The following n lines describe the glasses. The i-th of these lines contains two integers a_i and b_i (0 ≤ b_i ≤ a_i ≤ 100, a_i > 0) — capacity, and water amount currently contained for the glass i, respectively.

Output

Print n real numbers — the largest amount of water that can be collected in 1, …, n glasses respectively. Your answer will be accepted if each number is within 10^{-9} absolute or relative tolerance of the precise answer.

Example

Input


3
6 5
6 5
10 2


Output


7.0000000000 11.0000000000 12.0000000000

Note

In the sample case, you can act as follows:

  * for k = 1, transfer water from the first two glasses to the third one, spilling (5 + 5) / 2 = 5 units and securing 2 + (5 + 5) / 2 = 7 units;
  * for k = 2, transfer water from the third glass to any of the first two, spilling 2 / 2 = 1 unit and securing 5 + 5 + 2 / 2 = 11 units;
  * for k = 3, do nothing. All 5 + 5 + 2 = 12 units are secured.

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Trouble has come to the remote group of islands known as Insumulia. Due to an unfortunate combination of over-consumption, natural climate variations, and generally difficult conditions, the island of Incunabula has run out of trees. Because several other Insumulian islands depended on trees from Incunabula through trade, its collapse will have repercussions all over Insumulia. In this problem, we’ll simulate a (highly oversimplified) model of the situation to determine the effects of the collapse of Incunabula. 

We model the situation as follows. Each island has a threshold $T_ i$ on the amount of incoming goods (for simplicity we assume that there is only a single commodity of goods) it needs to receive per lunar cycle in order for the society of the island to sustain itself. If the amount of incoming goods drops below the threshold, society on the island will collapse and die out, and the island will no longer provide goods to other islands, thereby potentially causing them to collapse as well. Each island provides some amount of goods to a number of other islands. If an island collapses, we assume that goods that would have been delivered to that island is effectively lost; it does not get redistributed and delivered to other islands instead. Also, once an island dies out it is not repopulated (until possibly long after the ongoing collapses have finished).

Your job is to write a program to compute the number of islands that survive after the potential chain reaction of collapses that is caused by the collapse of Incunabula.

-----Input-----
The first line of input contains an integer $N$ ($1 \le N \le 100000$), the number of islands in Insumulia.

Then follow $N$ lines, describing each island. The $i$’th such description starts with two integers $T_ i$, $K_ i$, where $0 \le T_ i \le 50000$ is the amount of goods the $i$’th island needs to receive in order to survive, and $0 \le K_ i \le N-1$ is the number of other islands the $i$’th islands receives goods from. The remainder of the description of the $i$’th island is a list of $K_ i$ pairs of integers. The $j$’th such pair, $S_{ij}$, $V_{ij}$, indicates that island $i$ receives $V_{ij}$ units of goods from island $S_{ij}$ each lunar cycle. You may assume that the $S_{ij}$’s are distinct and between $1$ and $N$ (inclusive), and that none of them equals $i$. The values $V_{ij}$ satisfy $1 \le V_{ij} \le 1000$ and their sum is at least $T_ i$. The sum of all the $K_ i$’s for all the $N$ islands is at most $500000$.

Islands are numbered from $1$ to $N$, and Incunabula is island number $1$.

-----Output-----
Output a single integer, the number of islands surviving the collapses.

-----Examples-----
Sample Input:
4
0 0
25 3 1 10 3 10 4 10
10 1 2 10
10 1 2 10
Sample Output:
0

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
Polycarp has an array $a$ consisting of $n$ integers.

He wants to play a game with this array. The game consists of several moves. On the first move he chooses any element and deletes it (after the first move the array contains $n-1$ elements). For each of the next moves he chooses any element with the only restriction: its parity should differ from the parity of the element deleted on the previous move. In other words, he alternates parities (even-odd-even-odd-... or odd-even-odd-even-...) of the removed elements. Polycarp stops if he can't make a move.

Formally:   If it is the first move, he chooses any element and deletes it;  If it is the second or any next move:   if the last deleted element was odd, Polycarp chooses any even element and deletes it;  if the last deleted element was even, Polycarp chooses any odd element and deletes it.   If after some move Polycarp cannot make a move, the game ends. 

Polycarp's goal is to minimize the sum of non-deleted elements of the array after end of the game. If Polycarp can delete the whole array, then the sum of non-deleted elements is zero.

Help Polycarp find this value.


-----Input-----

The first line of the input contains one integer $n$ ($1 \le n \le 2000$) — the number of elements of $a$.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^6$), where $a_i$ is the $i$-th element of $a$.


-----Output-----

Print one integer — the minimum possible sum of non-deleted elements of the array after end of the game.


-----Examples-----
Input
5
1 5 7 8 2

Output
0

Input
6
5 1 2 4 6 3

Output
0

Input
2
1000000 1000000

Output
1000000

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
In an array A containing only 0s and 1s, a K-bit flip consists of choosing a (contiguous) subarray of length K and simultaneously changing every 0 in the subarray to 1, and every 1 in the subarray to 0.
Return the minimum number of K-bit flips required so that there is no 0 in the array.  If it is not possible, return -1.
 
Example 1:
Input: A = [0,1,0], K = 1
Output: 2
Explanation: Flip A[0], then flip A[2].


Example 2:
Input: A = [1,1,0], K = 2
Output: -1
Explanation: No matter how we flip subarrays of size 2, we can't make the array become [1,1,1].


Example 3:
Input: A = [0,0,0,1,0,1,1,0], K = 3
Output: 3
Explanation:
Flip A[0],A[1],A[2]: A becomes [1,1,1,1,0,1,1,0]
Flip A[4],A[5],A[6]: A becomes [1,1,1,1,1,0,0,0]
Flip A[5],A[6],A[7]: A becomes [1,1,1,1,1,1,1,1]

 


Note:

1 <= A.length <= 30000
1 <= K <= A.length

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You are given an integer k and an undirected tree, consisting of n vertices.

The length of a simple path (a path in which each vertex appears at most once) between some pair of vertices is the number of edges in this path. A diameter of a tree is the maximum length of a simple path between all pairs of vertices of this tree.

You are about to remove a set of edges from the tree. The tree splits into multiple smaller trees when the edges are removed. The set of edges is valid if all the resulting trees have diameter less than or equal to k.

Two sets of edges are different if there is an edge such that it appears in only one of the sets.

Count the number of valid sets of edges modulo 998 244 353.

Input

The first line contains two integers n and k (2 ≤ n ≤ 5000, 0 ≤ k ≤ n - 1) — the number of vertices of the tree and the maximum allowed diameter, respectively.

Each of the next n-1 lines contains a description of an edge: two integers v and u (1 ≤ v, u ≤ n, v ≠ u).

The given edges form a tree.

Output

Print a single integer — the number of valid sets of edges modulo 998 244 353.

Examples

Input


4 3
1 2
1 3
1 4


Output


8


Input


2 0
1 2


Output


1


Input


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


Output


25


Input


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


Output


29

Note

In the first example the diameter of the given tree is already less than or equal to k. Thus, you can choose any set of edges to remove and the resulting trees will have diameter less than or equal to k. There are 2^3 sets, including the empty one.

In the second example you have to remove the only edge. Otherwise, the diameter will be 1, which is greater than 0.

Here are the trees for the third and the fourth examples: 

<image>

Write Python code to solve the problem. Present the code in 
```python
Your code
```
at the end.
You have a garland consisting of $n$ lamps. Each lamp is colored red, green or blue. The color of the $i$-th lamp is $s_i$ ('R', 'G' and 'B' — colors of lamps in the garland).

You have to recolor some lamps in this garland (recoloring a lamp means changing its initial color to another) in such a way that the obtained garland is diverse.

A garland is called diverse if any two adjacent (consecutive) lamps (i. e. such lamps that the distance between their positions is $1$) have distinct colors.

In other words, if the obtained garland is $t$ then for each $i$ from $1$ to $n-1$ the condition $t_i \ne t_{i + 1}$ should be satisfied.

Among all ways to recolor the initial garland to make it diverse you have to choose one with the minimum number of recolored lamps. If there are multiple optimal solutions, print any of them.


-----Input-----

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

The second line of the input contains the string $s$ consisting of $n$ characters 'R', 'G' and 'B' — colors of lamps in the garland.


-----Output-----

In the first line of the output print one integer $r$ — the minimum number of recolors needed to obtain a diverse garland from the given one.

In the second line of the output print one string $t$ of length $n$ — a diverse garland obtained from the initial one with minimum number of recolors. If there are multiple optimal solutions, print any of them.


-----Examples-----
Input
9
RBGRRBRGG

Output
2
RBGRGBRGR

Input
8
BBBGBRRR

Output
2
BRBGBRGR

Input
13
BBRRRRGGGGGRR

Output
6
BGRBRBGBGBGRG

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