XXX Spain Olympiad in Informatics, online qualifier
A. Hugo's Soft Drinks
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Hugo is helping organize a small event and is in charge of buying the drinks. They come packaged in boxes of two different sizes. Small boxes always contain 6 cans of drink each, while large boxes always contain 15 cans of the same drink.

Hugo writes down on a piece of paper how many small boxes and how many large boxes he has in storage. With this information, he wants to know how many cans of drink he has in total.

Input

The input consists of two lines. The first line contains an integer $$$P$$$ indicating how many small boxes Hugo has. The second line contains an integer $$$G$$$ indicating how many large boxes Hugo has.

Output

Print a single integer: the total number of cans of drink that Hugo has.

Scoring
  1. (10 points) $$$P = G = 1$$$
  2. (15 points) $$$G = 0$$$
  3. (25 points) $$$P = 0$$$
  4. (50 points) No additional restrictions.
Example
Input
3
2
Output
48
Note
  • $$$0 \le P \lt 100$$$
  • $$$0 \le G \lt 100$$$

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

The Arriaga Museum is going to replace its old system of codes assigned to the works with a new, clearer, and more organized one.

Some pieces are twin works. They are pairs of pieces that share exactly the same code because they are practically identical. In the new system, this must be maintained: two works that had the same old code must retain the same new code, and works with different codes cannot share one.

The works are placed in a long hallway in a fixed order that cannot be modified. From time to time, Mr. Ernesto Lafuente, the catalog inspector, walks down the hallway reviewing the works in that same order. It is much more convenient for him if, as he progresses, the codes he reads tend to appear in increasing order.

The Board wants to assign the new codes in such a way that, while respecting exactly the same groups of twin works as the old system, the number of times a greater code appears before a lesser one in the walkthrough is minimized.

Help them by constructing a code assignment that minimizes that number. The new codes must:

  • Maintain exactly the same groups of twin works as the old codes.
  • Minimize the number of pairs of positions $$$i \lt j$$$ where the code at position $$$i$$$ is greater than the code at position $$$j$$$, known as an inversion.

If there are multiple optimal solutions, any of them will be valid.

Input

The first line contains an integer $$$T$$$, the number of cases to process.

The first line of each case contains $$$n$$$, the number of works placed in the hallway.

The second line contains $$$n$$$ positive integers $$$a_1, a_2, \ldots, a_n$$$, where $$$a_i$$$ is the old code of the work located at position $$$i$$$ in the hallway. Each value appears at most twice.

Output

For each case, you must print a line with $$$n$$$ positive integers, $$$b_1, b_2, \ldots, b_n$$$, representing the new codes assigned to the works to minimize the number of inversions, in the same order as in the hallway. If there are multiple optimal assignments, you can print any of them.

Example
Input
2
3
3 2 1
4
2 1 1 2
Output
1 2 3 
1 2 2 1
Note
  • $$$1 \le T \le 10^5$$$
  • $$$1 \le n \le 10^5$$$
  • The sum of $$$n$$$ across all cases will be at most $$$10^5$$$.
  • $$$1 \le a_i, b_i \le n$$$

C. The Battle for the Ratings
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

During the prime time slot, television networks compete minute by minute to lead the audience ratings. From the data collected by audience meters, the number of viewers watching each channel at every instant is known.

Telemachus must analyze a time slot of $$$D$$$ minutes and determine for how long each channel has been the most watched. Specifically, the $$$D$$$ intervals $$$[m, m+1)$$$ are considered for $$$0 \le m \lt D$$$.

At minute 0, the initial audiences of all channels are known. Afterwards, updates are received: at certain minutes, the audience of some channels changes, remaining constant until the next update.

It is guaranteed that at every minute there is a unique channel with the maximum audience.

The following figure shows the evolution of the audiences in the sample input. The thicker segments indicate which channel leads during each interval.

Input

The input begins with a line containing an integer $$$T$$$ indicating the number of test cases that follow.

