ICPC Pacific Northwest 2024

FizzBuzz is a common coding interview problem. The problem is as follows:

Given a positive integer n, for all integers i from 1 to n, inclusive:

• If i is divisible by both 3 and 5, print "FizzBuzz".

• Otherwise, if i is divisible by 3, print "Fizz".

• Otherwise, if i is divisible by 5, print "Buzz".

• Otherwise, print i.

We are interested in a generalized version of FizzBuzz:

Given three positive integers n, a, and b, for all integers i from 1 to n, inclusive:

• If i is divisible by both a and b, print "FizzBuzz".

• Otherwise, if i is divisible by a, print "Fizz".

• Otherwise, if i is divisible by b, print "Buzz".

• Otherwise, print i.

Given n, a, and b, how many times are "Fizz", "Buzz", and "FizzBuzz" printed for a correct implementation?

Input:

The first and only line of input contains three positive integers n, a, and b ( 1 ≤ n, a, b ≤  106 )

Output:

Output three integers: the number of times "Fizz" is printed, the number of times "Buzz" is printed, and the number of times "FizzBuzz" is printed.

Sample Input 1

17 3 5

Sample Output 1

4 2 1

Sample Input 2

10 3 3

Sample Output 2

0 0 3

• The constraints allow brute force / simulation, O(n) solution

• Use math for O(1) solution

The number of integers in the range [1,n] that divide a positive integer a is ⌊n/a⌋. You can arrive at this by thinking about the max integer x you can multiply a by such that a ∙ x ≤ n. This implies all numbers less than x can also be multiplied by a and be ≤ n. This formula works because n/a gives the exact (possibly fractional) number of times a goes into n, and the floor function ⌊ ⌋ gives us the largest integer not exceeding this value.

The number of integers in the range [1,n] that divide both positive integers a and b is ⌊n/lcm(a, b)⌋, where lcm(a, b) is the least common multiple of a and b. The idea here is that lcm(a, b) is the smallest number that is divisible by both a and b, so ⌊n/lcm(a,b)⌋ gives us the count of numbers up to n that are divisible by both a and b.

Time Complexity: O(1)

Space Complexity: O(1)

Brandon is learning the periodic table! However, he doesn't like some of the elements because the symbol of the element contains letters which are not present in the name of the element. He finds this to be unintuitive, especially because in other contexts, he expects abbreviations to not introduce random letters.

Given a string a and a proposed abbreviation b, determine if Brandon would find it intuitive. Brandon finds an abbreviation intuitive if and only if every letter that appears in the abbreviation appears in the original string. Brandon does not look at the abbreviation carefully, so it is acceptable for a letter to appear more times in the abbreviation than in the original string, or for the letters to appear in a different order between the string and the abbreviation.

Input

The first line of input contains a single integer t (1 ≤ t ≤ 10³). This is the number of test cases.

Each test case is represented on two lines.

The first line of each test case contains a single string a of length at least two and at most 50. This string only contains lowercase letters. The second line of the test case contains a single string b that is strictly shorter than a and also only contains lowercase letters.

Output

Output t lines, one for each test case.

For each test case, if all the letters in b appear in a, output YES. Otherwise, output NO.

Sample Input 1

4

magnesium

mg

silver

ag

aabb

bbb

aabb

ba

Sample Output 1

YES

NO

YES

YES

• Store which characters are in the original string

We can first iterate through the original string and use a boolean array of size 26 to track which characters are present. Then, we iterate through the abbreviation and check if each character exists in the original string. If we encounter a character that is not present, we immediately output "NO" and return. Otherwise, after checking all characters, we output "YES."

Time Complexity: O(t ∙ 50) = O(t)

Space Complexity: O(1)

The Institution for Carrying People Carefully is responsible for managing the famous Line Bus in Line Town. The Line Bus goes through n stops conveniently numbered from 1 to n. At stop i, aᵢ people first get off the bus. Then, bᵢ people get on the bus. The bus starts out empty at stop 1 and then goes through the stops in numerically increasing order, eventually stopping at stop n where the bus empties.

When someone rides the Line Bus, they must be seated. A bus with capacity c has exactly c seats for passengers. Each rider of the Line Bus occupies exactly one seat. The driver of the Line Bus is not counted. The Institution for Carrying People Carefully wants to know what is the minimum capacity bus needed to run the Line Bus.

Input

The first line contains a single integer, n (2 ≤ n ≤ 2 ∙ 10⁵).

Each of the next n lines contains two integers, aᵢ and bᵢ (0 ≤ aᵢ, bᵢ ≤ 10⁹). It is guaranteed that at least one person boards the bus, at most 10⁹ people board the bus over all stops, and that the bus will empty at stop n.

Output

Output a single integer, the minimum capacity bus needed to run the Line Bus.

Sample Input 1

4

0 3

1 2

2 1

3 0

Sample Output 1

4

• Find the maximum people there ever is on the bus

Keep track of the number of people on the bus at any given time and return the maximum.

Time Complexity: O(n)

Space Complexity: O(1)

Ashley and Brandon are playing the new hit card game, Ruffians!

In Ruffians, ten cards are dealt out in a grid of two rows and five columns. Each card has a number on it from 1 to 9. Ashley and Brandon are both looking for a pair of cards that have the same number.

