UTPC Contest 2-12-25 Div. 1 (Advanced)
C. Finchy Flying
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Darwin has been observing finches flying around the Galapagos Islands, and it is now mating season. For mating, the finches exhibit an interesting behavior: $$$n$$$ male finches will fly straight up and come back straight down as a flight display. The $$$i$$$th finsh starts at a horizontal location $$$l_i$$$ ($$$l_i$$$ can be negative) and reaches a height of $$$h_i$$$. Female finches will then fly to where the male landed and fan their tails to signal acceptance.

The wind will naturally affect where the male finch lands. There are $$$m$$$ jetstreams currently above the Galapagos. The $$$j$$$th jetstream is located at altitude $$$a_j$$$ and blows any finches at this height by $$$w_j$$$ units to the right ($$$w_j$$$ can be negative, blowing finches to the left). Male finches that go past a jetstream will be blown over both going up and coming down, while those peaking at the jetstream altitude will only be blown over once.

Natural female finches are adapted to adjusting for wind when locating the males, but Darwin rescued a baby finch that he will be releasing soon, and he needs to train this finch. Please provide the landing locations of each of the male finches that Darwin can communicate to his baby finch (don't worry about how, he's a trained scientist).

Input

The first line contains $$$n$$$ $$$(1 \leq n \leq 10^5)$$$, the number of male finches, and $$$m$$$ $$$(0 \leq m \leq 10^5)$$$, the number of jetstreams.

Each of the next $$$n$$$ lines contain two integers $$$l_i$$$ and $$$h_i$$$ ($$$0 \leq |l_i|, h_i \leq 10^9$$$) – the starting location and max altitude of the $$$i$$$th finch.

Each of the next $$$m$$$ lines contain two integers $$$a_j$$$ and $$$w_j$$$ ($$$0 \leq a_j, |w_j| \leq 10^9$$$) — the altitude and strength of the $$$j$$$th jetstream.

Output

Output one line containing the landing positions of each of the $$$n$$$ male finches in order.

Example
Input
3 1
5 2
2 4
-2 6
4 2
Output
5 4 2

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

Darwin is collecting samples at the Galapagos Islands to bring back Europe. He'd like to bring back the whole island for his research, but the Beagle has limited space!

He's choosing from $$$n\ (1 \leq n \leq 10^4)$$$ samples, each sample $$$i\ (1 \leq i \leq n)$$$ has:

  • a weight $$$w_i\ (1 \leq w_i \leq 100)$$$ in kg
  • relative research value $$$v_i\ (1 \leq v_i \leq 10^5)$$$

The Beagle has room for $$$m\ (0 \leq m \leq 100)$$$ kg in its main cargo hold, and features a special hold that can accommodate one item of any weight without counting towards the cargo limit.

Please output the max total research value that Darwin can bring back to the mainland.

Input

The first line will contain two integers $$$n\ (1 \leq n \leq 10^4)$$$ and $$$m\ (0 \leq m \leq 100)$$$ — the number of samples.

The next $$$n$$$ lines will contain two integers $$$w_i\ (1 \leq w_i \leq 100)$$$ and $$$v_i\ (1 \leq v_i \leq 10^5)$$$ — the weight and relative research value for each sample.

Output

A single integer that is the max total research value the beagle can carry.

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

E. Finch Sanctuaries
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Darwin is currently researching various traits of his $$$n$$$ finches that are each currently stored in their own sanctuary. He is trying to understand which finches might be evolutionarily related, so he wants to group them together based on common traits. Specifically, Darwin cares about $$$k$$$ traits of these finches, and has labeled every variant of each trait with a letter between 'a' and 'j'. There is a lot of coordination to be done in moving these finches around so Darwin needs your help processing and keeping track of all the information. Specifically, there are three types of queries he can request of you:

  1. Since he discovered that trait $$$j$$$ is a key indicator of genetic similarity, combine any groups with finches which share a value of this trait.
  2. Compute how many birds are currently in Finch $$$i$$$'s sanctuary (including Finch $$$i$$$ itself)?
  3. Compute how many birds are in the most populated sanctuary?
Input

The first line contains three integers $$$n$$$, $$$k$$$, and $$$q$$$. ($$$1 \leq n, k, q \leq 10^5, nk \leq 10^6$$$) — the number of birds, the number of traits, and the number of queries, respectively.

The next $$$n$$$ lines contain a string $$$s_i$$$ ($$$|s_i| = k$$$) — the values of the $$$k$$$ traits of the bird, respectively. Every trait value is a character between 'a' and 'j'.

