ASU Coding Cup 11
A. The Anadaryy Tragedy
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Basti is known for never answering any question directly. Whenever someone asks him something, he only says the word Anadaryy and leaves the rest to Belal.

After answering far too many questions himself, Belal became frustrated and decided to ask Basti the hardest question of all time.

But before that, Belal had a strange habit: every day, he counted all the characters Basti had spoken, then wrote them down in a completely random order.

Now Belal gives Basti this shuffled collection of characters. These characters represent everything Basti said during the day. Since Basti only says Anadaryy, Belal wants to know how many times Basti could have said that word.

Each time you form the word Andaryy, you must remove exactly one occurrence of each of its characters from the given collection.

Your task is to determine the maximum number of times the word Anadaryy can be formed.

Input

The first line contains a single integer $$$n$$$ $$$(1 \le n \le 2 \cdot 10^5)$$$ — the number of characters in the collection.

The second line contains a string $$$s$$$ of length $$$n$$$, consisting of English letters, representing the given characters in random order.

Output

Print a single integer — the maximum number of times the word Anadaryy can be formed.

Examples
Input
16
AAnnaaddaarryyyy
Output
2
Input
12
ybAradnyxqAa
Output
1

B. Mukhtar's Escape Plan
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Mukhtar is obsessed with octopuses and the deep sea.

At the Dead Sea, floating salt formations act as platforms connected by unusual water currents caused by natural conditions. Mukhtar uses these platforms to move around.

The platforms are represented as nodes of an undirected graph. If there is an edge between two platforms, then Mukhtar can directly move between them.

Unfortunately, some platforms are overcrowded with Salt creatures, so Mukhtar cannot stand on them.

Mukhtar has a special ability if an overcrowded platform $$$v$$$ lies between two platforms $$$u$$$ and $$$w$$$ such that there is an edge $$$(u, v)$$$ and an edge $$$(v, w)$$$, then he may skip platform $$$v$$$ and move directly from $$$u$$$ to $$$w$$$ without standing on $$$v$$$. Using this ability on platform $$$v$$$ costs $$$f(v)$$$.

Mukhtar starts at platform $$$1$$$ and wants to reach platform $$$n$$$.

However, his energy is limited. If the total cost of skipped platforms used in his path exceeds $$$c$$$, Mukhtar gets trapped and cannot escape until the conditions improve.

Determine whether Mukhtar can escape.

If there is no valid route from platform $$$1$$$ to platform $$$n$$$, or if the minimum possible total cost is greater than $$$c$$$, print $$$-1$$$. Otherwise, print the minimum total cost.

Input

The first line contains four integers $$$n$$$, $$$m$$$, $$$k$$$, and $$$c$$$ ($$$2 \le n, m \le 2 \cdot 10^5$$$, $$$0 \le k \le n-2$$$, $$$0 \le c \le 10^{18}$$$) — the number of platforms, the number of edges, the number of crowded platforms, and the maximum total skip cost Mukhtar can afford respectively.

The second line contains $$$k$$$ distinct integers — the indices of the crowded platforms.

The third line contains $$$n$$$ integers $$$f(1), f(2), \ldots, f(n)$$$ ($$$0 \le f(i) \le 10^9$$$), where $$$f(i)$$$ is the cost of skipping platform $$$i$$$.

Each of the next $$$m$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$), denoting an undirected edge between platforms $$$u$$$ and $$$v$$$.

It is guaranteed that platforms $$$1$$$ and $$$n$$$ are not crowded.

Output

Print the minimum possible total skip cost or $$$-1$$$ if its Impossible.

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

First test case explanation:

The crowded platforms are $$$3$$$ and $$$5$$$, with skip costs $$$f(3) = 8$$$ and $$$f(5) = 2$$$.

Mukhtar can use the allowed operation to skip platform $$$5$$$ while traversing a valid path, resulting in a total cost of $$$2$$$.

C. Crazy? I Was Crazy Twice
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Qatada is perfectly sane. He tells himself this every morning.

However, ever since the Al-A3damiya Incident involving a very chill spooder, his friends have started bringing a straightjacket to every meeting just in case.

