“壹零杯”第三届西华师范大学程序设计竞赛
A. Ruins Supply
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Explorer Little A discovered $$$N$$$ ancient supply boxes arranged in a row in the outer corridor of the Astra ruins. After being scanned by the detector, Little A learned that the $$$i$$$-th supply box contained $$$A_i$$$ points of starlight energy.

However, the energy in some of the supply boxes has become extremely weak, and they might even have been contaminated by dark matter. The portable energy absorber of Little A has a safety threshold of $$$X$$$. To ensure safety, Little A only activates those supply boxes whose energy values are strictly greater than $$$X$$$, and absorbs all the energy within them; for supply boxes with energy values less than or equal to $$$X$$$, he simply skips them.

Could you please calculate for Little A how many starlight energy points he can collect in total?

Input

The first line contains two integers, $$$N$$$ and $$$X$$$ ($$$1 \le N \le 10^5$$$, $$$0 \le X \le 10^9$$$), representing the number of supply boxes and the safety threshold of the detector respectively.

The second line contains $$$N$$$ integers $$$A_1, A_2, \dots, A_N$$$ ($$$0 \le A_i \le 10^9$$$), representing the energy values in each supply box.

Output

Output an integer to represent the total energy that Little A has collected in the end.

Example
Input
5 10
5 12 10 20 1
Output
32
Note

The threshold $$$X = 10$$$.

The energy levels of the supply boxes are $$$5, 12, 10, 20, 1$$$.

Only $$$12$$$ and $$$20$$$ are strictly greater than $$$10$$$. Therefore, the total energy collected is $$$12 + 20 = 32$$$.

B. Astra's Gate
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
The dust of history obscures the truth, but inscriptions never lie...

Explorer Little A has finally arrived at the main structure of the Astra ruins—the "Gate of Astra". The heavy doors are tightly shut, and an ancient inscription consisting of uppercase English letters is carved on them.

According to the first rule of the $$$\textit{China West Normal University (CWNU) Explorer's Survival Guide}$$$: If the inscription on a door contains the contiguous substring $$$\mathtt{CWNU}$$$, then behind the door is a safe supply room; otherwise, there is a deadly dark matter trap!

Now, Little A has transcribed the inscription from the door. Since he is too nervous and his palms are sweating, please help him write a program to determine whether this door is safe or not.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.

For each test case:

There is a single line containing a string $$$S$$$ ($$$1 \le |S| \le 100$$$) consisting only of uppercase English letters, representing the inscription on the door.

Output

For each test case:

If it is safe behind the door (i.e., the string contains the contiguous substring $$$\mathtt{CWNU})$$$, output $$$\mathtt{SAFE}$$$ on a new line.

Otherwise, output $$$\mathtt{TRAP}$$$.

Example
Input
4
CWNUCPC
HELLOCWNU
ASTRARUINS
CWNUC
Output
SAFE
SAFE
TRAP
SAFE

C. Global Resupply
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Logistics is the lifeblood of war...

In a vast strategic buffer zone, there are $$$n$$$ frontline outposts, indexed from $$$1$$$ to $$$n$$$. Due to the intensity of the battle, the headquarters commands that every single outpost must receive supplies.

As the logistics commander, you have two methods to provide supplies to the outposts:

  1. Direct Airdrop: You can choose to establish an airdrop station at any outpost $$$i$$$. The cost to airdrop supplies to outpost $$$i$$$ is $$$a_i$$$. Once an airdrop station is established, that outpost is considered supplied.

  2. Land Transport: There are $$$m$$$ potential bidirectional supply roads. The $$$j$$$-th road connects outpost $$$u_j$$$ and outpost $$$v_j$$$ with a construction cost of $$$w_j$$$. If a road is built between two outposts, and one of them is already supplied (either via airdrop or transport from another outpost), the other outpost also becomes supplied.

Your goal is to formulate a plan with the minimum total cost such that all $$$n$$$ outposts are supplied.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 2 \times 10^5$$$, $$$0 \le m \le 2 \times 10^5$$$), representing the number of outposts and the number of potential roads.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), where $$$a_i$$$ denotes the cost of directly airdropping supplies to the $$$i$$$-th outpost.