After playing this game for a while, they realize that there is always a pair of cards that have the same number. To make the game harder, they require that they find a pair of cards with the same number, and that the two cards are in different rows and different columns.

Given an arrangement of cards, determine if such a pair exists or not.

Input

The first line of input contains a single integer t (1 ≤ t ≤ 10³). This is the number of test cases.

Each test case is represented on two lines.

The first line of each test case contains five integers, each between 1 and 9. The second line of the test case also contains five integers, each between 1 and 9. These two lines combined form the grid of two rows and five columns of cards.

Output

Output t lines, one for each test case.

For each test case, if there exists a pair of cards with the same number in different rows and different columns, output YES. Otherwise, output NO.

Sample Input 1

3

1 2 3 4 5

1 2 3 4 5

1 2 3 4 5

2 6 7 8 9

5 5 5 5 5

5 5 5 5 5

Sample Output 1

NO

YES

YES

• The input constraints let you brute force it / simulate it.

We'll store the first row in an array of size 5. Then, as we process the second row, we'll check each value to see if it matches any number in the first row at a different column. If a match is found, we output "YES". Otherwise, we output "NO".

Time Complexity: O(t ∙ 25) = O(t)

Space Complexity: O(5) = O(1)

Brandon is playing the newest idle game, Mouse Pursuit! The goal of this game is to pursue mice for cheese and glory.

In Mouse Pursuit, an event consists of pursuing a mouse. If the mouse is caught, the player might earn cheese and glory. However, if the mouse is not caught, the player might lose cheese and glory.

Given Brandon's recent events, Brandon wants to know how much cheese and glory he earned in the last k seconds.

Input

The first line of input contains a single integer, n (1 ≤ n ≤ 10⁵).

The next n lines take one of two forms:

• CAUGHT s c g: A mouse was caught exactly s seconds ago. The player gained c pieces of cheese and g units of glory.

• MISS s c g: A mouse was missed exactly s seconds ago. The player lost c pieces of cheese and g units of glory.

For all events, 0 ≤ c, g ≤ 10⁶ and 1 ≤ s ≤ 10⁹. It is guaranteed that no two events happened at exactly the same time.

The last line contains a single integer k. It is guaranteed that no event happened exactly k seconds ago.

Output

Output two integers - the number of pieces of cheese Brandon gained in the last k seconds, and the number of units of glory Brandon gained in the last k seconds.

Sample Input 1

3

CAUGHT 1 6 5

MISS 4 1 2

CAUGHT 8 0 3

5

Sample Output 1

5 3

• We only care about events that happened ≤ k seconds ago

Process all events while keeping track of the number of cheese pieces and glory units. For every event that occurred within the last k seconds, update the cheese and glory values accordingly.

Time Complexity: O(n)

Space Complexity: O(n) - Since k comes after all the events in the input, we have to store all the events.

The kᵗʰ Champernowne word is obtained by writing down the first k positive integers and concatenating them together. For example, the 10ᵗʰ Champernowne word is 12345678910.

It can be proven that, for any finite string of digits, there exists some integer k such that the finite string of digits will appear as a subsequence in the kᵗʰ Champernowne word.

String s is a subsequence of string t if it is possible to delete some (possibly zero) characters from t to get s.

Given a string of digits, compute the smallest integer k such that the given string of digits is a subsequence of the kᵗʰ Champernowne word.

Input

The first line of input contains a single integer n (1 ≤ n ≤ 10⁵), the length of the string of digits.

The second line of input contains a string of n digits.

Output

Output a single integer k, the minimum integer such that the given string is a subsequence of the kᵗʰ Champernowne word.

Sample Input 1

2

90

Sample Output 1

10

Sample Input 2

2

Sample Output 2

00

• If you need a digit d to appear, writing down any sequence of 10 consecutive numbers will always include it at least once.

We can brute-force the solution by writing down numbers sequentially while tracking the digits of the given string in order. As we write each new integer, we check if it contains the next required digit in the sequence. We continue this process until all digits in the string appear as a subsequence, then return the last written integer as k. 

The constraints allow this approach because the maximum length of the given string is 10⁵, and since each digit appears within at most 10 consecutive numbers, we will write down at most 10⁶ numbers—likely fewer—which should be feasible within the time limits.

Time Complexity: O(10∙n) = O(n)

Space Complexity: O(1)

Peter has way too much trash and he needs to take it all out.

Specifically, there are n bags of trash each with a specific weight. Peter can hold either one or two bags of trash per trip, and he can carry a maximum total of m milligrams of trash in a single trip. What is the minimum number of trips Peter needs to take to take out all the trash?

Input

The input starts with two integers n (1 ≤ n ≤ 5 ∙10⁵) and m (1 ≤ m ≤ 10⁹), the number of bags of trash and the maximum weight of trash Peter can carry.

The next line contains n integers, wᵢ (1 ≤ wᵢ ≤ m), the weight of each bag of trash in milligrams.

Output

Output the minimum number of trips Peter needs to make to take out all the trash.

Sample Input 1

4 1000

100 900 200 900

Sample Output 1

3

Sample Input 2

4 10

1 2 3 4

Sample Output 2

2

• It's most optimal to try and carry two bags per trip

• Sort the trash bag weights

We first sort the trash bag weights in ascending order. Then, we greedily pair the heaviest remaining bag with the lightest remaining bag whenever possible. If the sum of their weights exceeds the carrying limit m, we take the heaviest bag alone. We continue this process until all bags are taken out.

