2025-2026 ICPC NERC, Kyrgyzstan Regional Contest
A. Borg Cube
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The Enterprise has finally found the Borg Cube, and now Picard must get inside. It is clear that the Borg have protected their Cube with a special code. Previously, the code could be easily calculated by reading the numbers in space located at the corners of the cube, but the Borg have covered these numbers with a protective field. The code itself is the sum of all eight numbers hidden at the corners of the Cube.

But now they are not visible...

However, since the Borg had to return to the Cube themselves, and not all of them remembered the code, a hint was left — the numbers on the sides of the Cube. Each corner number can be calculated by multiplying the three numbers on the faces that converge at that corner.

The Enterprise has flown around the Borg Cube — now Picard has the numbers from all sides of the Cube.

Help Picard: knowing the numbers on the sides of the Cube, calculate the sum of all the corner numbers.

Input

The first line contains 6 integers separated by spaces $$$v_1, \ldots, v_6$$$ $$$(1 \le v_i \le 500)$$$ — the numbers located on the top, bottom, left, right, front, and back sides of the Cube, respectively.

Output

In the first line, output a single integer $$$C$$$ $$$(1 \le C \le 10^9)$$$ — the code to access the Borg Cube.

Example
Input
1 2 3 4 4 5
Output
189
Note

First test example

The numbers at the corners of the cube are respectively:

  • top left front corner: $$$v_1 \cdot v_3 \cdot v_5 = 1 \cdot 3 \cdot 4 = 12$$$;
  • top left back corner: $$$v_1 \cdot v_3 \cdot v_6 = 1 \cdot 3 \cdot 5 = 15$$$;
  • top right front corner: $$$v_1 \cdot v_4 \cdot v_5 = 1 \cdot 4 \cdot 4 = 16$$$;
  • top right back corner: $$$v_1 \cdot v_4 \cdot v_6 = 1 \cdot 4 \cdot 5 = 20$$$;
  • bottom left front corner: $$$v_2 \cdot v_3 \cdot v_5 = 2 \cdot 3 \cdot 4 = 24$$$;
  • bottom left back corner: $$$v_2 \cdot v_3 \cdot v_6 = 2 \cdot 3 \cdot 5 = 30$$$;
  • bottom right front corner: $$$v_2 \cdot v_4 \cdot v_5 = 2 \cdot 4 \cdot 4 = 32$$$;
  • bottom right back corner: $$$v_2 \cdot v_4 \cdot v_6 = 2 \cdot 4 \cdot 5 = 40$$$.

The sum of all the corner numbers is $$$12 + 15 + 16 + 20 + 24 + 30 + 32 + 40 = 189$$$.

B. Nostalgia
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Aidar, Begimai, and Viktor came to the trial round of the championship.

They saw Scratch in the list of available compilers and remembered how they started learning programming with this language.

For example, during manual testing, it was often unclear what the program was waiting for in terms of input for a particular variable. Therefore, sometimes they would locally add output of the variable name before the input (but would remove it before submitting to the testing system).

The teammates even found several of their submissions on Scratch from those long-ago times in the system.

Now they are curious — how many total characters did they additionally output during local testing compared to the final submission to the system?

Input

The first line contains an integer $$$n$$$ $$$(2 \le n \le 10^5)$$$ — the number of lines in the Scratch program code.

The next $$$n$$$ lines contain one command of the analyzed program.

Commands can be one of the following types:

  • An input request in the format "Ask read_token and wait";
  • Storing the entered information in the variable name in the format "Set name to answer";
  • Assigning the variable name1 the result of the arithmetic operation op on the variables name2 and name3 in the format "Set name1 to name2 op name3";
  • Outputting the value of the variable name to the screen in the format Say name.

It is guaranteed that

  • all variable names consist only of lowercase Latin letters (a — z) and contain from $$$1$$$ to $$$10$$$ characters;
  • the source code does not contain variables named answer, which is reserved for inputting information into a variable.

It is guaranteed that op can only be one of the following symbols:

  • + — addition;
  • - — subtraction;
  • * — multiplication;
  • / — division.