The following $$$m$$$ lines each contain three integers $$$u, v, w$$$ ($$$1 \le u, v \le n$$$, $$$1 \le w \le 10^9$$$), representing a potential bidirectional road between outpost $$$u$$$ and outpost $$$v$$$ with a cost of $$$w$$$.

Note: The input may contain self-loops or multiple edges between the same pair of outposts.

Output

Output a single integer representing the minimum total cost required to supply all outposts.

Example
Input
3 2
5 10 3
1 2 1
2 3 2
Output
6
Note

In the sample case, the optimal strategy is:

  1. Establish an airdrop station at Outpost 3 (Cost: $$$3$$$). Outpost 3 is now supplied.
  2. Build the road between Outpost 3 and Outpost 2 (Cost: $$$2$$$). Supplies are transported from 3 to 2. Outpost 2 is now supplied.
  3. Build the road between Outpost 2 and Outpost 1 (Cost: $$$1$$$). Supplies are transported from 2 to 1. Outpost 1 is now supplied.
The total cost is $$$3 + 2 + 1 = 6$$$.

D. Bullfighting
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
"I want to check the cards..."
— A mysterious gambler with a French accent.

Alice is playing a card game called Bullfighting.

The game is played with a standard deck of cards, but only ranks A through 10 are kept. The point value of each card is defined as follows:

  • A counts as $$$1$$$ point.
  • Number cards 2 through 10 count as their face value (e.g., a 7 counts as $$$7$$$ points).

In each round, Alice is dealt $$$5$$$ cards. She must arrange these $$$5$$$ cards into two groups to determine her hand's power:

  1. Group 1: Consists of exactly $$$3$$$ cards.
  2. Group 2: Consists of the remaining $$$2$$$ cards.

The rank of the hand is determined by the following rules:

  1. Condition (Has Bull): If the sum of the points in Group 1 is a multiple of $$$10$$$, the hand is considered to "Have Bull". Otherwise, the hand is ranked as No Bull.
  2. Bull Rank: If the hand has a Bull, the rank is determined by the sum of points in Group 2. Let $$$S$$$ be the sum of the two cards in Group 2.
    • If $$$S$$$ is also a multiple of $$$10$$$, the rank is Bull Bull (the highest rank).
    • Otherwise, the rank is Bull $$$X$$$, where $$$X$$$ is the remainder of $$$S$$$ divided by $$$10$$$ (i.e., $$$X = S \bmod 10$$$).

The ranks are ordered as follows: $$$$$$ \text{No Bull} \lt \text{Bull } 1 \lt \text{Bull } 2 \lt \dots \lt \text{Bull } 9 \lt \text{Bull Bull} $$$$$$

Given 5 cards, please help Alice find the highest rank she can achieve by arranging them optimally.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 100$$$), representing the number of test cases.

Each test case consists of a single line containing $$$5$$$ integers $$$c_1, c_2, c_3, c_4, c_5$$$ ($$$1 \le c_i \le 10$$$), representing the point values of the $$$5$$$ cards Alice holds.

It is guaranteed that the cards are drawn from a single standard deck, meaning that for any rank $$$k \in [1, 10]$$$, it appears at most $$$4$$$ times in a hand.

Output

For each test case, output the highest rank Alice can obtain in a single line. The output must be one of the following strings:

  • No Bull
  • Bull 1, Bull 2, ..., Bull 9
  • Bull Bull
Example
Input
3
1 2 3 4 5
10 10 10 5 5
1 2 3 4 8
Output
Bull 5
Bull Bull
No Bull
Note

For the first case (1 2 3 4 5):

  • We choose Group 1 as $$$\{1, 4, 5\}$$$. The sum is $$$1+4+5=10$$$, which is a multiple of $$$10$$$.
  • Group 2 is $$$\{2, 3\}$$$. The sum is $$$2+3=5$$$.
  • Since $$$5 \bmod 10 = 5$$$, the rank is Bull 5.