It is finally time for the AFPC, and as judges, Qatada and Abd Alrhman are supposed to be setting up the hall. Qatada, however, had a better plan: Escape.

He almost made it to the exit before Abu Tahun, who was smoking outside, caught him. After Qatada tried to bolt a second time, Abu Tahun and Abd Alrhman reached a consensus that Qatada must be locked in the corner.

The moment the lock turned, Qatada began screaming at the ceiling:

Crazy? I was crazy twice! They locked me in the Internet Hall! Internet Hall! And Internet Halls make me crazy!

To distract him from his second mental breakdown, Abu Tahun pointed at the security cameras.

Look, Qatada! Geometry!

Qatada immediately stopped screaming and pulled out a cigarette. He stared at camera $$$A$$$ and camera $$$B$$$. He noticed that their vision lines crossed at point $$$C$$$, creating a large triangle $$$\triangle ABC$$$ near the ceiling.

On the floor, a smaller triangle $$$\triangle CDE$$$ was formed by the same two vision lines.

Abu Tahun told him the following information:

The ceiling segment $$$AB$$$ is parallel to the floor segment $$$DE$$$.

Points $$$A$$$, $$$C$$$, and $$$D$$$ are collinear.

Points $$$B$$$, $$$C$$$, and $$$E$$$ are collinear.

The length of $$$AB$$$ is known.

The length of $$$DE$$$ is known.

The area of the smaller triangle $$$\triangle CDE$$$ is known.

Qatada muttered, his eyes twitching:

I must calculate the area of the ceiling triangle to find the exact coordinates of my sanity.

Given $$$AB$$$, $$$DE$$$, and the area of $$$\triangle CDE$$$, calculate the area of $$$\triangle ABC$$$.

It is guaranteed that $$$AB \parallel DE$$$, points $$$A$$$, $$$C$$$, and $$$D$$$ are collinear, and points $$$B$$$, $$$C$$$, and $$$E$$$ are collinear.

Since $$$AB \parallel DE$$$, triangles $$$\triangle ABC$$$ and $$$\triangle CDE$$$ are similar.

Therefore, the ratio between their corresponding side lengths is $$$\frac{AB}{DE}$$$.

Since areas scale by the square of the similarity ratio, the required area is:

$$$$$$S \cdot \left(\frac{AB}{DE}\right)^2$$$$$$

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 three integers $$$a, b, s$$$ ($$$1 \le a,b,s \le 10^9$$$) — where $$$a$$$ is the Distance between cameras, $$$b$$$ is the Width of the floor overlap and $$$s$$$ is the Area of the bottom triangle

Output

For each test case, output the area of triangle $$$\triangle ABC$$$. Your answer is correct if its absolute or relative error does not exceed $$$10^{-6}$$$.

Example
Input
2
12 3 6
5 2 7
Output
96.0000000000
43.7500000000

D. Prime Aqua Jelly
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Deep beneath the surface of a forgotten sea lies the Silent Abyss — a realm where numbers do not merely exist, but live.

Every integer in the Abyss is embodied as an Aqua Jelly a luminous creature woven from binary sparks. Each spark is either active or dormant, and together they encode the jelly's identity.

When two jellies meet in the deep current, something remarkable happens. Every spark that is active in exactly one of them begins to oscillate — flickering restlessly, searching for a partner. Sparks active in both jellies, or dormant in both, remain perfectly calm. The scholars of the Abyss called the count of oscillating sparks the resonance of the pair.

Through centuries of study, the scholars uncovered a sacred law of inheritance. Jelly $$$y$$$ earns the right to be called an heir of jelly $$$x$$$ if and only if their resonance is a prime number — for prime counts represent patterns that are indivisible and eternally stable in the ocean currents.

Formally, for two non-negative integers $$$x$$$ and $$$y$$$, define their resonance as $$$$$${R}(x, y) = \operatorname{popcount}(x \mathbin{|} y) - \operatorname{popcount}(x \mathbin{\&} y)$$$$$$

where $$$\operatorname{popcount}(v)$$$ denotes the number of set bits in the binary representation of $$$v$$$, the operation $$$|$$$ denotes bitwise OR, and the operation $$$\&$$$ denotes bitwise AND.