The key idea is that by always trying to pair the heaviest with the lightest, we are making optimal use of the capacity. If the heaviest can't pair with the lightest, then it definitely can't pair with any other (since after sorting, all others are ≥ lightest). Therefore, it must be taken alone, which then reduces the problem size.

Time Complexity: O(n ∙ log(n))

Space Complexity: O(1)

While in Binaria, you find a store where you want to buy some presents for your friends. In Binaria, the currency is bits, and the coin denominations are the set of all integer powers of 2. You know that you want to spend at least a bits here, but no more than b bits.

When you make a purchase, you must pay with exact change. You have an unlimited number of bits that you can access from your bank account, but you can choose to withdraw them in whatever denominations you find most convenient. Carrying many coins is inconvenient though, so you wish to minimize the number of coins you carry with you.

Compute the minimum number of coins you need to bring with you such that you can pay any integer amount of bits between a and b, inclusive.

Input

The first line of input contains a single integer a, 1 ≤ a < 2¹⁰⁰⁰⁰⁰⁰, a will be written in base 2 with no leading zeros.

The second line of input contains a single integer b, a ≤ b ≤ 2¹⁰⁰⁰⁰⁰⁰, b will be written in base 2 with no leading zeros.

Output

Output a single integer k, the minimum number of coins you need to bring.

Sample Input 1

10101

101010

Sample Output 1

6

Sample Input 2

100

101

Sample Output 2

2

• Consider two cases:

1. a and b have the same length in binary.

2. a and b have different lengths in binary.

Handle the two cases separately. 

In binary representation, each power of 2 is represented by a specific bit. For example, 8 = 1000₂, and subtracting 1 from a power of 2 gives a number with all 1s up to that bit position, like 7 = 0111₂.

To solve this problem, we need to find the largest bit position that's set in b but not in a. There are two cases:

1. If a and b have different lengths (i.e. a is shorter than b):

The first bit position in b will be the point of difference. For example, if a = 3 = 11₂ and b = 11 = 1011₂, we need to cover all numbers from 3 to 11. The highest bit in b introduces the need to cover all 4 bits, which is the length of b.

2. If a and b have the same length:

We start comparing bit by bit, from the highest bit position down to the lowest. The first bit position that's set in b but not in a gives us the number of bits we need to cover the range between a and b. For example, if a = 17 = 10001₂ and b = 20 = 10100₂, they first differ at the third bit from the left. From there, the remaining part of the bit string is 3 bits long. This means we need at least 3 bits to represent all numbers between a and b. Additionally, we must include the higher bits that both numbers share, so the total number of bits required will be 4.

Time Complexity: O(n)

Space Complexity: O(1)

Alice was recently given a homework assignment to write a program that would output the number of inversions in any subarray of a given permutation. She happily turned it in and got full marks on her assignment. The next week, their homework assignment was to find the length of the longest increasing subsequences in the same array. Unfortunately, Alice had already thrown away the paper that contained the permutation she needed.

Luckily, this permutation was stored in the program she wrote. Unfortunately, she is now only able to query for the number of inversions in the subarrays of the permutation. As class is close to starting, she asks you for help to solve this problem in a timely manner.

A sequence a is a subsequence of an array b if it is possible to delete some (possibly zero) elements from b to get a. A sequence is increasing if every element is strictly greater than all preceding ones, and the LLIS of an array is the length of the longest increasing subsequence.

Interaction

This is an interactive problem.

Interaction starts by reading a single integer n (1 ≤ n ≤ 10³), the length of the permutation p.

You are then able to make at most n queries of the form ? l r where 1 ≤ l < r ≤ n. Each query should be on a single line. After each query, read in a single integer, the number of inversions in the subarray [l, r]. An inversion is a pair of integers (x, y) where l ≤ x < y ≤ r and pₓ > pᵧ.

When you have determined the LLIS, output the answer in the form: ! ans on a single line, where ans is the LLIS. After outputting the answer, your program should exit. If you attempt to read a response after outputting an answer, you will receive an arbitrary verdict.

Do not forget to flush the output after each query you output.

The interactor is not adaptive: When the interaction begins, the permutation p is already determined. It is guaranteed that each integer from 1 to n appears exactly once.

If the interactor receives any invalid or unexpected input, the interactor will output -1 and then immediately terminate. Your program should cleanly exit in order to receive a Wrong Answer verdict, otherwise the verdict that it receives may be an arbitrary verdict indicating that your submission is incorrect.

If your program terminates before outputting the answer, your submission will receive an arbitrary verdict indicating that your submission is incorrect.

You are provided with a command-line tool for local testing. The tool has comments at the top to explain its use.

Sample Interaction 1

Read

3

Write

? 1 2 3

Read

1

Write

? 1 2

Read

1

Write

!  2

• Start with ? 1 2, if the response is 1, then you know the number at position 2 is smaller than the number at position 1.

• It's possible to rebuild the actual permutation given n queries.

We reconstruct the original permutation one element at a time by issuing queries of the form ? 1 i for each i in the range [1, n] and storing the resulting values in an array. Assume that we've successfully determined the first x elements of the permutation. When we query ? 1 x, we obtain an inversion count of K for that prefix. To determine the (x+1)ᵗʰ element, we initially assume that it is x+1 and then perform a query ? 1 (x+1). Suppose this query returns an inversion count of Y.