For the second case (10 10 10 5 5):

  • We choose Group 1 as $$$\{10, 10, 10\}$$$. The sum is $$$30$$$ (multiple of $$$10$$$).
  • Group 2 is $$$\{5, 5\}$$$. The sum is $$$10$$$.
  • Since $$$10$$$ is a multiple of $$$10$$$, the rank is Bull Bull.

E. Dark Matter Crisis
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
The price of greed is awakening the nightmares slumbering in the abyss...

Explorer Little A has collected too many crystals in the Astra ruins, accidentally triggering the ancient self-destruct mechanism! The dark matter containers deep within the ruins have ruptured, and terrifying dark matter is beginning to spread outward.

The ruins can be viewed as an $$$N \times M$$$ 2D grid. The grid contains the following elements:

  • $$$\mathtt{A}$$$: Little A's current position (exactly one).
  • $$$\mathtt{E}$$$: The exit door of the ruins (exactly one).
  • $$$\mathtt{*}$$$: The source of ruptured dark matter (there may be none, or multiple).
  • $$$\mathtt{\#}$$$: Solid stone walls, which neither Little A nor the dark matter can pass through.
  • $$$\mathtt{.}$$$: Empty space.

Every $$$1$$$ second that passes, Little A can move to one adjacent cell in the four cardinal directions (up, down, left, right); simultaneously, each dark matter source will also spread to an adjacent cell in the four directions.

Extremely dangerous: Dark matter has the characteristic of instantaneous devouring. Little A must guarantee that at the exact moment he arrives at a certain cell, the dark matter has not yet spread to that cell. In other words, the time Little A takes to reach a cell must be strictly less than the time it takes for the dark matter to reach that cell. If the dark matter and Little A arrive at a cell at the exact same time, Little A will also be devoured!

Please help Little A calculate whether he can make it out alive to the exit door $$$\mathtt{E}$$$. If so, what is the minimum time (in seconds) required.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.

For each test case: The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \le N, M \le 1000$$$) — the number of rows and columns of the ruins grid.