It is guaranteed that

  • each input request is necessarily accompanied by storing the entered information in a variable;
  • each storage of entered information in a variable necessarily follows an input request.

It is guaranteed that all variables are used in the right side of arithmetic expressions only after their correct initialization.

Output

Output a single integer $$$P$$$ $$$(1 \le P \le 10^9)$$$ — the total number of characters that the teammates output additionally during local testing of this program.

Examples
Input
6
Ask read_token and wait
Set first to answer
Ask read_token and wait
Set second to answer
Set result to first + second
Say result
Output
11
Input
15
Ask read_token and wait
Set a to answer
Ask read_token and wait
Set bb to answer
Set ccc to a * bb
Set dddd to a / bb
Set dddd to ccc + dddd
Say dddd
Ask read_token and wait
Set bb to answer
Ask read_token and wait
Set ccc to answer
Set x to bb * dddd
Set x to ccc - x
Say x
Output
8
Note

First test example

In the program, two input operations are performed:

  • the variable first is entered once — $$$5$$$ additional characters for input;
  • the variable second is entered once — $$$6$$$ additional characters for input.

In total, the teammates output additionally exactly $$$5 + 6 = 11$$$ characters.

Second test example

In the program, four input operations are performed:

  • the variable a is entered once — $$$1$$$ character for input;
  • the variable bb is entered twice — $$$2$$$ characters for input;
  • the variable ccc is entered once — $$$3$$$ characters for input.

In total, the teammates output additionally exactly $$$1 + 2 \cdot 2 + 3 = 8$$$ characters.

C. You can't just take and divide
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Anatoly and Antitoly met on a forum about numerical injustice.

It turned out that besides their love for mathematics, they have many differences.

For example, Anatoly always strives for a fair distribution of resources and is not afraid of difficulties.

Antitoly, on the other hand, finds pleasure in the unfair distribution of resources and seeks simplicity in everything.

At the moment, Antitoly is developing his model of an ideal society, defined by the parameter $$$n$$$.

To complete his model, Antitoly needs to compute exactly one quantity — the number of integers $$$x$$$ in the range from $$$1$$$ to $$$n$$$ such that:

  • the number $$$x$$$ itself is odd (even numbers are too easy to divide in half, Antitoly does not like them);
  • the number of divisors of $$$x$$$ is odd and prime.
Input

The first line contains an integer odd number $$$n$$$ $$$(3 \le n \le 11^{13})$$$ — the parameter of the ideal society in Antitoly's model.

Output

Output a single integer $$$R$$$ $$$(0 \le R \le n)$$$ — the number of integers $$$x$$$ in the range from $$$1$$$ to $$$n$$$ such that:

  • the number $$$x$$$ itself is odd;
  • the number of divisors of $$$x$$$ is odd and prime.
Examples
Input
3
Output
0
Input
5
Output
0
Input
9
Output
1
Input
111
Output
4
Input
9753113579
Output
9563
Note

Definition A positive integer is called prime if it has exactly two distinct divisors.

For example, the numbers $$$3$$$, $$$17$$$, and $$$59$$$ are prime, while the numbers $$$1$$$ ($$$1$$$ divisor), $$$9$$$ ($$$3$$$ divisors), $$$30$$$ ($$$8$$$ divisors), and $$$111$$$ ($$$4$$$ divisors) are not prime.

First test example

Consider each of the numbers not exceeding $$$3$$$:

  • $$$1$$$ has $$$1$$$ divisor — the number of divisors is odd, but not prime.
  • $$$2$$$ has $$$2$$$ divisors — the number itself is even, so it is not of interest.
  • $$$3$$$ has $$$2$$$ divisors — the number of divisors is prime, but even.

Accordingly, there are no suitable numbers for Antitoly.

Second test example

Compared to the first test, two numbers are added:

  • $$$4$$$ has $$$3$$$ divisors — the number of divisors is odd and prime, but the number itself is even.
  • $$$5$$$ has $$$2$$$ divisors — the number of divisors is prime, but even.