Since adding one more element to the sequence cannot decrease the inversion count, we know Y ≥ K. There are two cases:

1. If Y equals K, this means that the newly assumed element did not create any additional inversions with the previously placed numbers, so it is already in the correct position. In this case, we simply move on to the next element.

2. If Y is greater than K, let D = Y - K. This difference d indicates that the new element is smaller than exactly D numbers among those to its left. So we slide this new element leftward—swapping it with each of the d elements to its left—until it reaches the correct position relative to the already-placed elements.

3. 
   

Once we've built the full permutation using this sliding mechanism, we then run the standard LLIS (Longest Increasing Subsequence) algorithm on our recovered permutation array to obtain the final answer.

Time Complexity: O(n)

Space Complexity: O(n)

Ashley is training for another programming contest on Brandon's Online Judge.

Ashley has k weeks left to train for her next programming contest. Her coach, Tom, is very busy and is no longer curating specific problems for Ashley to train on. At the start of every week, Tom picks p distinct problems independently and uniformly at random from the bank of n problems that Brandon's Online Judge has and assigns them for Ashley to work on. Tom generates a total of k sets of problems in this manner.

Ashley diligently solves every problem that Tom picks out. However, she gets annoyed if there exist two different weeks that share at least one problem in common, because she wants to solve unique problems.

Compute the probability that Ashley becomes annoyed.

Input

The first and only line of input contains three integers, n (1 ≤ n ≤ 10⁷), k (1 ≤ k ≤ 10⁷), and p (1 ≤ p ≤ n).

Output

Let p be the probability that Ashley becomes annoyed. It can be shown that p can be written as a rational number x/y with gcd(x, y) = 1 and y ≠ 0 (mod 998244353). Define r to be the unique integer in [0, 998244353) such that r ∙ y ≡ x (mod 998244353). Output r.

It can be shown that, under the constraints provided, r is guaranteed to exist and also be unique.

Sample Explanation

In the first sample, we can show that the probability Ashley becomes annoyed is 7/9. Note that 110916040 ∙ 9 ≡ 7 (mod 998244353), therefore the output for that test case is 110916040.

In the second sample, we can show that Ashley always becomes annoyed. Note that 1 ∙ 1 ≡ 1 (mod 998244353), therefore the output for that test case is 1.

In the third sample, we can show that Ashley never becomes annoyed. Note that 0 ∙ 1 ≡ 0 (mod 998244353), therefore the output for that test case is 0.

Sample Input 1

3 3 1

Sample Output 1

110916040

Sample Input 2

3 2 2

Sample Output 2

1

Sample Input 3

3 1 1

Sample Output 3

0

• Compute the probability that Ashley doesn't become annoyed

First, if k ∙ p > n, then Ashley is guaranteed to be annoyed. We can output 1 immediately.

Ashley will not be annoyed if the k sets of problems Tom picks are all distinct:

1. In the first week, Tom may choose any set of p problems out of the n available problems.

2. In the second week, Tom must choose p problems that were not chosen in the first week. The number of ways to do this is given by the binomial coefficient C(n – p, p). Since there are C(n, p) total ways to choose p problems in any week, the probability that there is no overlap in the second week is:

C(n – p, p) / C(n, p)

3. In the third week, Tom again chooses p problems that do not overlap with the problems chosen during the previous two weeks. In this case, the probability is:

C(n – 2p, p) / C(n, p)

4. This pattern continues for each subsequent week. Thus, the total probability that Tom picks distinct sets of p problems each week (with no overlap for k weeks) is the product:

[ C(n, p) ∙ C(n – p, p) ∙  … ∙  C(n – (k – 1)p, p) ] / [ C(n, p) ᵏ ].

Ashley becomes annoyed if there is any overlap. So, the probability that Ashley is annoyed is 1 minus the product above.

To compute this probability, we calculate the numerator and denominator separately. As in the problem description, let the numerator be denoted by x and the denominator by y. We then reduce the fraction x/y by dividing both x and y by their greatest common divisor (GCD) to obtain a fraction in simplest terms. The final result is output as an integer r, where r is defined as:

y ∙ r ≡ x (mod 998244353)

r ≡ y ⁻¹ ∙ x (mod 998244353)

To compute the modular inverse of y, we can use Fermat’s Little Theorem. Fermat’s Little Theorem tells us that for any number y and a prime modulus p, y ⁽ ᴾ ⁻ ¹⁾ ≡ 1 (mod p). This means the modular inverse of y is:

   y ⁻¹ ≡ y⁽ᴾ ⁻ ²⁾ (mod p)

We can use binary exponentiation to calculate the modular inverse efficiently. The key idea behind this algorithm is that aᵇ∙aᵇ = a²ᵇ. Thus, each time we raise a number to an even power, we can recursively compute aᵇ÷² and then square it. This approach results in an O(log n) runtime for computing powers.

We the modulo inverse of y, we can use it to calculate and output r.

Time Complexity: O(n + log₂998244353) = O(n)

Space Complexity: O(n)

Nick is preparing a problem for a programming contest about comparing big integers. He has decided on the input format for the integers: They will be expressed in base 62, with 0 through 9 representing digit values 0 through 9, lowercase letters a through z representing digit values 10 through 35, and uppercase letters A through Z representing digit values 36 through 61. For example, the string Aa would represent 36 x 62 + 10 = 2242.