The next $$$N$$$ lines each contain a string of length $$$M$$$, representing the map of the ruins. The characters in the string will only be $$$\mathtt{A}$$$, $$$\mathtt{E}$$$, $$$\mathtt{*}$$$, $$$\mathtt{\#}$$$, or $$$\mathtt{.}$$$.

It is guaranteed that the map contains exactly one $$$\mathtt{A}$$$ and exactly one $$$\mathtt{E}$$$.

It is guaranteed that the sum of $$$N \times M$$$ over all test cases does not exceed $$$2 \times 10^6$$$.

Output

For each test case, output a single integer on a new line.

If Little A can safely reach the exit, output the minimum time (in seconds) required.

If Little A will inevitably be devoured by dark matter, or if it is impossible to reach the exit at all, output $$$\mathtt{-1}$$$.

Example
Input
3
4 5
A....
..#..
..#..
*.#.E
4 4
A..*
....
....
...E
3 3
A#.
#.#
.*E
Output
7
-1
-1
Note

In the first example:

Little A is located at the top-left corner $$$(1, 1)$$$, the exit is at the bottom-right corner $$$(4, 5)$$$, and the dark matter source is at the bottom-left corner $$$(4, 1)$$$.

Little A's optimal route is to move right first and bypass the walls in the middle to reach the exit. Although the dark matter is spreading, Little A is fast enough to safely reach the exit at the $$$7$$$-th second.

In the second example:

The grid size is $$$4 \times 4$$$. Little A starts from the top-left corner, and the dark matter spreads from the top-right corner. Since the exit is at the bottom-right corner, no matter how Little A moves, the dark matter will arrive at the inevitable path near the exit before or at the same time as him. Little A is bound to be devoured, so the output is $$$-1$$$.

In the third example:

Little A is completely sealed in the top-left corner by walls. There is absolutely no path to the exit, so the output is directly $$$-1$$$.

F. Dark Matter Purification
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Deep within the ancient ruins of Astra, young explorer A discovered a core matrix severely eroded by dark matter. This matrix can be regarded as a row of $$$n$$$ energy nodes, numbered from 1 to $$$n$$$.

The defense system of the ruins is attempting to purify these nodes. Due to the damage to the system, it can only perform random purification operations. Specifically, in every second, the defense system will randomly select one interval (with equal probability) from all possible consecutive subintervals $$$[L, R]$$$ ($$$1 \le L \le R \le n$$$) and release a beam of purification light, purifying all the nodes within that interval once. There are a total of $$$\frac{n(n+1)}{2}$$$ possible choices.

Please note that it is permitted and harmless for the same node to be purified multiple times.

Little A wants to know: starting from the moment the defense system is activated, until all $$$n$$$ nodes have been purified at least once, what is the average number of seconds required?

Since the expected value might be a fraction, please output the result of this fraction modulo $$$10^9 + 7$$$. Specifically, if the simplest fraction for the expected value is $$$\frac{P}{Q}$$$, you need to output an integer $$$X$$$ such that $$$X \cdot Q \equiv P \pmod{10^9 + 7}$$$ and $$$0 \le X \lt 10^9 + 7$$$.

Input

The input consists of only one line with a single integer $$$n$$$ ($$$1 \le n \le 100$$$), representing the number of energy nodes.

Output

Output an integer representing the result of the expected seconds modulo $$$10^9 + 7$$$.

Examples
Input
1
Output
1
Input
2
Output
2
Input
3
Output
300000005
Note

For the case where $$$n=2$$$, all possible intervals are $$$[1, 1], [2, 2], [1, 2]$$$, totaling $$$3$$$ types. Each type has a probability of $$$\frac{1}{3}$$$ of being selected.

  • If $$$[1, 2]$$$ is selected in the first second, both nodes will be purified, and it will take 1 second.
  • If $$$[1, 1]$$$ is selected in the first second, then we need to wait for the selection of the interval containing node 2 (i.e., $$$[2, 2]$$$ or $$$[1, 2]$$$). After that, each time there is a $$$\frac{2}{3}$$$ probability of selecting the target interval, and the expected additional time is $$$\frac{3}{2} = 1.5$$$ seconds. Thus, the total expected time is $$$1 + 1.5 = 2.5$$$ seconds.
  • If $$$[2, 2]$$$ is selected in the first second, similarly, the total expected time is 2.5 seconds.

Overall, the total expected time is $$$\frac{1}{3} \times 1 + \frac{1}{3} \times 2.5 + \frac{1}{3} \times 2.5 = 2$$$ seconds.

For the case where $$$n=3$$$, the actual expected number of seconds for purifying all nodes is $$$\frac{29}{10}$$$, which is equivalent to $$$300000005$$$ modulo $$$10^9 + 7$$$.

G. Ruined steps
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Explorer Little A arrived at the prayer hall of the Astra ruins. The hall was built at a high location, and Little A needed to climb an ancient stone staircase consisting of $$$N$$$ steps. The step numbers ranged from $$$1$$$ to $$$N$$$. Little A started from the ground (which could be regarded as the $$$0$$$th step).

Little A has excellent physical fitness. Each time, he can choose to jump up across either one or two steps. However, due to the passage of time, some $$$M$$$-level steps have completely broken apart. Little A must not step on these broken steps.

Could you please calculate for Little A how many different ways there are for him to safely reach the $$$N$$$th step?

Input

The first line contains two integers, $$$N$$$ and $$$M$$$ ($$$1 \le N \le 50$$$, $$$0 \le M \le N$$$), representing the total number of steps and the number of broken steps respectively. The second line contains $$$M$$$ integers $$$b_1, b_2, \dots, b_M$$$ ($$$1 \le b_i \le N$$$), representing the numbers of the broken steps. It is guaranteed that these $$$M$$$ numbers are all distinct and are given in ascending order.

Output

Output a single integer, representing the number of different ways to reach the $$$N$$$-th step.

Examples
Input
4 1
2
Output
1
Input
5 0
Output
8
Input
3 3
1 2 3
Output
0
Note

If $$$N=4$$$ and $$$M=1$$$, the broken step is the second step.

Little A cannot step on the second level. The only legal way to proceed is: $$$0 \rightarrow 1 \rightarrow 3 \rightarrow 4$$$.

H. Astra's Vanguard
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Mechas are the blades for exploring the ruins, and the pilots are their souls...

Deep within the Astra ruins, Little A has discovered the core energy sources of $$$K$$$ ancient mechas. The energy value of the $$$j$$$-th core is $$$E_j$$$. Meanwhile, there are $$$N$$$ candidate pilots in Little A's expedition team. Each pilot has the following four attributes:

  1. Name: A string consisting of uppercase and lowercase English letters.
  2. Sync Rate ($$$S$$$): Determines the priority to match with a mecha.
  3. Agility ($$$A$$$): The secondary assessment metric when sync rates are equal.
  4. Combat Power ($$$C$$$): Determines the destructive power when piloting a mecha.

Since there are only $$$K$$$ mechas, Little A must strictly select $$$K$$$ elites from the $$$N$$$ candidate pilots. The selection sorting rules are as follows:

  1. Prioritize pilots with a higher Sync Rate ($$$S$$$).
  2. If Sync Rates are equal, prioritize pilots with higher Agility ($$$A$$$).
  3. If the first two attributes are identical, prioritize pilots whose Names have a smaller lexicographical order.
(It is guaranteed that no two pilots have the exact same name).

After selecting these $$$K$$$ elites, Little A needs to pair them one-to-one with the $$$K$$$ energy cores. When a pilot with Combat Power $$$C_i$$$ is assigned an energy core with energy value $$$E_j$$$, the combat effectiveness generated is $$$C_i \times E_j$$$.

Little A can freely decide the assignment of energy cores among the $$$K$$$ selected pilots. Please calculate the maximum total combat effectiveness the entire vanguard team can generate.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10$$$) — the number of test cases.