Jelly $$$y$$$ is an heir of jelly $$$x$$$ if and only if $$${R}(x, y)$$$ is prime.

You are an explorer who has descended into the Abyss with $$$q$$$ questions. Each question names an ancestor jelly $$$x$$$ and a depth $$$n$$$. count how many jellies $$$y$$$ in the range $$$[1, n]$$$ are heirs of $$$x$$$.

Input

The first line contains a single integer $$$q$$$ ($$$1 \le q \le 10^4$$$) — the number of queries.

Each of the next $$$q$$$ lines contains two integers $$$x$$$ and $$$n$$$ ($$$1 \le x \le 10^9$$$, $$$1 \le n \le 10^9$$$).

Output

For each query print a single integer — the number of integers $$$y \in [1, n]$$$ such that $$${R}(x, y)$$$ is prime.

Examples
Input
3
6 10
1 5
10 15
Output
5
2
9
Input
6
1 1
7 7
15 15
1199 2005
5 20
255 1000
Output
0
3
10
991
13
524

E. Accurate Medals
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

At each ICPC contest, there are three types of medals Gold, Silver, and Bronze.

Each winning team consists of exactly 3 members, and each member receives one medal of the same type as their team.

After being denied his medals twice because the organizers undercounted the required number, Qatada decided that this will never happen again. For every contest he organizes, he wants to buy the exact number of medals needed for all winning teams.

He goes to a medals store to buy medals for $$$n$$$ winning teams. The seller asks him:

"How many medals do you need?"

Qatada suddenly remembers that he is not very good at calculations, so he calls the best coach, Ayoub.

Ayoub hears the problem, but he is currently busy at work, so he forwards the question to you.

Can you help them compute the exact number of medals required?

Input

The first and only line of input consists of a single integer $$$n$$$ ($$$1 \le n \le 10^{8}$$$) — the number of winning teams.

Output

Print a single integer — the total number of medals required.

Examples
Input
9
Output
27
Input
1
Output
3

F. Kilani's Startup
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

After a long training session and (the tragic loss of an HDMI cable), Kilani needed something to cheer himself up. He found the legendary 7aleeb Baladna in a vending machine and buy it Seeing his teammates rushing toward the machine, he sees an opportunity so he bought all available milk and decided to resell the milk with one strict rule:

ElDain Mamnoo3 wel 3atb Marfoo3 (No debt. No exceptions.)

There are $$$n$$$ guys standing in a line. Kilani has $$$m$$$ milk bottles, each with a fixed price. The $$$i$$$-th guy has $$$a_i$$$ money, and the $$$j$$$-th bottle has price $$$b_j$$$.

Each guy, in order from $$$1$$$ to $$$n$$$, wants to buy exactly one bottle. A guy will buy the most expensive available bottle whose price does not exceed his money. Each bottle can be sold at most once. If a guy cannot afford any available bottle, he leaves without buying anything.

Your task is to determine the number of guys who cannot buy any bottle and output their indices in increasing order.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5, (m \le n)$$$) — the number of guys and the number of milk bottles respectively.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the amount of money the $$$i$$$-th guy has.

The third line contains $$$m$$$ integers $$$b_1, b_2, \dots, b_m$$$ ($$$1 \le b_j \le 10^9$$$) — the price of the $$$j$$$-th milk bottle.

Output

Print in the first line a single integer $$$k$$$, the number of guys who cannot buy any bottle.

In the second line, print $$$k$$$ integers, the indices of those guys in increasing order. If $$$k = 0$$$, print a single line containing $$$0$$$.

Examples
Input
5 3
10 4 8 3 15
5 7 12
Output
2
2 4
Input
4 4
5 6 7 8
1 2 3 4
Output
0

G. Qatada or Qashata Stick
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Qatada has always been determined to change his lifestyle. After years of skipping proper meals and relying on whatever he could find, he finally decided to take his health seriously and gain weight in a controlled and consistent way.