The problem is to take two strings representing two distinct base 62 integers and determine which of the two is smaller. However, Nick wrote his judge solution incorrectly, assuming that the lexicographically smaller string is always the smaller integer.

Given some test cases, determine for each if Nick's solution would report the correct result.

Input

The first line of input contains a single integer t (1 ≤ t ≤ 10⁵). This is the number of test cases.

Each test case consists of two lines.

The first line contains a single alphanumeric string of length at most 10⁵.

The second line contains a single alphanumeric string of length at most 10⁵.

Both strings are guaranteed to contain no unnecessary leading zeroes, and the two strings are guaranteed to be distinct.

The sum of the lengths of all input strings across all t test cases is guaranteed to be at most 2 ∙ 10⁶.

Output

For each test case, output a single line with YES if the lexicographically smaller string represents the smaller integer in base 62, and output a single line with NO otherwise.

Sample Input 1

2

icpc

ICPC

a

bc

Sample Output 1

NO

YES

• Longer digit strings, even in base 62, are always larger numbers

• Compare the digits one at a time

We can treat the base 62 digits similarly to base 10 digits when comparing their values. If the two digit strings have different lengths, we can immediately determine which one represents the smaller integer by comparing their lengths. The shorter string is numerically smaller, so if Nick assumed the shorter string was larger, we output "NO", and if he assumed the longer string was larger, we output "YES". If the two digit strings are the same length, we compare them digit by digit starting from the most significant position (the leftmost one). The first position where the digits differ tells us which number is larger. We then check whether Nick’s assumption about the lexicographical order matches the actual numerical comparison. If it matches, we output "YES"; otherwise, we output "NO".

Time Complexity: O(t ∙ n) 

Space Complexity: O(1)

Antonio is sightseeing in Line Town. Part of his sightseeing involves taking the famous Line Train. The Line Train goes through n stops conveniently numbered from 1 to n. The path the Line Train takes involves starting at stop 1, then going to every stop in numerically increasing order until it reaches stop n, at which point it turns around and goes to every stop in numerically decreasing order until it reaches stop 1, where it turns around and repeats its journey. When the train gets to either stop 1 or stop n, it lets all passengers that want to disembark leave the train. It then turns around, and then allows new passengers to board before heading to the next stop.

Antonio is traveling from stop a to stop b. Antonio is very sleepy, so he is not paying attention when he boards the train and could board a train initially heading in the wrong direction. Immediately upon boarding the train, he falls asleep and wakes up t times during the trip. Each time he wakes up, he notices that he is somewhere between stop sᵢ and sᵢ + 1. Since he is very sleepy, he does not know which direction the train is traveling in. Also, since he is not presently at his destination, he immediately falls back asleep.

After the tᵗʰ time waking up, Antonio decides he should stay awake for the rest of the trip. He stays on the train until the next time it stops at stop b, at which point he disembarks.

Compute the minimum number of times the train turned around while he was on it.

Input

The first line contains four integers, n (2 ≤ n ≤ 10⁹>), t (1 ≤ t ≤ 10⁵), a, and b (1 ≤ a, b ≤ n, a ≠ b).

The second line contains t integers. The iᵗʰ integer, sᵢ (1 ≤ sᵢ < n), indicates that when Antonio woke up for the iᵗʰ time, he was somewhere between stops sᵢ and sᵢ + 1.

Output

Output the minimum number of times the train turned around while he was on it.

Sample Input 1

10 1 5 3

4

Sample Output 1

0

Sample Input 2

10 2 5 3

5 4

Sample Output 2

1

• Be greedy

We can determine the train's direction by comparing each wake-up stop to the previous one. By comparing consecutive wake-up positions:

• If sᵢ > sᵢ₋₁, the train is moving right.

• If sᵢ < sᵢ₋₁, the train is moving left.

Each time the direction changes, the train must have turned around. At first, I had trouble comparing the current position to the previous one since we’re only told Antonio is between stops sᵢ and sᵢ+1. My first approach was to treat all wake-up positions (except for boarding and disembarking) as sᵢ + 0.5 to make comparisons easier. But in my second solution, I figured out how to work with the given stops directly by being more careful with the comparisons.

Time Complexity: O(t)

Space Complexity: O(1)

It's finally here! The day you unveil your new invention, the Auto-Coin-o-Matic! You watch with glee and anxiety as people insert their card into the machine, type in the amount they want, and get exact change out with the fewest number of coins.

But was it actually the fewest number of coins? That's how it was programmed, but what if you had a bug? It's okay, you're watching. You decide to randomly pick some transactions and double check that what the machine gave out is indeed the fewest number of coins possible. But, oh no, the machine is running out of certain types of coins! Will it still work correctly?

Input

The input starts with two integers n and m (1 ≤ n ≤ 2000, 1 ≤ m ≤ 10⁵).

The next line contains n integers, d₁, d₂,..., dₙ (1 ≤ dᵢ ≤ 10⁵) representing the denominations of coins available initially. It is guaranteed that all denominations are unique.

The next m lines contain a character c (c ∈ {Q, X}) and an integer v (1 ≤ v ≤ 10⁵), where c is the type of event and v is the value of the event.

• If c is the character Q, this is a query and the output should be the minimum number of coins needed to give out exactly v. It is guaranteed that there will be at least one query.