For each test case: The first line contains two integers $$$N$$$ and $$$K$$$ ($$$1 \le K \le N \le 10^5$$$) — the number of candidate pilots and the number of mecha cores.

The next $$$N$$$ lines describe the pilots. The $$$i$$$-th line contains a string $$$Name_i$$$ ($$$1 \le |Name_i| \le 10$$$) and three integers $$$S_i, A_i, C_i$$$ ($$$1 \le S_i, A_i, C_i \le 10^5$$$). It is guaranteed that the names consist only of English letters and are pairwise distinct within the same test case.

The following line contains $$$K$$$ integers $$$E_1, E_2, \dots, E_K$$$ ($$$1 \le E_j \le 10^5$$$) — the energy values of the cores.

It is guaranteed that the sum of $$$N$$$ over all test cases does not exceed $$$2 \times 10^5$$$.

Output

For each test case, output a single integer on a new line, representing the maximum total combat effectiveness.

Example
Input
2
3 2
Alice 10 20 50
Bob 10 20 40
Charlie 15 10 30
10 20
4 3
David 100 100 10
Eve 100 100 100
Frank 100 90 500
Grace 90 200 1000
5 2 10
Output
1300
5520

I. Matrix Reconstruction
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Deep within the ruins, you need to reconstruct a square energy matrix of size $$$n \times n$$$.

You have exactly $$$n^2$$$ energy crystals, with energy levels ranging from 1 to $$$n^2$$$. You must place all $$$n^2$$$ crystals into the matrix, such that each cell contains exactly one crystal.

To prevent dangerous resonance explosions between the crystals, an ancient rule states: The absolute difference in energy levels between any two adjacent crystals (sharing an edge, either horizontally or vertically) must be strictly greater than 1.

Formally, for any two adjacent elements $$$x$$$ and $$$y$$$ in the matrix, $$$|x - y| \gt 1$$$ must hold.

Please construct a valid placement for the matrix. If no such placement exists, output -1.

Input

The first line contains a single integer $$$t$$$ (1 $$$\le t \le$$$ 100) — the number of test cases.

For each test case, the only line contains a single integer $$$n$$$ (1 $$$\le n \le$$$ 100) — the size of the matrix.

Output

For each test case:

  • If it is impossible to construct a valid matrix, output -1 on a single line.
  • Otherwise, output $$$n$$$ lines, each containing $$$n$$$ integers separated by a space, representing your constructed matrix. If there are multiple valid solutions, you may output any of them.