So far, there are still no suitable numbers for Antitoly.

Third test example

Compared to the second test, four numbers are added:

  • $$$6$$$ and $$$8$$$ — even numbers, not of interest.
  • $$$7$$$ has $$$2$$$ divisors — the number of divisors is prime, but even.
  • $$$9$$$ has $$$3$$$ divisors — the number of divisors is both prime and odd.

D. Treasure
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice the Fox and Basil the Cat ran away from Pinocchio but left him a cube. They said that it has written on it where the treasure is buried. Of course, he believed them.

A digit was burned on each face of the cube.

Pinocchio was told that he needs to move along the faces of the cube, transitioning to a neighboring face each time and recording the digits that are drawn on them. He can enter each face only once.

The largest number that can be collected in this way will indicate where the treasure is buried. The first three digits represent steps to the north from the old mill, and the rest represent steps to the east.

Help Pinocchio find the largest number that can be obtained in the specified way. After all, he wants to check if what he was told is true.

Input

The first line contains $$$6$$$ integers $$$d_1, \ldots, d_6$$$ $$$(0 \le d_i \le 9)$$$ — the digits burned on the top, bottom, left, right, front, and back faces of the cube, respectively.

It is guaranteed that at least one of the digits $$$d_i$$$ is different from $$$0$$$.

Output

In the first line, output a single integer $$$X$$$ $$$(10^5 \le X \lt 10^6)$$$ — the largest number that can be obtained in the way described by Pinocchio.

Example
Input
2 3 1 4 5 6
Output
645312
Note

First test example

The maximum number $$$645312$$$ can be obtained by traversing the faces of the cube in the following order:

  • back;
  • right;
  • front;
  • bottom;
  • left;
  • top.

Note that the following numbers cannot be obtained:

  • $$$654312$$$ cannot be obtained, as you cannot move from the back face directly to the front;
  • $$$645321$$$ cannot be obtained, as you cannot move from the bottom face directly to the top.

E. Visualize This
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Aidar, Begimai, and Viktor wrote their first segment tree to solve a complex problem.

However, a problem arose — their tree was producing incorrect answers even for the test cases provided in the problem statement.

First of all, the guys assumed that they had incorrectly matched the semi-intervals of the array to the nodes. Viktor suggested that they should output all the nodes and their semi-intervals in order.

Begimai noted that simple line-by-line output would not significantly speed up the process — they needed to visualize the entire tree!

Attention: This problem uses certain rules for constructing a segment tree — familiarize yourself with them in the notes of the problem.

Input

The first line contains an integer $$$n$$$ $$$(1 \le n \le 10^4)$$$ — the size of the array.

Output

The tree must be visualized layer by layer, with each layer corresponding to one line.

  • The root of the tree is visualized in the first line.
  • Child nodes are placed one line below their parent node.
  • Each node is visualized as follows:
    • The semi-interval of the node is described in the format $$$[L;R)$$$.
    • In case $$$L + 1 \lt R$$$, strictly under the symbol ";" down to the very last line, there should be "|" symbols representing the separator between the left and right subtrees.
    • There must be a minimally possible number of spaces (at least one) between the line describing the node itself and any separator on the same line.
  • At least one output line must not start with a space.
  • The last character of each line must not be a space.

Refer to the test examples for clarification on the details.

Examples
Input
1
Output
[0;1)
Input
2
Output
    [0;2)
[0;1) | [1;2)
Input
3
Output
    [0;3)
[0;1) |     [1;3)
      | [1;2) | [2;3)
Input
7
Output
                    [0;7)
    [0;3)             |             [3;7)
[0;1) |     [1;3)     |     [3;5)     |     [5;7)
      | [1;2) | [2;3) | [3;4) | [4;5) | [5;6) | [6;7)
Input
9
Output
                            [0;9)
            [0;4)             |             [4;9)
    [0;2)     |     [2;4)     |     [4;6)     |     [6;9)