On the famous Street of Hungres, a place owned by Mr. Krabs and known for its endless line of restaurants and legendary food quality, there are $$$n$$$ restaurants placed in a straight line. Each restaurant serves food with a certain rating, representing how "effective" it is for Qatada's weight-gain plan.

Danial, who has been accompanying Qatada on this journey, hands him an array $$$a$$$ of length $$$n$$$ describing these restaurants.

If the value of $$$a_i \ne -1$$$, then it represents the fixed rating of the $$$i$$$-th restaurant. If $$$a_i = -1$$$, then the rating of that restaurant is unknown because Plankton has secretly tampered with the restaurant ratings while trying to steal the Krabby Patty formula, and Qatada is allowed to replace it with any integer value from $$$l$$$ to $$$r$$$ after carefully inspecting the menu.

However, Danial warns him that not every combination of choices will lead to a stable plan. After replacing all $$$-1$$$ values with valid integers, the resulting array must satisfy certain conditions.

First, no two adjacent restaurants are allowed to have the same rating. Formally, $$$ a_i \ne a_{i+1} \ \forall\, 1 \le i \lt n $$$

Second, Danial believes that a successful weight-gain plan must maintain a certain balance, so the total sum of all ratings in the final array must be odd, i.e., $$$ \sum_{i=1}^{n} a_i \equiv 1 \pmod{2}. $$$

Now Qatada wants to determine how many different valid arrays can be formed after replacing all $$$-1$$$ values such that both conditions are satisfied. Since the answer can be very large, output it modulo $$$10^9 + 7$$$.

Input

The first line contains three integers $$$n, l, r$$$ $$$(1 \le n \le 10^5, 1 \le l \le r \le 10^{18})$$$ — the number of restaurants on the Street of Hungres and the allowed range of ratings respectively.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$, where each $$$a_i$$$ is either $$$-1$$$ or satisfies $$$l \le a_i \le r$$$, describing the initial ratings of the restaurants. If $$$a_i = -1$$$, the rating of the $$$i$$$-th restaurant is unknown and must be chosen from the range $$$[l, r]$$$.

It is guaranteed that the first and last elements of the array are fixed, i.e., $$$a_1 \ne -1$$$ and $$$a_n \ne -1$$$.

Output

Print a single integer representing the number of valid ways to replace all $$$-1$$$ values under Danial conditions $$$\pmod{10^9 + 7}$$$.

Examples
Input
5 2 7
4 -1 4 2 5
Output
2
Input
6 1 4
3 -1 -1 4 -1 1
Output
7

H. 3awatleyyet El ASU
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

"Powerpuff men" and "1234" were rewarded the prize of #1 & #2 3awatleyyeh groups in ASU; therefore they thought of opening an online non-existent company and call themselves CEOs of 3awatleyyeh Co.

3awatleyyeh Co. is a company with no tasks, they only spam LinkedIn with fake achievements and success stories posts plus calling themselves El 7eetan to advertise themselves. They decided to do another useless activity together since they have nothing to do in their lives.

The activity is as follows: they wanted to compare their family trees and check what is the maximum occurrences of similar family tree structures, with the oldest known ancestors they remember as the roots of the tree, at least going back to their four grandparents. Each node in the tree has a value, either M or F. M for a Male, F for a Female.

Each person (except the roots) has exactly two parents, and no two parents of the same child share a common ancestor. The family tree is represented as a directed acyclic graph (DAG), with edges directed from parent to child. Two family trees are considered identical if they have the same structure and the same labels at every corresponding node.

Since they are lazy brain-rotted individuals, they hired you to do this task for them.

Input

The first line contains a single integer $$$n$$$ – the number of 3awatleyyeh $$$(1 \leq n \leq 10^4)$$$.

For each of the $$$n$$$ family trees:

  • A line containing a single integer $$$s$$$ – the number of people in this family tree $$$(7 \leq s \leq 10^3)$$$.
  • A line containing $$$s$$$ space-separated characters, the $$$i$$$-th being the label of node $$$i$$$ (0-indexed), either M or F.
  • A line containing a single integer $$$e$$$ – the number of edges $$$(2 \leq e \leq s(s-1)/2)$$$.
  • $$$e$$$ lines, each containing two integers $$$u$$$ and $$$v$$$ $$$(0 \leq u, v \lt s)$$$, representing a directed edge from parent $$$u$$$ to child $$$v$$$.