Example
Input
3
1
2
3
Output
1
-1
1 8 6
4 2 9
7 5 3

J. 2048 Simulator
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
In this world composed of digits, merging is the only way to evolve...
Figure 1: An example of 2048 game grid

You are given an $$$N \times N$$$ grid. Each cell in the grid contains either a positive integer of the form $$$2^k\ (k \ge 1)$$$ or $$$0$$$ (representing an empty space).

You need to process an operation string $$$S$$$ of length $$$M$$$, consisting of characters L (Left), R (Right), U (Up), and D (Down). For each character in $$$S$$$, you must slide the numbers in the grid according to the rules of the game 2048.

The rules for sliding and merging are as follows:

  1. Slide: All numbers slide in the direction of the instruction until they hit the border or another non-zero number. (e.g., $$$[0, 2, 0, 2]$$$ moving Left becomes $$$[2, 2, 0, 0]$$$ before merging).
  2. Merge: If two adjacent numbers (with no other non-zero numbers between them) in the sliding direction have the same value, they merge into a new number with twice the value.
  3. Priority:
    • Single Merge Rule: In a single move, each tile (including those created by a merge) can participate in at most one merge.
    • Directional Priority: Merges always happen from the front of the sliding direction.
    • Example: If a row is $$$[2, 2, 2, 2]$$$ and moves Left (L), the leftmost two 2 merge first, then the remaining two 2 merge. The result is $$$[4, 4, 0, 0]$$$. It is not $$$[8, 0, 0, 0]$$$ nor $$$[4, 2, 2, 0]$$$.
    • Example: If a row is $$$[4, 2, 2, 0]$$$ and moves Left (L), the result is $$$[4, 4, 0, 0]$$$.

Note: Unlike the original game, new tiles are not generated in empty spots after a move.

Input

The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \le N \le 20, 1 \le M \le 100$$$), representing the size of the grid and the length of the operation string.

The next $$$N$$$ lines each contain $$$N$$$ integers $$$A_{i,j}$$$ ($$$0 \le A_{i,j} \le 1024$$$), representing the initial state of the grid. It is guaranteed that all non-zero integers are powers of 2.

The last line contains a string $$$S$$$ of length $$$M$$$, consisting only of the characters L, R, U, and D.

Output

Output $$$N$$$ lines, each containing $$$N$$$ integers, representing the final state of the grid after all operations.

Example
Input
4 4
2 2 2 2
4 2 2 0
0 4 2 2
8 0 0 8
LRLU
Output
16 0 0 0
8 0 0 0
16 0 0 0
0 0 0 0
Note

Visual explanation of the sample case:

Let the state of the grid be denoted by matrices. The transitions are as follows:

$$$$$$ \underbrace{ \begin{pmatrix} 2 & 2 & 2 & 2 \\ 4 & 2 & 2 & 0 \\ 0 & 4 & 2 & 2 \\ 8 & 0 & 0 & 8 \end{pmatrix} }_{\text{Initial State}} \xrightarrow{(1)\ \textbf{L}} \underbrace{ \begin{pmatrix} 4 & 4 & 0 & 0 \\ 4 & 4 & 0 & 0 \\ 4 & 4 & 0 & 0 \\ 16 & 0 & 0 & 0 \end{pmatrix} }_{\text{After L}} \xrightarrow{(2)\ \textbf{R}} \underbrace{ \begin{pmatrix} 0 & 0 & 0 & 8 \\ 0 & 0 & 0 & 8 \\ 0 & 0 & 0 & 8 \\ 0 & 0 & 0 & 16 \end{pmatrix} }_{\text{After R}} $$$$$$

$$$$$$ \xrightarrow{(3)\ \textbf{L}} \underbrace{ \begin{pmatrix} 8 & 0 & 0 & 0 \\ 8 & 0 & 0 & 0 \\ 8 & 0 & 0 & 0 \\ 16 & 0 & 0 & 0 \end{pmatrix} }_{\text{After L}} \xrightarrow{(4)\ \textbf{U}} \underbrace{ \begin{pmatrix} 16 & 0 & 0 & 0 \\ 8 & 0 & 0 & 0 \\ 16 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix} }_{\text{Final State}} $$$$$$