[0;1) | [1;2) | [2;3) | [3;4) | [4;5) | [5;6) | [6;7) |     [7;9)
      |       |       |       |       |       |       | [7;8) | [8;9)
Note

Definition

A segment tree built for an array of length $$$n$$$ represents a binary tree in which each node is matched to a certain semi-interval of the given array:

  • The root of the tree is matched to the entire array — the semi-interval $$$[0; n)$$$.
  • Each leaf (terminal node) of the tree is matched to a specific element of the array — the semi-interval $$$[i; i + 1)$$$.
  • The general rule for matching nodes and semi-intervals is as follows:
    • Let the non-terminal node $$$v$$$ be matched to the semi-interval $$$[L; R)$$$.
    • Let $$$M = \lfloor\frac{(L + R)}{2}\rfloor$$$ — the midpoint of the semi-interval.
    • In this case, the left child of this node is matched to the semi-interval $$$[L, M)$$$, and the right child is matched to the semi-interval $$$[M; R)$$$.

F. Sign Entanglement
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Pozislav and Minuslav met at a forum on the physics of integers.

It turned out that their research areas are very similar — Pozislav studies energy emissions of positive numbers, while Minuslav studies energy bursts of negative numbers.

The guys decided to combine their efforts and conduct a large-scale study of sign entanglement:

  • Suppose that at time $$$t_i$$$ there is an energy emission on the positive half-axis.
  • Suppose that at time $$$t_j$$$ there is an energy burst on the negative half-axis.
  • If $$$0 \lt |t_i - t_j| \le d$$$, then events $$$i$$$ and $$$j$$$ are considered entangled by sign.

The guys combined their records — now they need to find the number of pairs of events that are entangled by sign.

Input

The first line contains two integers $$$n$$$ and $$$d$$$ $$$(1 \le n \le 3 \cdot 10^5; 1 \le d \le 10^9)$$$ — the number of studied energy events and the maximum time difference for entanglement to exist.

The second line contains $$$n$$$ integers $$$t_i$$$ $$$(1 \le t_i \le 10^9)$$$ — the moment in time when the $$$i$$$-th event occurred.

The third line contains a string $$$S$$$ $$$(|S| = n)$$$ — the signs of the half-axes on which the events occurred:

  • if $$$S_i$$$ is +, then the $$$i$$$-th event occurred on the positive half-axis;
  • if $$$S_i$$$ is -, then the $$$i$$$-th event occurred on the negative half-axis.

It is guaranteed that the records are given in chronological order: $$$t_1 \le t_2 \le \ldots \le t_n$$$.

Output

Output a single integer $$$T$$$ $$$(0 \le T \le 10^{18})$$$ — the number of pairs of entangled events by sign.

Example
Input
14 3
1 1 3 3 3 3 5 5 6 6 6 8 9 11
+--+++--+++++-
Output
23
Note

First test example

Events on the positive axis occurred at times $$$[1, 3, 3, 3, 6, 6, 6, 8, 9]$$$. Events on the negative axis occurred at times $$$[1, 3, 5, 5, 11]$$$.

Let's enumerate the entangled pairs of events:

  • An event at time $$$1$$$ on the positive axis and an event at time $$$3$$$ on the negative axis —- $$$1$$$ pair.
  • An event at time $$$1$$$ on the negative axis and three events at time $$$3$$$ on the positive axis — a total of $$$3$$$ pairs.
  • An event at time $$$3$$$ on the negative axis and three events at time $$$6$$$ on the positive axis — a total of $$$3$$$ pairs.
  • Three events at time $$$3$$$ on the positive axis and two events at time $$$5$$$ on the negative axis — a total of $$$6$$$ pairs.
  • Two events at time $$$5$$$ on the negative axis and three events at time $$$6$$$ on the positive axis — a total of $$$6$$$ pairs.
  • Two events at time $$$5$$$ on the negative axis and an event at time $$$8$$$ on the positive axis — a total of $$$2$$$ pairs.
  • An event at time $$$8$$$ on the positive axis and an event at time $$$11$$$ on the negative axis — a total of $$$1$$$ pair.
  • An event at time $$$9$$$ on the positive axis and an event at time $$$11$$$ on the negative axis — a total of $$$1$$$ pair.