It is guaranteed that:

  • Every root node has no parents and represents an oldest known ancestor.
  • Every non-root node has exactly two parents.
  • No two parents of the same child share a common ancestor.
  • The graph contains no cycles.
Output

Print a single integer – the maximum number of identical family trees among the $$$n$$$ given trees.

Example
Input
4
7
M F M F M F M
6
0 4
1 4
2 5
3 5
4 6
5 6
7
M F M F M F M
6
4 6
2 5
1 4
5 6
3 5
0 4
7
M F M F M F M
6
2 5
0 4
3 5
4 6
1 4
5 6
7
F M F M F M F
6
0 4
1 4
2 5
3 5
4 6
5 6
Output
3
Note

The first three family trees are structurally identical with matching labels – the edges are listed in a different order in the input for each, but the underlying structure is the same. The fourth tree has all labels swapped (F where M was and vice versa), making it different from the rest. Therefore the answer is $$$3$$$.

I. Shamalli the crab
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the deep aqua biome, there exist more than $$$4000$$$ species of crabs, each with its own magnificent and unique appearance.

One day, Shamalli arrived at Aqaba and decided to go diving. As he descended into the depths, he was amazed by the breathtaking beauty of the biome — colorful corals, shimmering water, and countless fascinating sea creatures all around him.

Shamalli loves eating crabs, but today he decided to do something different — he wanted to learn more about them instead. Every time he encountered a crab, he carefully memorized its species, paying close attention to its features and trying not to forget any of them.

After finishing his dive, he called his friends Mukhtar and Dabbour and excitedly told them about what he had seen. Curious, they asked him one question:

What is the most common crab species you saw?

Shamalli remembers all the crabs he encountered, but determining the species that appeared the most is not as easy as it sounds. Help him find the crab species with the highest frequency.

Input

The first line contains a single integer $$$n$$$ $$$(1 \le n \le 7 \cdot 10^4)$$$ — the number of crabs Shamalli encountered during his dive.

The next $$$n$$$ lines each contain a string $$$s_i$$$, representing the species of a crab.

Output

Output a single string — the species that appeared the maximum number of times among the observed crabs.

If there are multiple species with the same maximum number of appearances, output the lexicographically smallest one.

Example
Input
10
callinectes
menippe
ocypode
callinectes
emerita
callinectes
menippe
callinectes
ocypode
emerita
Output
callinectes
Note

It is guaranteed that each species string consists only of lowercase English letters.

J. Dabbour AND Qatada then what?
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem.

Qatada and Dabbour have very strange habits. Sometimes they race through airport terminals, and sometimes they start screaming "Dorraya sin el dahab ya dorraya!" while trying to sell corn they do not even own.

Mukhtar says this is only the beginning.

One day, they sit on moving travelators, and then they lie down on them. Mukhtar finally had enough of their chaos.

To keep track of their madness, Mukhtar records a Chaos Score (a unique integer) every time something unusual happens. He stores these values in two separate files one for Qatada and one for Dabbour. Each file contains $$$n$$$ distinct integers in range $$$[1, 2 \cdot 10^9]$$$, and both files are sorted in strictly decreasing order.

One day, Mukhtar's system crashes. The screen freezes, and the full files are no longer accessible. The only remaining functionality is a restricted query system, which you may ask at most $$$72$$$ queries in total.

Interaction

The interaction begins by reading two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le k \le 2n$$$).

You may ask queries in the following format:

  • $$$? \ 1 \ i$$$ : returns the $$$i$$$-th element of the first array
  • $$$? \ 2 \ i$$$ : returns the $$$i$$$-th element of the second array

where $$$1 \le i \le n$$$.

Finally, you must output:

  • $$$! \ s$$$ : where $$$s$$$ is the $$$k$$$-th largest value among all $$$2n$$$ values combined

After printing the answer, your program must terminate.

Each output must be flushed immediately.

It can be proven that the answer can always be determined within the allowed number of queries.