Transition Details:

  1. Operation L (Left):
    • Row 1 ($$$[2, 2, 2, 2]$$$): The first two $$$2$$$s merge into $$$4$$$. The next two $$$2$$$s merge into $$$4$$$. Result: $$$[4, 4, 0, 0]$$$.
    • Row 4 ($$$[8, 0, 0, 8]$$$): The zeros are skipped, and the two $$$8$$$s merge. Result: $$$[16, 0, 0, 0]$$$.

  2. Operation R (Right):
    • Row 1 ($$$[4, 4, 0, 0]$$$): They slide to the right. Since they are equal, they merge into $$$8$$$. Result: $$$[0, 0, 0, 8]$$$.
    • Same applies to Rows 2 and 3.

  3. Operation L (Left):
    • All numbers slide back to the left. No merges are possible since each row contains only a single number.

  4. Operation U (Up):
    • Column 1 ($$$[8, 8, 8, 16]^T$$$):
      • The top two $$$8$$$s merge into $$$16$$$.
      • The third $$$8$$$ slides up (cannot merge with the new $$$16$$$ due to the Single Merge Rule).
      • The bottom $$$16$$$ slides up.
    • Result for Col 1: $$$[16, 8, 16, 0]^T$$$.

K. Starlight Blend
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the alchemy chamber of the Astra ruins, Little A found $$$N$$$ starlight crystal stones. The energy value of the $$$i$$$-th crystal stone is $$$A_i$$$.

According to the ancient alchemy rule, only by combining a crystal with an odd energy value and a crystal with an even energy value can a perfect and stable 'Starlight Core' be synthesized.

Each crystal stone can only be fused once (meaning it is consumed once it is used).

Little A hopes to synthesize as many 'Starlight Core' as possible. Please help him calculate how many Starlight Cores can be synthesized with these $$$N$$$ gemstones?

Input

The first line contains an integer $$$N$$$ ($$$1 \le N \le 5 \times 10^5$$$), representing the number of gemstones.

The second line contains $$$N$$$ integers $$$A_1, A_2, \dots, A_N$$$ ($$$1 \le A_i \le 10^9$$$), representing the energy values of each crystal stone

Output

Output a single integer, indicating the maximum number of starlight cores that can be synthesized.

Examples
Input
5
1 2 3 4 5
Output
2
Input
4
2 4 6 8
Output
0
Note

For example 1

If you have 5 crystals at hand, their energies are 1, 2, 3, 4, and 5.

The odd numbers are $$$1, 3, 5$$$, and the even numbers are $$$2, 4$$$.

The points $$$(1, 2)$$$ and $$$(3, 4)$$$ can be combined. The remaining 5 cannot be paired with even crystal stones. At most, 2 cores can be synthesized.

L. The Vault of Stars
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
The mysteries of the universe have long been engraved in the alignment of the stars...

After enduring countless hardships, explorer Little A has finally stepped into the ultimate region of the Astra ruins—the Vault of Stars.

Suspended in the center of the vault are $$$S$$$ pure starlight crystals, surrounded by $$$N$$$ ancient array pillars of various shapes. To completely stabilize the energy field of the ruins, Little A must distribute all $$$S$$$ crystals into these $$$N$$$ pillars.

Every pillar has a limit to the energy it can withstand. Specifically, the $$$i$$$-th pillar can hold at most $$$L_i$$$ crystals. Of course, Little A can also choose not to place any crystals in certain pillars (i.e., the allocated amount is 0).

Little A wants to know: how many different distribution plans can successfully allocate all $$$S$$$ crystals while satisfying the capacity limits of all pillars?

Since the number of valid plans might be extremely large, you only need to output the answer modulo $$$10^9+7$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10$$$) — the number of test cases.

For each test case: The first line contains two integers $$$N$$$ and $$$S$$$ ($$$1 \le N \le 15$$$, $$$1 \le S \le 10^9$$$) — the number of pillars and the total number of starlight crystals.