In total, we get $$$1 + 3 + 3 + 6 + 6 + 2 + 1 + 1 = 23$$$ pairs of entangled events.

G. Secret Words
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Sirin has moved to a parallel world, and the Fairy Patrol needs to go after him.

Snezka approached the old fireplace and noticed that a corner of some old scroll was sticking out from behind a brick. She carefully pulled it out and unfolded it. The parchment was filled with a continuous stream of incomprehensible letters and symbols, and next to it lay a small sheet with a list of mysterious words.

The girls realized that this was yet another cipher from Sirin. At the edge of the sheet was a note — "To those who want to reach the parallel world, you need to break the entire text into separate secret words from this list. Each word can be used any number of times, but nothing extra can be added. Note: the symbols "?" in the text replace any letters of the secret word."

Masha, glancing at the text that Snezka had retrieved, understood that this text could be broken down into words in many ways! How can one find out how many such ways exist? She realized that counting would be necessary. But it seems that the girls themselves cannot handle it — they need your help!

Help the girls from the Fairy Patrol catch up with Sirin — determine how many different ways there are to break the text from the parchment into secret words from the list.

Input

The first line contains an integer $$$n$$$ $$$(1 \le n \le 100)$$$ — the number of secret words.

Each of the following lines contains a string $$$W_i$$$ $$$(1 \le |W_i| \le 10)$$$ — the $$$i$$$-th secret word.

It is guaranteed that all words $$$W_i$$$ are unique, that is, for $$$i \ne j$$$, $$$W_i \ne W_j$$$.

The last line contains a string $$$T$$$ $$$(1 \le |T| \le 100)$$$ — the text from the parchment.

It is guaranteed that

  • each word $$$W_i$$$ consists only of lowercase Latin letters (a — z);
  • the text $$$T$$$ consists only of lowercase Latin letters (a — z) and the symbols "?", where each symbol "?" replaces exactly one arbitrary letter.
Output

Let $$$P$$$ be the number of ways to break the text from the parchment into secret words.

In a single line, output a single integer — the remainder of $$$P$$$ when divided by $$$M = 10^9 + 7$$$.

Examples
Input
7
a
b
c
d
ab
bc
cd
ab?d
Output
11
Input
2
a
b
??
Output
4
Note

First test example

Let's enumerate the possible ways to break the text:

  1. $$$[\texttt{a}, \texttt{b}, \texttt{a}, \texttt{d}]$$$;
  2. $$$[\texttt{a}, \texttt{b}, \texttt{b}, \texttt{d}]$$$;
  3. $$$[\texttt{a}, \texttt{b}, \texttt{c}, \texttt{d}]$$$;
  4. $$$[\texttt{a}, \texttt{b}, \texttt{d}, \texttt{d}]$$$;
  5. $$$[\texttt{ab}, \texttt{a}, \texttt{d}]$$$;
  6. $$$[\texttt{ab}, \texttt{b}, \texttt{d}]$$$;
  7. $$$[\texttt{ab}, \texttt{c}, \texttt{d}]$$$;
  8. $$$[\texttt{ab}, \texttt{d}, \texttt{d}]$$$;
  9. $$$[\texttt{a}, \texttt{bc}, \texttt{d}]$$$;
  10. $$$[\texttt{a}, \texttt{b}, \texttt{cd}]$$$;
  11. $$$[\texttt{ab}, \texttt{cd}]$$$.

Second test example

Let's enumerate the possible ways to break the text:

  1. $$$[\texttt{a}, \texttt{a}]$$$;
  2. $$$[\texttt{a}, \texttt{b}]$$$;
  3. $$$[\texttt{b}, \texttt{a}]$$$;
  4. $$$[\texttt{b}, \texttt{b}]$$$.

H. Nested Loops
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Begimai returned home after the competition — and she was greeted by her very happy younger sister Dinara.

Dinara said that she had been closely following the competition — and even came up with a way to solve a challenging problem!