Example
Input
4 3
? 1 1
10
? 2 1
9
? 1 2
7
? 2 2
5
Output
! 7
Note

Explanation of first test case the first array was $$$a = [10, 7, 4, 2]$$$ and the second array $$$b = [9, 5, 3, 1]$$$ we need to find the $$$3^{rd}$$$ largest value among all elements from both arrays combined.

After conceptually merging the two arrays $$$a + b = [10, 9, 7, 5, 4, 3, 2, 1]$$$ the $$$3^{rd}$$$ largest value is $$$7$$$.

The interaction shown in the sample demonstrates one possible sequence of queries used to determine the answer.

K. SpongeBob to Shat El-Ghandoor
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

SpongeBob has failed his boating exam more times than anyone in Qa3 El-Hamoor can count. Patrick suggested he try Jordan instead, because he heard licenses are easy to get there. SpongeBob got excited and packed for Aqaba (LOL). Squidward, being the smart one, followed him to break the news: getting a license in Jordan is actually much harder, and there is a special test every boat rider must pass first. He handed SpongeBob a slip of paper with a formula on it. If SpongeBob can compute the string it describes, Squidward will let him keep heading to Shat El-Ghandoor. Help him out, because we all know he is going to need it.

A formula is a string composed of:

  • lowercase letters a–z, which expand to themselves.
  • repetition blocks of the form #[X], #{X}, or #(X), where # is a positive integer and $$$X$$$ is itself a formula (possibly empty).
  • the delete character !.

The expansion of a formula is defined as follows:

  • A letter expands to itself.
  • A sequence of items at the same level expands to the concatenation of each item's expansion, in order.
  • #[X] expands to the expansion of $$$X$$$ repeated # times, with no separator between repetitions.
  • #{X} expands to the expansion of $$$X$$$ repeated # times, with , (a comma followed by a space) placed between consecutive repetitions.
  • #(X) expands to the expansion of $$$X$$$ repeated # times, with ; (a semicolon followed by a space) placed after each repetition, including the last one.
  • ! deletes everything accumulated at its current bracket level so far. It is strictly scoped: a ! inside a bracket never affects anything outside that bracket. A ! with nothing to delete is a silent no-op.

Important: $$$X$$$ is expanded once and then repeated. So in 3[ab!cd], the inner ab!cd first becomes cd, then is repeated three times to give cdcdcd.

Input

A single line containing the formula $$$s$$$. It is guaranteed that:

  • $$$1 \le |s| \le 10^5$$$.
  • every repetition count is an integer in $$$[1, 10^6]$$$ with no leading zeros.
  • all brackets are balanced and every opener is preceded by its repetition count.
  • the maximum nesting depth of brackets is at most $$$100$$$.
  • the peak expansion length during evaluation is at most $$$10^6$$$ characters.
Output

Print the expansion of $$$s$$$ on a single line.

Examples
Input
2[2{2(a)}]
Output
a; a; , a; a; a; a; , a; a;
Input
5[ab!cd]
Output
cdcdcdcdcd
Input
2[3[a]!b]c!d
Output
d
Input
2{ab!cd}
Output
cd, cd
Input
1[1{1{ya}1{markeb}1{rayeh}1{alagabah}}]
Output
yamarkebrayehalagabah
Note

In Example 1, 2(a) expands to a; a; (two copies of a, each followed by ; ). Then 2{2(a)} joins two such strings with , between them, giving a; a; , a; a; . Finally 2[2{2(a)}] concatenates that with itself two times.

In Example 3, the outer 2[...] first builds 3[a] into its accumulator as aaa, then the inner ! wipes that, then b is added. The inner expansion is therefore b, repeated twice gives bb. At the root level the buffer becomes bb, then c makes it bbc, then the root ! wipes the whole root buffer, then d is appended. Output: d.