The second line contains $$$N$$$ integers $$$L_1, L_2, \dots, L_N$$$ ($$$0 \le L_i \le 10^9$$$) — the maximum capacity of each pillar.

Output

For each test case, output a single integer on a new line, representing the number of valid distribution plans modulo $$$10^9+7$$$.

Example
Input
3
2 5
3 3
3 4
1 2 3
15 1000000000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Output
2
5
0
Note

In the first example, there are 2 pillars and 5 crystals to distribute. Both pillars have a capacity limit of 3. There are only two valid distribution plans:

  1. Place 2 crystals in the first pillar, and 3 in the second.
  2. Place 3 crystals in the first pillar, and 2 in the second.
Output 2.

In the second example, there are 3 pillars and 4 crystals to distribute. The capacity limits are 1, 2, and 3, respectively.

There are three valid distribution plans:

  1. $$$(0, 1, 3)$$$
  2. $$$(1, 0, 3)$$$
  3. $$$(1, 1, 2)$$$
  4. $$$(1, 2, 1)$$$
  5. $$$(0, 2, 2)$$$

Output 5.

In the third example, the 15 pillars can hold at most 1 crystal each, meaning they can hold a maximum of 15 crystals in total. It is impossible to distribute 1000000000 crystals. The number of valid plans is 0.

M. Crystal Resonance
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
The deeper the resonance, the greater the power...

Deep within the ruins of Astra, explorer Little A has discovered an energy array consisting of $$$n$$$ energy crystals connected in a line. The base energy value of the $$$i$$$-th crystal is $$$a_i$$$. Due to the erosion by dark matter in the ruins, the energy values of some crystals might be negative.

Initially, the total energy of this energy array is equal to the sum of the base energy values of all the crystals.

Little A holds an ancient device called the "Resonator". He can use the Resonator to perform a soul resonance between two adjacent crystals.

When the $$$i$$$-th and $$$(i+1)$$$-th crystals resonate, they merge into an extremely unstable high-energy crystal. Their energy contribution changes from the original addition $$$(a_i + a_{i+1})$$$ to multiplication $$$(a_i \times a_{i+1})$$$.

Regarding the Resonator, there are ancient rules:

  1. Each crystal can participate in at most one resonance (i.e., the pairs of resonating crystals cannot overlap).
  2. Due to the limited charge of the Resonator, Little A can perform at most $$$k$$$ resonance operations (he can also choose to perform fewer than $$$k$$$ times, even $$$0$$$ times).

Although negative energy is dangerous, the resonance of two negative energy crystals might produce massive positive energy! Please help Little A calculate the maximum total energy the entire array can achieve after clever operations.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10$$$) — the number of test cases.

For each test case:

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 1000$$$, $$$0 \le k \le 1000$$$) — the number of crystals and the maximum number of resonance operations allowed.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$-10^5 \le a_i \le 10^5$$$) — the base energy value of each crystal.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5000$$$.

Output

For each test case, output a single integer on a new line, representing the maximum total energy the entire array can achieve.

Example
Input
3
5 1
2 3 -1 -5 4
5 2
2 3 -1 -5 4
3 1
-2 -2 -2
Output
14
15
2
Note

In the first example, at most $$$1$$$ resonance can be performed.

If no resonance is used, the total energy is $$$2 + 3 + (-1) + (-5) + 4 = 3$$$.

If the $$$-1$$$ and $$$-5$$$ resonate, their merged energy becomes $$$(-1) \times (-5) = 5$$$. The array is now effectively $$$[2, 3, 5, 4]$$$, and the total energy is $$$2 + 3 + 5 + 4 = 14$$$. This is the maximum possible value.

In the second example, at most $$$2$$$ resonances can be performed.

We can let $$$2$$$ and $$$3$$$ resonate (energy becomes $$$6$$$), and at the same time let $$$-1$$$ and $$$-5$$$ resonate (energy becomes $$$5$$$).

The array is now effectively $$$[6, 5, 4]$$$, and the total energy is $$$15$$$.

In the third example, letting the first two $$$-2$$$ resonate gives $$$4$$$, plus the last $$$-2$$$, the total energy is $$$2$$$.