The only thing Dinara was still unsure about was how efficient her proposed solution was. Therefore, Dinara prepared pseudocode of her solution for Begimai to evaluate.

Dinara's pseudocode consists of a combination of three types of operators:

  • The operation for followed by an integer $$$k$$$ indicates the start of a loop with $$$k$$$ iterations;
  • The operation end indicates the end of the loop defined by the nearest unfinished for operator;
  • The operation calc followed by an integer $$$k$$$ indicates calculations performed in total over $$$k$$$ operations.

Now Begimai must determine the total number of operations performed by this solution and draw a conclusion about its efficiency.

Begimai immediately saw that the final total number of operations was simply enormous — and to avoid upsetting her sister too much, she decided to tell her the remainder of this number when divided by $$$10^9 + 7$$$.

Input

The first line contains an integer $$$n$$$ $$$(1 \le n \le 10^5)$$$ — the number of lines in the pseudocode of the solution.

Each of the following $$$n$$$ lines contains one of three operators:

  • A space-separated string for and an integer $$$k$$$ $$$(1 \le k \le 10^9)$$$ — the start of a loop with $$$k$$$ iterations;
  • A string end — the end of the loop defined by the nearest unfinished for operator;
  • A space-separated string calc and an integer $$$k$$$ $$$(1 \le k \le 10^9)$$$ — calculations performed in total over $$$k$$$ operations.

It is guaranteed that

  • each end operator corresponds to some for operator in one of the previous lines;
  • each for operator has a corresponding end operator in one of the subsequent lines;
  • each pair of for — end contains at least one nested operator.
Output

Let $$$T$$$ be the total number of operations performed by the described solution.

In this case, output a single integer — the remainder of $$$T$$$ when divided by $$$10^9 + 7$$$.

Examples
Input
13
for 10
for 300
calc 5
end
for 40
calc 7
calc 4
end
end
calc 45
for 3
calc 123
end
Output
19814
Input
7
for 2000
for 1000
for 3000
calc 4000
end
end
end
Output
999832007
Note

First test example

Decomposing the presented pseudocode:

  • In lines $$$2$$$ — $$$4$$$, $$$300 \cdot 5 = 1500$$$ operations are performed;
  • In lines $$$5$$$ — $$$8$$$, $$$40 \cdot (7 + 4) = 440$$$ operations are performed;
  • In lines $$$1$$$ — $$$9$$$, $$$10 \cdot (1500 + 440) = 19400$$$ operations are performed;
  • In line $$$10$$$, $$$45$$$ operations are performed;
  • In lines $$$11$$$ — $$$13$$$, $$$3 \cdot 123 = 369$$$ operations are performed.

In total, $$$T = 19400 + 45 + 369 = 19814$$$ operations.

Second test example

In total, this solution performs $$$T = 2000 \cdot 1000 \cdot 3000 \cdot 4000 = 24 \cdot 10^{12}$$$ operations.

It is necessary to output the remainder of $$$T$$$ when divided by $$$10^9 + 7$$$, which equals $$$999832007$$$.

I. Cutting Trees
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

While sitting on a call about live coding on the topic of "trees", two programmers from "Kanda Software" started playing a game on paper — drawing trees. Naturally, not green ones with leaves, but graphs.

They started with a tree consisting of a single vertex numbered $$$1$$$. Then they added a vertex numbered $$$2$$$ and connected them with an edge, resulting in the second tree, and they named vertex number $$$2$$$ its root.

Then they agreed that each subsequent $$$n$$$-th tree would be constructed from the $$$(n - 1)$$$-th tree using the following procedure:

  • In the $$$(n - 1)$$$-th tree, a path is constructed from the root of the tree to some leaf such that at each step, a child vertex with the highest number is chosen;
  • All edges belonging to the constructed path are removed;
  • All vertices belonging to the constructed path are connected, each with one edge to a new vertex numbered $$$n$$$;
  • The vertex numbered $$$n$$$ becomes the root of the $$$n$$$-th tree.