L. Shrimpinous
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The sunken city of Aqua Badran is the jewel of the deep. Once a prosperous kingdom on the surface, it was swallowed by the sea in an age beyond memory yet far from being lost, it grew into one of the great underwater civilizations: a glittering metropolis of coral towers, pearl-paved boulevards, and bustling reef markets. Travelers from every trench come to taste its food, and at the heart of the city stands its most celebrated landmark, the legendary deep-sea restaurant Shrimpinous. Once a year, Shrimpinous hosts the prestigious Al3afawiah Festival, judged by the legendary merfolk chef Al3afawiah himself.

Along a long underwater reef, $$$n$$$ chefs have set up their cooking stations in a single row. The $$$i$$$-th chef ($$$1 \le i \le n$$$) has prepared a signature shrimp dish with flavor intensity $$$h_i$$$ (measured on the official Shrimpinous Spice Scale).

Al3afawiah declares a chef's dish legendary if and only if its flavor intensity is strictly greater than the flavors of both the chef to their left and the chef to their right. By this rule, the first and last chefs on the reef can never have legendary dishes, since they don't have neighbors on both sides.

The chefs want to maximize the number of legendary dishes so that Aqua Badran's culinary reputation echoes through the trenches. To boost a dish, a chef can sprinkle pinches of secret abyssal seasoning onto it — each pinch increases that dish's flavor by exactly $$$1$$$. A chef can add any non-negative number of pinches, but flavor cannot be removed.

Since the seasoning is rare and harvested from glowing kelp in the deep trenches, the chefs want to use as few pinches as possible while still maximizing the number of legendary dishes.

Find the minimum total number of pinches needed.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of competition rounds.

For each round:

  • The first line contains an integer $$$n$$$ ($$$3 \le n \le 10^5$$$) — the number of chefs on the reef.
  • The second line contains $$$n$$$ integers $$$h_1, h_2, \ldots, h_n$$$ ($$$1 \le h_i \le 10^9$$$) — the initial flavor intensities.
The sum of $$$n$$$ over all rounds does not exceed $$$2 \cdot 10^5$$$.
Output

For each round, print a single integer — the minimum number of pinches the chefs must add so that the number of legendary dishes judged by Al3afawiah is maximized.

Example
Input
6
3
2 1 2
5
1 2 1 4 3
6
3 1 4 5 5 2
8
4 2 1 3 5 3 6 1
6
1 10 1 1 10 1
8
1 10 11 1 10 11 10 1
Output
2
0
3
3
0
4
Note

In the first round, adding $$$2$$$ pinches to chef $$$2$$$ gives flavors $$$[2, \underline{3}, 2]$$$ — one legendary dish.

In the second round, chefs $$$2$$$ and $$$4$$$ are already legendary, so no seasoning is needed.

In the third round, adding $$$2$$$ pinches to chef $$$3$$$ and $$$1$$$ pinch to chef $$$5$$$ gives $$$[3, 1, \underline{6}, 5, \underline{6}, 2]$$$ — two legendary dishes using $$$3$$$ pinches, the minimum possible.

In the fourth round, the chefs can make either chef $$$2$$$ or chef $$$3$$$ legendary along with chefs further down the reef. Either way, exactly $$$3$$$ pinches are needed.

M. Whales and the Coral Grants
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the depths of the Ocean, schools of young whales train in the Coral Academies. Each whale has a certain cognitive strength measured as its GPA. To support their development, the Ocean Council issues a limited number of Coral Grants.

There are $$$n$$$ young whales and $$$m$$$ Coral Grants.

The $$$i$$$-th whale has a GPA $$$a_i$$$, representing its ability to utilize a grant. The $$$j$$$-th grant requires a minimum GPA $$$b_j$$$ to be useful.

Each whale can receive at most one grant, and each grant can be assigned to at most one whale. A whale can only receive a grant if its GPA is greater than or equal to the requirement of that grant.

can you help to determine the maximum number of whales that can receive grants.

Input

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

The first line contains two integers $$$n$$$ and $$$m$$$ $$$(1 \le n, m \le 2 \cdot 10^5)$$$ — the number of whales and the number of Coral Grants.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \le a_i \le 10^9)$$$ — the GPAs of the whales.

The third line contains $$$m$$$ integers $$$b_1, b_2, \ldots, b_m$$$ $$$(1 \le b_j \le 10^9)$$$ — the requirements of the grants.

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