Each case begins with three integers $$$D$$$, $$$C$$$, and $$$N$$$: the duration of the observed time slot (in minutes), the number of channels, and the number of updates.

Then:

  • One line with $$$C$$$ integers: the audience of each channel at minute $$$0$$$, from channel $$$1$$$ to channel $$$C$$$.
  • $$$N$$$ lines, each with the format

    $$$$$$ m\ u\ c_1\ e_1\ \dots\ c_u\ e_u $$$$$$ which indicates that at minute $$$m$$$ (with $$$0 \lt m \lt D$$$) a total of $$$u$$$ channels (with $$$u \gt 0$$$) change their state: the channels $$$c_1, \dots, c_u$$$ change their audiences to $$$e_1, \dots, e_u$$$, respectively, from that minute onwards.

Updates are given in strictly increasing order of minute, and no channel appears more than once within the same update.

Output

For each case, print on separate lines every channel that has been the most watched for at least one minute, followed by the number of minutes it has led the audience.

Lines must be sorted by the number of minutes in decreasing order, and in case of a tie, by increasing channel identifier.

Scoring
  1. (8 points) $$$N = 0$$$
  2. (12 points) $$$C = 2$$$
  3. (15 points) Audiences only increase.
  4. (25 points) $$$C \le 1000$$$, $$$N \le 1000$$$
  5. (40 points) No additional constraints.
Example
Input
2
120 3 5
9000 1000 15000
15 2 1 13000 3 8000
30 1 3 11000
45 2 1 9000 2 3500
60 1 1 14000
100 3 2 5000 1 13000 3 10000
90 3 2
0 0 100
30 2 1 100 3 0
60 2 1 0 2 100
Output
1 90
3 30
1 30
2 30
3 30
Note
  • $$$1 \le T \le 1000$$$
  • $$$1 \le D \le 10^9$$$
  • $$$1 \le C \le 2\cdot 10^5$$$
  • $$$0 \le N \le 2\cdot 10^5$$$
  • $$$1 \le c_i \le C$$$, $$$0 \le e_i \le 10^9$$$
  • In an update $$$c_i\ e_i$$$, the value $$$e_i$$$ is different from the audience of channel $$$c_i$$$ immediately before minute $$$m$$$. In Subtask 3, it is strictly greater.
  • There are no ties for the maximum audience at any minute.
  • The sum of $$$C$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.
  • The sum of all $$$u_i$$$ over all test cases does not exceed $$$3\cdot 10^5$$$.

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

Marisa has $$$n$$$ magic books placed on a shelf, all of them volumes from the same collection. Each book has an associated number within the collection. Initially, the book in position $$$i$$$ on the shelf is volume number $$$a_i$$$ of the collection, for $$$1\le i \le n$$$.

Since the magic books are very delicate, they can only be moved using the following operation. Two indices $$$1\le i \lt j \le n$$$ are chosen such that the volume numbers of the books in positions $$$i,i+1,\dots,j$$$ on the shelf are pairwise coprime$$$^{\text{∗}}$$$; and the order of the books in positions $$$i,i+1,\dots,j$$$ is reversed. That is, the book in position $$$i+r$$$ would move to position $$$j-r$$$ for each $$$0\le r \le j-i$$$.

Help Marisa decide if she can sort the books on the shelf using this operation as many times as she wants. We say that the books on the shelf are sorted if the volume numbers form a non-decreasing sequence from the book in position $$$1$$$ to the book in position $$$n$$$.

$$$^{\text{∗}}$$$We recall that two integers are coprime if their greatest common divisor is 1. We say that several numbers are pairwise coprime if any pair of them is coprime.

Input

The first line contains a positive integer $$$T$$$, the number of test cases that will follow.

Each test case starts with an integer $$$n$$$, the number of books on the shelf.

The next line contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$, where $$$a_i$$$ is the volume number of the book initially in position $$$i$$$. Note that $$$a_1,a_2,\dots,a_n$$$ do not have to be pairwise distinct.