After several trees, they ran out of space on the paper, and they decided to stop drawing and start counting, posing problems to each other to compute characteristics of their sequence of trees.

One would think of two numbers, $$$n$$$ and $$$v$$$, and the other had to calculate the sum of the vertex numbers on the shortest path from the root of the $$$n$$$-th tree to vertex $$$v$$$ (including both the starting and ending vertices).

At this point, Slava noticed their game and suggested that for better understanding of the material, they compute the required sum for sufficiently large values of $$$n$$$. Naturally, performing such complex calculations on paper is impossible. Help them do this.

Input

The first line contains two integers $$$n$$$ and $$$v$$$ $$$(1 \le v \le n \le 10^{18})$$$ — the number of the tree and the number of the vertex in the tree, respectively.

Output

In a single line, output the integer $$$S$$$ – the sum of the vertex numbers on the shortest path from the root of the $$$n$$$-th tree to vertex $$$v$$$ (including both the starting and ending vertices).

It is guaranteed that $$$S$$$ does not exceed $$$9 \cdot 10^{18}$$$.

Examples
Input
2 1
Output
3
Input
3 2
Output
5
Input
6 1
Output
12
Input
9 6
Output
23
Note

The $$$2$$$-nd and $$$3$$$-rd trees, respectively.

The $$$6$$$-th and $$$9$$$-th trees, respectively.

First test example

The sum of the vertex numbers on the path is $$$2 + 1 = 3$$$.

Second test example

The sum of the vertex numbers on the path is $$$3 + 2 = 5$$$.

Third test example

The sum of the vertex numbers on the path is $$$6 + 5 + 1 = 12$$$.

Fourth test example

The sum of the vertex numbers on the path is $$$9 + 8 + 6 = 23$$$.

J. Laser Balancing
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In a certain laboratory, $$$n$$$ lasers are suspended from the ceiling. Initially, each laser is suspended at a distance of $$$a_i$$$ from the ceiling. All lasers hang in the same plane, and each has its own unique coordinate $$$x_i = i$$$.

At the other end of the room is a screen. All lasers emit light towards the screen, so if $$$2$$$ lasers hang at the same height, the light from the laser with the smaller coordinate does not reach the screen.

You can take any laser and increase its distance from the ceiling by $$$1$$$ no more than $$$k$$$ times. You are interested in determining the maximum number of lasers whose light will be registered by the screen with optimal use of the operations.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains $$$2$$$ integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 2 \cdot 10^5, 1 \leq k \leq 10^9$$$) — the total number of lasers and the number of operations, respectively.

The second line of each test case contains $$$n$$$ integers $$$a_i$$$ ($$$1 \leq a_i \leq 10^9$$$) separated by spaces — the initial distances of the lasers from the ceiling.

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output a single integer on a single line — the maximum number of lasers whose light reaches the screen after applying no more than $$$k$$$ operations.

Example
Input
3
4 4
1 2 3 4
4 5
1 1 1 1
9 2
4 3 3 10 5 5 5 99 11
Output
4
3
7
Note

First test case

All lasers are already at different heights, so they do not block each other's light.

Second test case

Initially, all lasers are at the same height, so only the light from the $$$4$$$-th laser reaches the screen.

You can increase the distance for the $$$2$$$-nd laser by $$$1$$$ and the distance for the $$$3$$$-rd laser by $$$2$$$ — in this case, the lasers will be at distances $$$[1, 2, 3, 1]$$$.

A total of $$$3$$$ operations will be performed (out of $$$5$$$ available), and the light from $$$3$$$ lasers reaches the screen.

Note that with the $$$5$$$ available operations, it is impossible to make all $$$4$$$ lasers hang at different heights.

Third test case

One of the lasers at a distance of $$$5$$$ can be moved to $$$1$$$ — in this case, the light from $$$7$$$ different lasers will reach the screen.

Note that the distance from the ceiling cannot be decreased — you cannot move one of the lasers at a distance of $$$3$$$ to $$$1$$$ closer to the ceiling (so that its new distance equals $$$2$$$).