Output

For each test case, Print a single integer — the maximum number of whales that can receive a Coral Grant.

Examples
Input
3
2 4
5 3
1 2 6 4
1 1
10
5
3 5
4 2 7
1 3 4 2 6
Output
2
1
3
Input
2
4 3
6 2 8 3
5 7 4
3 3
1 1 1
1 1 1
Output
2
3

N. Spectacular Seal
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

They call him the Seal, not because he swims, but because every case he touches gets closed. Stamped shut. Sealed. A few miles up the coast from Aqua Badran sprawls Aquarbour, a city so overcrowded that three people can witness a murder and all swear they were looking the other way. Last Tuesday, someone walked into the Aquarbour National Archive and walked out with the Ledger, a book the city's elite would very much prefer remained unread. The Seal took the case for one shawarma sandwich and a cup of Al Ameed coffee. His only lead: the thief left behind two coded sequences, scratched into the marble floor in two parallel rows.

  • Row $$$a$$$ contains $$$n$$$ marks bearing each odd number from $$$1$$$ to $$$2n$$$, in some order.
  • Row $$$b$$$ contains $$$n$$$ marks bearing each even number from $$$1$$$ to $$$2n$$$, in some order.
The Seal knows the cipher. The thief's identity is revealed only when row $$$a$$$ reads lexicographically smaller than row $$$b$$$. Anything else, and the marble stays silent. ("Cute," the Seal muttered. "A puzzle with a sense of drama.") He can rearrange the marks himself, but the marble is old and brittle. Each operation is:
  • choose one of the two rows,
  • pick an index $$$i$$$ from $$$1$$$ to $$$n-1$$$,
  • swap the marks at positions $$$i$$$ and $$$i+1$$$ of that row.
The two rows weren't carved equally:
  • Row $$$a$$$ was cut into soft limestone, each swap costs $$$c_a$$$ units of effort.
  • Row $$$b$$$ was cut into hard Aquarbour granite, each swap costs $$$c_b$$$.
The Seal has until sunrise. He needs the minimum total effort to make the marble talk. For two different arrays $$$x$$$ and $$$y$$$ of the same length $$$n$$$, $$$x$$$ is lexicographically smaller than $$$y$$$ if, at the first position where they differ, $$$x$$$ has the smaller element.
Input

The first line contains $$$t$$$ ($$$1 \le t \le 10^4$$$), the number of cases on the Seal's desk. For each test case:

  • The first line contains three integers $$$n$$$, $$$c_a$$$, $$$c_b$$$ ($$$1 \le n \le 10^5$$$; $$$1 \le c_a, c_b \le 10^9$$$).
  • The second line contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$, all odd, pairwise distinct, each between $$$1$$$ and $$$2n$$$.
  • The third line contains $$$n$$$ integers $$$b_1, \ldots, b_n$$$, all even, pairwise distinct, each between $$$1$$$ and $$$2n$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.
Output

For each test case, print one integer, the minimum effort the Seal must spend before the marble gives up its name.

Example
Input
3
2 1 1
3 1
4 2
3 1 3
5 3 1
2 4 6
4 4 3
7 5 3 1
2 6 4 8
Output
0
2
7
Note

Case 1. The marble is already talking ($$$3 \lt 4$$$). The Seal lights a cigarette and writes the name down. Cost: $$$0$$$. Case 2. Granite is unforgiving ($$$c_b = 3$$$). The Seal works only the limestone row, sliding $$$1$$$ to the front of row $$$a$$$ in two swaps: $$$[1, 5, 3]$$$, which already reads smaller than $$$[2, 4, 6]$$$. Cost: $$$2 \cdot 1 = 2$$$. Case 3. Now both chisels come out. One swap on row $$$a$$$ (cost $$$4$$$) brings $$$5$$$ to the front: $$$[5, 7, 3, 1]$$$. One swap on row $$$b$$$ (cost $$$3$$$) brings $$$6$$$ to the front: $$$[6, 2, 4, 8]$$$. Since $$$5 \lt 6$$$, the marble confesses. Total cost: $$$4 + 3 = 7$$$.