• If it is not possible to make v exactly with the available denominations, output -1 instead.

• If c is the character X, this means the machine is out of coins of denomination v. All queries after this point cannot use this denomination. It is guaranteed that each X event corresponds to a denomination v which the machine currently has in stock.

Output

Output k lines, where k is the number of query events (c = Q). On the iᵗʰ line, output the fewest number of coins needed to give change for the iᵗʰ query, or -1 if this is impossible.

Sample Input 1

4 7

1 2 5 10

Q 23

X 1

Q 23

X 5

Q 23

X 10

Q 22

Sample Output 1

4

6

-1

11

• Reverse time

If you know with the popular min coin change problem, this follows a similar approach with a twist. The key idea is to process all input first and then reverse the order of events.

Since the maximum value we could be queried for is 100000, we'll create a DP array of that size where dp[x] represents the minimum number of coins needed to make change for x. To update it, iterate from 1 to 1e5 and apply dp[x] = min(dp[x], dp[x - y] + 1) for each new coin y.

Then, process the events in reverse order. For each query, return the precomputed DP result. When encountering a remove event, add the coin back and update the DP array accordingly.

Time Complexity: O(m ∙ 1e5) in the worst case

Space Complexity: O(m + 1e5)

On the Word Game show, Ashley has selected n words and asks Brandon to combine them. Two words s and t can be combined if s has a suffix of length k > 0 that is a prefix of t. The result of combining them is a new word made of s concatenated with the last |t - k| letters of t. If there are multiple values of k that are valid, any can be chosen.

Brandon must repeatedly take a pair of words from the list of words that can be combined, and replace them in the list with the combined word, until the list contains only a single word, and that word is as short as possible. If multiple final words of the same length are possible, Brandon must find the lexicographically first one.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 5), the number of words to start out with.

The next n lines each contain a single word in lowercase letters of length at most 5.

Output

Output the lexicographically first word of minimum length Brandon can come up with. If it is not possible to come up with a single word, output -1.

Sample Input 1

2

aba

bab

Sample Output 1

abab

Sample Input 2

3

ab

bc

ca

Sample Output 2

abca

Sample Input 3

2

x

y

Sample Output 3

-1

• The input constraints let you brute-force the answer

We can use a backtracking approach that tries every possible sequence of merging the words until only one word remains. At each step, we select a pair of words and check if one has a suffix (of length k > 0) that matches a prefix of the other. If a valid overlap exists, we merge the words by appending the non‐overlapping part of the second word to the first word. This merged word then replaces the pair in the list, and the process continues recursively.

Because there are at most 5 words and each word has at most 5 letters, the number of possible combinations is very limited. In the worst case, when starting with 5 words, there are C(5, 2) = 10 possible pairs to merge. After the first merge, 4 words remain (with 6 possible pairs), then 3 words (3 pairs), and finally 2 words (1 pair). Multiplying these, we get 10 ∙ 6 ∙ 3 ∙ 1 = 180 distinct sequences of pair selections. For each chosen pair, we might try up to 5 possible overlap lengths (since the maximum overlap length is at most 5), leading to roughly 180 ∙ 5⁴ = 180 ∙ 625 = 112,500 merge operations in the worst case. In each merge operation, checking whether two words overlap correctly is done in O(length of word) time, but since the words are very short (length ≤ 5), each check is effectively constant time. This makes the backtracking approach efficient enough given the constraints.

Time Complexity: O(112,500) in the worst case

Space Complexity: O(n) for the recursion and storing temporary merged words

You have a set of n bowls, arranged in a circle.

You have many balls of various colors. There are m different colors, and you have cᵢ balls of the iᵗʰ color.

You want to distribute all the balls into the bowls. To do this, for each color, you choose a contiguous range of bowls of size cᵢ and place one ball of that color in each bowl in the range. A contiguous range of bowls is a set of consecutive bowls around the circle. Ranges from different colors are allowed to overlap.

A bowl is rainbow if it contains one ball of each color. A rainbow bowl range is a contiguous range of rainbow bowls that cannot be extended by including another rainbow bowl.

You want to arrange balls in bowls to maximize the number of rainbow ranges.

Given the number of bowls and the number of balls of each color, what is the maximum number of rainbow bowl ranges that can be formed?

Input

The first line contains two integers, n (2 ≤ n ≤ 10⁹), m (1 ≤ m ≤ 10⁵).

The next m lines each contain a single integer, cᵢ (1 ≤ cᵢ ≤ n).

Output

Print a single integer, the maximum number of rainbow bowl ranges that can be formed.

Sample Input 1

4 2

3

3

Sample Output 1

2

Sample Input 2

10 11

3

1

4

1

5

9

2

6

5

3

5

Sample Output 2

1

• More than two rainbow ranges are possible

• Align gaps optimally

The tech team is gearing up for the PacNW Regional! There are n computers that need to be connected together for the contest, isolated from the outside internet. There are m bidirectional connections between computers, each connection requiring one of k different types of cable (for example, CAT5, RS232, MIDI, etc.). Using all the possible cable types, every computer is reachable from every other computer by following some set of cables. In addition, each pair of computers participates in at most one connection. Finally, to minimize leakage, no two distinct simple cycles of connected computers can have more than one computer in common (a simple cycle is a cycle where each computer can appear at most once, and two cycles are distinct if there is at least one connection present in one but not the other).