Output

For each test case, print on one line the word "YES" when it is possible to sort the books, and the word "NO" when it is not possible.

Example
Input
4
4
6 1 1 1
5
5 4 3 2 1
5
5 2 3 4 1
4
2 2 6 3
Output
SI
NO
SI
NO
Note
  • $$$1 \le T \le 1000$$$
  • $$$1 \le n \le 10^5$$$
  • $$$1\le a_1, a_2, \dots, a_n \le 10^6$$$
  • The sum of $$$n$$$ over all cases will not exceed $$$2\cdot 10^5$$$.

E. Musical Fragments
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Martín has been digitizing his music collection for weeks. He has converted old records and recordings into a long list of numbered tracks, each labeled with a number indicating its musical style. Some tracks share a style; others are completely different. Martín boasts of having "a little bit of everything," although he suspects that he repeats more than he would like to admit.

While organizing the collection, he decides to analyze consecutive fragments of the list. A fragment of a list of $$$n$$$ elements is determined by two positions $$$l$$$ and $$$r$$$ such that $$$1 \le l \le r \le n$$$, and includes all tracks from the $$$l$$$-th to the $$$r$$$-th, both inclusive. For each fragment, Martín counts how many distinct styles appear in it.

He is particularly interested in those fragments that contain an odd number of different styles.

Given the sequence of styles of each collection, determine how many fragments satisfy this property.

Input

The first line contains an integer $$$T$$$, the number of test cases to process.

The first line of each case contains an integer $$$n$$$, the number of tracks in the collection.

The second line contains $$$n$$$ positive integers $$$a_1, a_2, \ldots, a_n$$$, where $$$a_i$$$ is the style of the $$$i$$$-th track.

Output

For each case, you must print a single line with an integer: the number of fragments whose number of distinct styles is odd.

Example
Input
2
3
1 2 3
5
1 1 1 1000000000 1
Output
4
8
Note
  • $$$1 \le T \le 10^5$$$
  • $$$1 \le n \le 10^5$$$
  • The sum of $$$n$$$ across all cases will be at most $$$10^5$$$.
  • $$$1 \le a_i \le 10^9$$$

F. Broken Line Operation
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

The Kronos Agency never leaves loose ends. After an internal leak, director Clara Voss suspects that part of her network of informants has been compromised. The organization consists of agents connected to each other through direct communication channels. By design, the network avoids redundancies: between any pair of agents, there exists a unique possible chain of contacts.

To contain the damage, Clara must activate exactly $$$k$$$ agents. The activated agents will receive a special protocol and will operate in enhanced undercover mode. The rest will remain inactive, under observation.

Each direct channel that connects an activated agent with one that is not activated becomes a critical point of cross-monitoring. These points allow for information verification and detection of possible betrayals. The more there are, the greater the internal control capacity.

Clara needs to decide which agents to activate so that the number of these critical channels is maximum.

Your task is to help her.

Input

The first line contains an integer $$$T$$$, the number of cases to process.

For each case:

  • The first line contains two integers $$$n$$$ and $$$k$$$: the number of agents in the network and the exact number of agents that must be activated.
  • The following $$$n-1$$$ lines contain two integers $$$u$$$ and $$$v$$$, indicating that there is a direct and bidirectional communication channel between agents $$$u$$$ and $$$v$$$.
It is guaranteed that the network is connected and contains no redundancies.
Output

For each case, print a single integer: the maximum number of direct channels that can connect an activated agent with a non-activated one, activating exactly $$$k$$$ agents.

Example
Input
3
3 2
1 2
2 3
5 2
1 2
1 3
1 4
1 5
2 0
1 2
Output
2
3
0
Note
  • $$$1 \le T \le 1000$$$
  • $$$2 \le n \le 2000$$$
  • $$$0 \le k \le n$$$
  • $$$1 \le u, v \le n$$$ and the graph is a tree.
  • The sum of $$$n$$$ over all cases does not exceed $$$2000$$$.