The next $$$q$$$ lines contain a description of the corresponding query. The line begins with an integer $$$t$$$ ($$$t \in \{1, 2, 3\}$$$.

  • If $$$t = 1$$$, then the line contains another integer $$$j$$$ ($$$1 \leq j \leq k$$$) — the trait which finches should now also be grouped by.
  • If $$$t = 2$$$, then the line contains another integer $$$i$$$ ($$$1 \leq i \leq n$$$) — the finch which the second query should be performed on.
  • If $$$t = 3$$$, then there is nothing else on the line.

It is guaranteed that there is at least one query of type two or three. Note that queries of type 1 may be repeated.

Output

Output the answers for the second and third queries in order on their own lines.

Example
Input
4 5 14
abcdj
acdei
bcffh
bffgg
2 4
3
1 3
2 3
2 1
3
1 1
2 3
2 1
3
1 2
2 3
2 1
3
Output
1
1
2
1
2
2
2
2
4
4
4

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

While in the Galapagos Islands, Darwin noticed a curious fact about the birds on the island. Each bird's beak length and wingspan add up to the same number $$$k$$$. There are $$$n$$$ resources on the island, each with some value $$$v$$$. The $$$i$$$th resource requires a wingspan of at least $$$w_i$$$ and a beak length of at least $$$b_i$$$ to reach. Darwin is curious about the best bird adapted to the environment. Find the maximum possible sum of resource values that is reachable by a bird with beak length and wingspan that adds up to $$$k$$$.

Input

The first line contains two integers $$$n$$$ ($$$1 \leq n \leq 10^5$$$) and $$$k$$$ ($$$1 \leq k \leq 10^5$$$) — the number of resources and the sum of each bird's beak length and wingspan.

The next line contains $$$n$$$ integers, each representing the beak length $$$b_i$$$ ($$$1 \leq b_i \leq 10^5$$$) required to access the $$$i$$$th resource.

The next line contains $$$n$$$ integers, each representing the wingspan $$$w_i$$$ ($$$1 \leq w_i \leq 10^5$$$) required to access the $$$i$$$th resource.

The last line contains $$$n$$$ integers, each representing the value $$$v_i$$$ ($$$1 \leq v_i \leq 10^5$$$) of the $$$i$$$th resource.

Output

Output a single integer — the maximum sum of resource values that can be acquired by a bird with a beak length and wingspan adding up to $$$k$$$.

Example
Input
5 6
2 2 3 3 4
5 4 2 2 1
3 2 4 5 2
Output
11
Note

One possible best bird has a beak length of 4 and a wingspan of 2. It can access the 3rd, 4th, and 5th resource, for a total sum of 11. It can be shown that this is the maximum.

G. Galapagos
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Charles Darwin has made it to the Galapagos Islands, and is observing turtles - more specifically, there are $$$n$$$ ($$$1 \leq n \leq 200,000$$$) turtles with their nests (these turtles have nests) lined up in a row. They all lay an integer number of eggs; the $$$i$$$'th turtle's nest has $$$a_i$$$ ($$$0 \leq a_i \leq 10^9$$$) eggs. He also observes diversity in that no 2 turtles lay the same number of eggs. Darwin likes things to be ordered and is therefore displeased that the nests are not sorted in increasing order. He is allowed to do the following operation - he can choose $$$a_i, a_{i+1}, a_{i+2}$$$ and reorder them to be $$$a_{i+2}, a_i, a_{i+1}$$$ in place. Determine whether it is possible for Darwin to obtain a sorted row of nests (in increasing order) by doing this operation any number of times.

Input

The first line will contain an integer $$$n$$$. The next line contains $$$n$$$ space separated integers $$$a_1, a_2 \cdots a_n$$$.

Output

Output a single bit - $$$1$$$ if it is possible for Darwin to sort the nests, and $$$0$$$ if it is not.

Examples
Input
3
3 1 2
Output
1
Input
4
1 2 4 3
Output
0

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

Dr. Prakash recently learned about how the human brain evolved a marvelous ability to form, prune, and reshape connections between neurons. (He should have learned this awhile ago in medical school, but Dr. Prakash isn't the best medical student, or medical doctor for that matter.)

He would like to test this himself by performing some basic neurectomies on his victim patient and observing the results. He did receive consent to do this (like many of us, his patient did not read all the fine print before signing), but the medical board is still very much on his case due to the outcomes of his previous patients. As such, Dr. Prakash wants to avoid killing his patient (again), which happens if part of the brain becomes totally disconnected and unable to communicate with another part of the brain (a full lobotomy).

Dr. Prakash will make a single cut. Please help him identify which neurons he should definitely avoid with this cut if he wishes to keep his medical license (at least until the next ethics hearing).

Input

The first line contains $$$n$$$ $$$(2 \leq n \leq m + 1)$$$ and $$$m$$$ $$$(1 \leq m \leq 2 * 10^5)$$$, the number of neurons representing the patient's brain, and the number of connections/synapses between neurons.

The next $$$m$$$ lines contain $$$i_m$$$ $$$(0 \leq i_m \lt 2^{32})$$$, a unique integer identifier for the synapse, and $$$n_1$$$ and $$$n_2$$$ $$$(0 \leq n_1, n_2 \lt n)$$$, denoting the two neurons that are connected. Please note that a pair of neurons may be connected by multiple synapses, and that $$$n1$$$ may equal $$$n2$$$.

It is guaranteed that the brain is connected at the start.

Output

Print a single line of a sorted list of synapse identifiers that, if cut, will cause a brain partition. If there are none, print -1.

Examples
Input
4 4
212 3 0
238 1 2
394 2 0
281 0 1
Output
212
Input
3 3
101 0 1
102 0 2
103 2 1
Output
-1

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

After studying evolution for years, Charles Darwin stumbled upon a new archipelago: The Palagapos. He is especially fascinated by the species of turtles native to the island, and has been monitoring the DNA of the turtles on the islands.

For simplicity, a strand of DNA can be represented as an array of length $$$n$$$ containing integers ranging from $$$1$$$ to $$$k$$$. Let $$$a$$$ be a strand of DNA. A mutation of $$$a$$$ is an operation that consists of the following steps:

  • Select an index $$$i$$$ such that $$$1 \leq i \leq n$$$ and $$$a_i \lt k$$$.
  • Set $$$a_i \gets a_i + 1$$$.

Now, for DNA strands $$$a$$$ and $$$b$$$, define the function $$$f(a, b)$$$ to be the maximum number of mutations that could be applied to $$$a$$$ until $$$b$$$ is not lexicographically larger than $$$a$$$ for the first time.

Darwin wants to know the sum of $$$f(a[i,j], b[i,j])$$$ for all $$$1 \leq i \leq j \leq n$$$, where $$$a[i,j]$$$ represents the subarray of $$$a$$$ consisting of the elements $$$a_i, a_{i+1}, ..., a_{j}$$$. Please help Darwin!

Input

The first line of input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq k \leq 10^9$$$) — denoting the length of the DNA sequences and the upper bound on the range of values in the sequences, respectively. The second line contains $$$n$$$ space-separated integers $$$a_1, a_2, ... a_n$$$ ($$$1 \leq a_i \leq k$$$) — denoting the values in Darwin's first DNA sequence. The third line contains $$$n$$$ space-separated integers $$$b_1, b_2, ... b_n$$$ ($$$1 \leq b_i \leq k$$$) — denoting the values in Darwin's second DNA sequence.

Output

Output a single integer, denoting the sum that Darwin wants to know. Since this value can be quite large, output it modulo the prime $$$998244353$$$.

Examples
Input
2 3
2 1
2 2
Output
2
Input
3 4
1 2 2
3 4 1
Output
18

J. Barnacle Game
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Darwin's biggest rival, Wallace, has challenged him to a game to determine who is the real Father of Evolution!

Being the one challenged, Darwin gets to pick the format, and so he chooses his specialty: barnacles. A barnacle can be represented as a set of $$$n$$$ segments connected together by $$$n-1$$$ ligaments with no cycles. In other words, a barnacle is a tree where segments are nodes and ligaments are edges.

The game that Darwin proposes is as follows:

  • The players alternate taking turns, with Darwin going first.
  • On the current player's turn, they will choose one ligament of the remaining barnacle and cut it.
  • Then, the other player will choose one connected component of the barnacle to keep after the cut, and discard the rest of the barnacle. This concludes the turn, and roles swap for the next round.

When a player must cut a ligament and there are no ligaments in the remaining barnacle left to cut, that player loses.

Wallace has just brought in the barnacle they will play the game on, but Darwin is not sure if he wins under optimal play from both players. Please help Darwin determine if he can win the game and keep his title as the Father of Evolution!

Input

The first line of input will contain an integer $$$n\ (1\leq n\leq 5000)$$$ — the number of segments of the barnacle.

The next $$$n-1$$$ lines will contain two integers $$$u$$$ and $$$v\ (1\leq u,v\leq n)$$$ — indicating there is a ligament between segments $$$u$$$ and $$$v$$$.

It is guaranteed the given segments form a tree.

Output

Print "I am Darwinning!" (without quotes) if Darwin wins under optimal play, or "I lost the game." (without quotes) if Wallace wins.

Examples
Input
3
1 2
2 3
Output
I lost the game.
Input
8
1 2
1 3
3 4
3 5
3 6
6 7
7 8
Output
I am Darwinning!
Note

In the first test, if Darwin cuts the 1-2 ligament, the barnacle will be split into two components {1} and {2,3}. Then, Wallace can choose the {2,3} component to keep. After Wallace cuts the 2-3 ligament, splitting the barnacle into {2} and {3}, regardless of which component Darwin chooses to keep, there will be no more ligaments for him to cut on his turn, meaning he loses. It can be shown that Darwin also loses if he starts by cutting the 2-3 ligament, so there is no way for Darwin to win.