The tech team needs to make sure that every computer can communicate with every other computer, but doesn't want to use all the cable types if they don't have to. Can you help them figure out the answers to two questions: what is the minimum number of cable types they need to connect all of the computers, and how many subsets of cable types would allow every computer to communicate with every other computer?

Input

The first line contains three integers n, m, and k (1 ≤ n ≤ 2 ∙ 10⁵, n - 1 < m ≤ 3 ∙ 10⁵, 1 ≤ k ≤ 24) - the number of computers, the number of connections, and the number of cable types respectively.

The next line contains k strings: the iᵗʰ string is the name of the iᵗʰ cable type. Each cable name is made up of between 1 and 10 alphanumeric characters. It is guaranteed that the cable names are distinct.

The next m lines describe the connections between the computers. The iᵗʰ line contains two integers x and y (1 ≤ x < y ≤ n) and a string s (guaranteed to be one of the cable types).

Output

Output two lines, each containing a single integer. The first line should contain the minimum number of cable types the tech team needs connect all the computers. The second line should contain the number of subsets of cable types such that only installing those types would connect all of the computers.

Sample Input 1

6 7 4

CAT5 RS232 MIDI USBC

1 2 CAT5

2 3 MIDI

3 4 MIDI

2 4 CAT5

4 5 MIDI

5 6 MIDI

4 6 RS232

Sample Output 1

2

4

• Break it into sub-problems

• When is it mandatory for a cable type to be included?

• What do cycles and non-cycles tell us?

We're asked to determine two things: (1) the minimum number of cable types needed to connect all the computers, and (2) the number of subsets of cable types that allow every computer to communicate with every other computer. We can approach this problem this by breaking it into the following subproblems:

1. Identify Mandatory Cable Types:

First, we analyze the structure of the network by distinguishing between cycles and chains (acyclic paths). In the parts of the graph that form chains, the cable type(s) on the connections are essential—if you remove any of these, connectivity would be lost. In cycles (loops), some cable types might appear only once, which means they could potentially be omitted without breaking connectivity, provided another cable in the cycle is present. However, if a cable type appears more than once in a cycle, it becomes mandatory since removing it would split the cycle into disconnected pieces.

2. Enforce Cable Dependencies Using Bitmasks:

To formalize these dependencies, we introduce an array called mustKeepIfRemoved[numCableTypes] with one entry per cable type. For each cable type i, mustKeepIfRemoved[i] is a bitmask representing the other cable types that must be included if cable type i is removed from the graph.

For cable types required due to being part of linear chains, we simply mark the cable type itself in its bitmask.

For cycles where a cable type appears uniquely, if we decide to remove it, then every other cable type in that cycle must be kept in order to preserve the cycle’s connectivity. Therefore, for such cable types, we update mustKeepIfRemoved with bits corresponding to all the other cable types in that cycle.

3. Evaluate All Cable Type Subsets:

Once we build the graph, convert cable type names to their corresponding indices, detect cycles, and populate the mustKeepIfRemoved array, we iterate over all possible subsets of cable types (up to 2ⁿᵘᵐ⁻ᶜᵃᵇˡᵉ⁻ᵗʸᵖᵉˢ). For each subset, we:

• Check if the subset is valid by ensuring that for every cable type omitted, the cable types indicated by its corresponding bitmask (from mustKeepIfRemoved) are present.

• If the subset is valid, consider it for counting and update the value for the minimum subset size if its size is lower.

Time Complexity: O(n+m+2ᵏ)

Space Complexity: O(n+m+k)

In the Shape Galaxy, where all shapes are sentient beings, there is currently a feud between circles and squares. Circles want all pathways to be flat while squares argue that they should be evenly spaced inverted catenary shaped bumps. Because of this feud, circles have begun to dislike all square-biased numbers. A number s is square-biased if it is divisible by x², for some integer x > 1.

Mr. Circle has taken this feud to heart. He is given the assignment of calculating the greatest common divisor between all pairs of numbers in an array. He wants to go one step further and count the number of greatest common divisors that are not square biased.

Input

The first line of input contains a single integer, n (1 ≤ n ≤ 10⁵), representing the length of the array of numbers.

The next n lines contain the integers aᵢ (1 ≤ aᵢ ≤ 10¹²) which comprise the numbers in the array.

Output

Output a single integer, the number of pairs (i, j) (1 ≤ i < j ≤ n) such that gcd(aᵢ, aⱼ) is not square-biased.

Sample Input 1

6

3

4

6

12

4

1

Sample Output 1

12

• Count the number of greatest common divisors that are square-biased.

  • Then at the end you can return (n∙(n-1))/2 - [number of greatest common divisors that are square-biased]

• Find the greatest square divisor for each number.

  • Achieve this in O(∛K) for a number of size K

  • Check primes directly

  • We only need to go up to the cube root because if K has a square divisor, it can be written as a product of a square part and a non-square part.

• Use the principle of inclusion-exclusion to count the number of distinct pairs whose greatest common divisor is square-biased.

  • Use bit masks. A number up to 10¹² can have at most 8 distinct prime factors in its greatest square divisor (e.g., 2 ∙ 3 ∙ 5 ∙ 7 ∙ 11 ∙ 13 ∙ 17 ∙ 19 = 9699690, and squaring this exceeds 10¹²)

This problem involves a number of tricks, so don't worry if you didn't get it.

The goal is to count the number of pairs (i, j) (with 1 ≤ i < j ≤ n) such that gcd(aᵢ, aⱼ) is not square‐biased. A number is called square‐biased if it is divisible by some square number (x² for some x > 1)—in other words, if its prime factorization contains any prime with an exponent of two or more.

First, recognize that it is easier to count the pairs that are square‐biased gcd’s and then subtract this count from the total number of pairs (n∙(n−1)/2). Two numbers will have a square‐biased gcd if they both contain, in their "square part," a common prime factor (i.e. a prime that appears with an exponent of at least 2).

So for every number in the array, we need to extract its "largest square divisor", or the list of distinct primes p for which the number is divisible by p². We do this by the following steps:

• First, we precompute a list of primes using sieve's algo up to 1e6.

• For each number aᵢ (which can be as large as 10¹²), we iterate through our list of primes up to approximately its cube root. For each prime p in this range, if aᵢ is divisible by p², we add p to the list of square primes for aᵢ. We then repeatedly divide by p² to reduce aᵢ and potentially end iterating through our primes list earlier.

• After the loop, some square-biased factors might remain if they involve a prime greater than the cube root. We handle this by taking the square root of the remaining value; if the remaining value is a perfect square whose square root is prime, we add that prime as well.

The result for each number is the set of primes that “cause” it to be square‐biased.

Once each number’s square-biased prime factors are determined, we count pairs that share at least one common square-biased factor using the principle of inclusion–exclusion. The idea is to iterate over every nonempty subset of these prime factors (using bit masks):

1. For each nonempty subset, compute the product of the primes in that subset. This product represents a particular factor that might appear in the gcd’s square component.

2. For every such product, use a frequency array (gcdSquareFactorCount) to keep track of how many numbers encountered so far have that product as part of their greatest square divisor.

3. When processing a number, for each subset of its square primes:

   1. If the subset has an odd number of primes, add the frequency count of its corresponding product to a running total (squareBiasedCount).

   2. If even, subtract the frequency count.

This alternating sum correctly counts pairs that share at least one common square factor without overcounting cases where the number has multiple square-biased prime factors.

After iterating through all the numbers, squareBiasedCount holds the number of pairs of numbers whose gcd is square-biased. Finally, subtracting squareBiasedCount from the total number of pairs (n∙(n−1)/2) yields the desired count of pairs with a non-square-biased gcd.

Time Complexity: 

• The sieve run, which is O(V log log V) with V on the order of 10⁶

• For each number, iterating only up to its cube root and over at most 2⁸ (256) subsets (since a number won’t have many square prime factors under the constraints).

Space Complexity:

• O(V) for sieve and the gcdSquareFactorCount array

Alex is a climber who is planning his next free solo expedition. He wants to do a completely new climb this time, one that nobody else has done before. Before he starts the climb, he wants to get a rough idea of what the shortest path to the top is.

In climbing, Alex uses his hands and feet to hold on to "holds," which are points on the wall he is climbing where he can put either his hands or feet to stabilize himself.

In this simplified simulation of the route, Alex is modelled as a single point, from which 4 limbs of up to length 1 extend out from. Holds on the wall are also single points, and can be used by any of his limbs, but one hold can only be used by one limb at a time. In order to stay safe, Alex must ensure that at least 3 of his limbs are attached to holds at all times during the climb.

Alex starts at coordinate (0,0) on 3 holds located at (-0.2, 0), (0, 0), and (0.2, 0) and has a target hold at (Tₓ, Tᵧ) he is trying to reach. Find the length of the shortest path traced out by Alex's location until he is able to put one limb on the target hold. Alex's location is allowed to be anywhere on the wall as long as he stays safe, including locations with negative y-coordinates.

Guarantees:

• No two holds will be within 10³ units of each other.

• No two holds will be within 10³ units of being distance 2 apart from each other.

• There will not exist a location on the wall where Alex is able to reach more than 6 holds.

• If Alex's reach increases or decreases by up to 10⁶, the length of the shortest path will not change by more than 10⁵.

Input

The first line contains an integer n (1 ≤ n ≤ 30), the number of holds.

The next n lines contain two floating point numbers, the x and y coordinates of each hold (-10 ≤ x ≤ 10, 0 ≤ y ≤ 10).

Floating point numbers will be expressed to exactly 5 decimal places.

The three starting holds are not included in the input. The target hold is the last hold given.

Output

Output the length of the shortest safe path to the target hold, or -1 if no such path exists. 

Your answer will be accepted if the absolute or relative error is within 10⁴ of the judge's answer.

Sample Input 1

1

0.00000 1.50000

Sample Output 1

0.5000000000

Sample Input 2

1

0.00000 2.50000

Sample Output 2

-1

Sample Input 3

4

0.00000 0.50000

-0.80000 1.50000

0.80000 1.50000

0.70000 2.20000

Sample Output 3

1.3647093219

• Imagine a circle of radius 1 unit around each hold. Alex always needs to be in a region where at least three circles overlap.

• The intersections between two circles are critical points, as they determine potential turn locations for Alex.

• A straight line from Alex to the destination hold, when it intersects the 1-unit circle around the destination, is also a critical point.

• To solve this, we can use Dijkstra’s algorithm on the critical points, applying a line-sweep technique to validate the path between critical points.