UTPC Contest 11-03-23 Div. 1 (Advanced)
C. An Odd Meal
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Eating jellyfish may seem like an odd meal to most of us. But Sally the sea turtle loves eating jellyfish for lunch. Today, her lunch will last for $$$N$$$ minutes. At minute $$$i$$$, Sally eats $$$j_i$$$ jellyfish.

Sally also likes odd numbers. Given the above details of her lunch, she wants you to find out the length of the longest contiguous time interval where the total number of jellyfish she ate during that interval sums to an odd number (if possible).

Input

The first line of input contains $$$N$$$ $$$(1 \leq N \leq 2 \cdot 10^5)$$$. The second line of input contains $$$N$$$ space separated integers denoting $$$j_i$$$ $$$(0 \leq j_i \leq 10^9)$$$.

Output

Please output 1 integer, the length of the longest contiguous time interval where the total number of jellyfish eaten during that interval sums to an odd number.

If it is impossible to find such an interval, output -1.

Examples
Input
7
4 6 8 3 2 12 5
Output
6
Input
2
0 1
Output
2
Input
4
100 200 300 400
Output
-1

D. Jelly Swarm
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Jerry the jellyfish wants to join his $$$N$$$ friends as they swim around the ocean ($$$1 \leq N \leq 2*10^5$$$). Jerry's favorite number is $$$K$$$, so he wants to join a swarm of exactly $$$K$$$ of his friends ($$$1 \leq K \leq N$$$). Each of his friends are located at an integer position of a one-dimensional ocean. More specifically, the $$$i$$$th jellyfish is located at position $$$a_i$$$. The jellyfish are all located at distinct positions. Jerry prefers tightly packed groups of jellyfish, so he wants to minimize the maximum distance between any two jellyfish in the swarm. Jerry is willing to move anywhere to be with his friends, but unfortunately his friends are too stubborn and will not move. Please help jerry find the maximum distance between any two jellyfish if he chooses a group optimally.

Input

The first line contains two integers $$$N$$$ and $$$K$$$. ($$$1 \leq K \leq N \leq 2*10^5$$$) The next line contains $$$N$$$ space-separated integers $$$a_{1...N}$$$, where $$$a_i$$$ denotes the position of Jerry's $$$i$$$th friend. ($$$1 \leq a_i \leq 10^9$$$) Note that these positions are distinct.

Output

Output an integer representing the smallest maximum distance between any two jellyfish.

Examples
Input
5 3
2 8 6 15 5
Output
3
Input
7 4
1 2 4 5 6 7 9
Output
4
Note

In the first sample, Jerry could chose the group $$$\{8, 6, 5\}$$$, and can locate himself at position $$$7$$$, making the maximum distance between any two Jellyfish equal to $$$3$$$.

In the second sample, even though the group $$$\{4, 5, 6, 7\}$$$ has a maximum distance of $$$3$$$, Jerry cannot occupy the same space as any of his friends so he must go to either position $$$3$$$ or $$$8$$$.

E. Seacave Jellyfish
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Ao Run, the white dragon among the Dragons of Four Seas and the King of the West Seas (don't ask me which sea that is), has identified an elaborate network of seacaves, labelled $$$1, \dots, n$$$, that is connected by exactly $$$n-1$$$ bidirectional pathways, represented by the starting and ending seacaves, as well as the amount of energy it takes for him to traverse through that pathway —- all hidden from human intervention in the form of submarines, undersea cables, and other activities that Ao Run views as nuisances. Importantly, the King notices that every cave is reachable from every other cave.

As an avid enjoyer of jellyfish, the King is also flattered to discover that seacave $$$i$$$ contains $$$c_i$$$ units of jellyfish that he can engage with. But the King is also lazy —- his interest in engaging with the jellyfish is hindered by the amount of energy he must spend to reach these jellyfish. As a result, the total engagement he'll get from the jellyfish from cave $$$x$$$ after traveling from cave $$$y$$$ is evaluated by $$$\dfrac{c_x}{dist(x, y) + 1}$$$, where $$$dist(x, y)$$$ is the minimal amount of energy to traverse from cave $$$x$$$ to $$$y$$$ using the pathways, and $$$1$$$ is the energy that the King needs to engage with the jellyfish.

The King, however, still intends to engage with jellyfish from every cave; to do so, he wants to establish a base that maximizes the total engagement —- so you, the King's special advisor, must find the cave such that maximizes the sum of engagement from that cave to all caves (including the current cave), as well as that sum of engagement. Importantly, you may treat the King's engagements as separate - he will engage with the $$$n$$$ seacaves of jellyfish separately.

Input

The first line will consist of one integer, $$$n$$$ ($$$2\leq n \leq 100$$$).

The second line will consist of $$$n$$$ integers, $$$c_i$$$ ($$$1\leq i \leq n$$$, $$$0\leq c_i \leq 10^9$$$).

For each of the next $$$n-1$$$ lines, the following: $$$x$$$, $$$y$$$, $$$w$$$, denoting a hidden bidirectional pathway between caves $$$x$$$ and $$$y$$$, with a traversal energy of $$$w$$$ ($$$1\leq x, y \leq n$$$, $$$1\leq w\leq 10^3$$$)

Output

Two lines. The first line contains a single integer, the 1-based index of the seacave that maximizes the sum of engagement from the cave to all caves.

The second line contains the total engagement gained by engaging with jellyfish from all seacaves when the King is based in the seacave you printed in the last line, rounded to 5 digits after the decimal. The judging system will accept answers within $$$10^{-4}$$$ from the correct solution.

Example
Input
5
5 2 9 1 7
1 2 2
1 3 2
3 4 1
3 5 3
Output
3
13.31667
Note

In the sample, when the king is based in seacave 3, he can:

- engage with $$$9$$$ units of jellyfish in seacave $$$3$$$ using $$$1$$$ energy, for an engagement gain of $$$\dfrac{9}{1} = 9$$$;

- engage with $$$5$$$ units of jellyfish in seacave $$$1$$$ using $$$3$$$ energy ($$$2$$$ for getting from seacave $$$3$$$ to $$$1$$$, $$$1$$$ for the engagement itself), for an engagement gain of $$$\dfrac{5}{2+1} = \dfrac{5}{3}$$$;

- engage with $$$2$$$ units of jellyfish in seacave $$$2$$$ using $$$2+2+1=5$$$ energy, for an engagement gain of $$$\dfrac{2}{5} = 0.4$$$;

- engage with $$$7$$$ units of jellyfish in seacave $$$5$$$ using $$$4$$$ energy, for an engagement gain of $$$\dfrac{7}{4} = 1.75$$$;

- engage with $$$1$$$ units of jellyfish in seacave $$$4$$$ using $$$2$$$ energy, for an engagement gain of $$$\dfrac{1}{2} = 0.5$$$;

For a total engagement that sums up to $$$\dfrac{799}{60}$$$, or $$$13.31667$$$ when rounded.

It can be shown that this is the maximum engagement attainable in this arrangement of seacaves and paths.

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

Yolanda frequently goes shopping at a jellyfish-themed shop on a bustling oceanfront promenade. This week is the Jellyfish Lantern Festival, and she is excited to buy a few gifts for her friends.

There are $$$N$$$ items at the shop, labeled 1 to $$$N$$$. For the next 10 days, labeled from 1 to 10, you are given the stock of the items, $$$F$$$, where $$$F_{i,j} = 1$$$ if item $$$i$$$ is in stock on day $$$j$$$ and $$$F_{i,j} = 0$$$ if it is out of stock on day $$$j$$$. Note that $$$1 \leq i \leq N$$$ and $$$1 \leq j \leq 10$$$.

Let $$$c_i$$$ be the number of days during which item $$$i$$$ is in stock and Yolanda visits the store. To evaluate her selections, Yolanda applies a unique strategy. For integers $$$a$$$ and $$$b$$$, the beauty is equal to the output of $$$XOR\_range(a,b)$$$ where $$$XOR\_range(a,b)$$$ calculates the exclusive OR of the numbers between $$$a$$$ and $$$b$$$ inclusive. Given the array $$$P$$$, Yolanda has decided that the total beauty of all her purchases will be $$$XOR\_range(P_{1}, P_{c_1}) + XOR\_range(P_{2},P_{c_2}) + \cdots + XOR\_range(P_{N},P_{c_N})$$$.

On each day, Yolanda decides whether or not she will visit the shop. Find the maximum possible beauty of Yolanda's purchase when she decides whether to visit the shop on each of the 10 days.

Input

The first line has an integer $$$N$$$ for $$$(1\leq N \leq 100)$$$.

The next $$$N$$$ lines contain the array $$$F$$$ where $$$0 \leq F_{i,j} \leq 1$$$,

$$$F_{1,1} \: F_{1,2} \: \cdots \: F_{1,10}$$$

$$$\vdots$$$

$$$F_{N,1} \: F_{N,2} \: \cdots \: F_{N,10}$$$

The next line contains the array $$$P$$$ where $$$0 \leq P_{i,j} \leq 10^9$$$,

$$$P_{0} \: \cdots \: P_{\max\{10,N\}}$$$

Output

Please print the maximum possible beauty of Yolanda's purchases.

Examples
Input
1
0 0 0 1 1 1 0 1 0 1
0 3 0 0 0 8 0 0 0 0 0
Output
11
Input
2
1 1 1 1 1 0 0 0 0 0
0 0 0 0 0 1 1 1 1 1
0 10 9 8 7 6 5 4 3 2 1
Output
21
Note

In the first test sample, it would be optimal for Yolanda to visit the first shop on all the days where the item is in stock. Then the answer is $$$XOR\_range(P_1, P_5) = XOR\_range(3, 8) = 11$$$.

In the second sample, note the arguments of $$$XOR\_range$$$ may be unordered.

G. Genome Splicing
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Spunch Bob has big dreams for the jellyfishing competition coming up. In this competition, jellyfishers show off their best catch to be judged by the audience.

Plankton has a sneaky plan to win this competition. Instead of catching a jellyfish, he decides he can just make one. In particular, since he knows what aspects of a jellyfish (transparency, size, number of tentacles) are preferred, he plans to splice together the DNA of existing jellyfish in order to create an award-winning jellyfish.

This process works as follows. Plankton has a string consisting of the uppercase letters "A, T, C, G", representing the desired genome of the award-winning jellyfish.

Plankton also has segments of DNA recovered from other jellyfish, also represented as strings with the letters "A, T, C, G." These segments can be concatenated together to form longer strands of DNA; furthermore, any segment can be used as many times as desired.

Plankton wants to know: what is the minimum number of segments required to build the desired genome (the concatenated segments must match the genome exactly)?

Furthermore, Plankton has an additional restriction: he knows it will look suspicious if the same segment of DNA is used twice in a row, i.e., the same segment is concatenated to itself with nothing in between. What is the minimum number of segments required to build the desired genome subject to this restriction?

Input

The first line contains a single integer $$$N$$$, denoting the number of segments. ($$$1 \le N \le 10^3$$$)

The second line contains a single string $$$G$$$ ($$$1 \le |G| \le 10^3$$$), representing the desired genome.

The next $$$N$$$ lines each contain a single string $$$s_i$$$ ($$$1 \le |s_i| \le 10^3$$$), representing the component segments. It is guaranteed that all segments will be distinct.

All segments and the genome will consist of only the uppercase letters "A, T, C, G".

Output

Output a single integer: the minimum number of segments required to match the desired genome exactly, or -1 if it is not possible.

Examples
Input
6
ATTACAGA
AT
TA
T
ACAGA
C
AGA
Output
3
Input
6
ATTTACAGACA
AT
TTA
T
ACAGACA
CA
GA
Output
5
Input
1
ACTG
A
Output
-1

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

For a nice weekend vacation, you decided to take a trip to the aquarium. There, you saw $$$n$$$ jellyfish, and you noticed a specific pattern in the number of tentacles they had. The first jellyfish you saw had $$$a_1$$$ tentacles. Surprisingly, the $$$i$$$th jellyfish had $$$a_i = (a_1 \cdot a_2 \cdots a_{i - 2} \cdot a_{i - 1}) \cdot p_i$$$ tentacles, where $$$p_i$$$ is the smallest prime that does not divide $$$a_1 \cdot a_2 \cdots a_{i - 2} \cdot a_{i - 1}$$$!

You also notice that a jellyfish's popularity is defined by how many sizes you can divide the number of tentacles by. More formally, if a jellyfish has $$$m$$$ tentacles, then their popularity score is the number of divisors of $$$m$$$. You want to find out, what is the maximum popularity score of all the jellyfish that you saw? Because the answer may be large, output it mod $$$998244353$$$.

Input

The first line contains two integers $$$n$$$ and $$$a_1$$$ ($$$1 \leq n, a_1 \leq 10^5$$$) — the number of jellyfish and the number of tentacles the first jellyfish has.

Output

Output one integer — the maximum number of divisors any jellyfish has, mod $$$998244353$$$.

Examples
Input
4 9
Output
108
Input
1234 9876
Output
882891106
Note

In the first sample:

  • $$$a_1 = 9$$$
  • The smallest prime not a factor of $$$a_1$$$ is 2, so $$$a_2 = (9) \cdot 2 = 18$$$.
  • The smallest prime not a factor of $$$a_1 \cdot a_2$$$ is 5, so $$$a_3 = (9 \cdot 18) \cdot 5 = 810$$$.
  • The smallest prime not a factor of $$$a_1 \cdot a_2 \cdot a_3$$$ is 7, so $$$a_4 = (9 \cdot 18 \cdot 810) \cdot 7 = 918,540$$$.

Each of these have $$$3$$$, $$$6$$$, $$$20$$$, and $$$108$$$ factors respectively, so the answer is $$$108$$$.

Note that you want the mod of the maximum, not the maximum after taking the mod of the number of tentacles each jellyfish has.

I. Deep Sea Navigation
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Rock and his crew are currently searching the deep sea (which can be represented by a $$$n$$$ by $$$m$$$ grid) for treasure in a shipwreck. They already know where the shipwreck is, but moving through the deep sea is not trivial. To navigate the deep sea, they need to use a submarine that uses special batteries. A battery of power $$$x$$$ allows their submarine to move up to $$$x$$$ cells in one go. They can only move in the 4 cardinal directions. For example, with a battery of power 2, they could move once to the right, twice to the right, once to the right and once upwards, etc... Once the submarine stops after moving up to $$$x$$$ cells, they must replace the battery with a new battery (and cannot reuse the old one).

Additionally, the deep sea is filled with $$$y$$$ swarms of mysterious jellyfish which occupy specific locations. These jellyfish don't usually pose a problem, but if Rock and his crew are stationary (such as when they are replacing the battery) in a location with jellyfish, the jellyfish will swarm together and move the submarine to another location. Note that the crew can always replace the battery within the amount of time a jellyfish swarm takes to move them, and if there is a jellyfish swarm at the location they are moved to, they can choose to remain stationary (and get moved again by jellyfish) or move up to $$$x$$$ cells using their new battery. Given the starting location of the submarine, the location of the shipwreck, the power of the batteries, and knowledge of the locations and behaviors of the jellyfish swarms, help Rock compute the least number of batteries needed in order to reach the shipwreck.

Input

The first line contains 4 space separate integers: $$$n$$$, the number of rows in the sea, $$$m$$$, the number of columns in the sea ($$$2 \leq n * m \leq 10^6$$$), $$$x$$$, the power of the batteries ($$$1\leq x \leq 10^6$$$), and $$$y$$$, the number of jellyfish swarms ($$$0\leq y \leq n * m - 2$$$). The next line contains $$$a$$$ and $$$b$$$, the starting row and column of the submarine respectively, and $$$c$$$ and $$$d$$$, the row and column of the shipwreck respectively. Finally, the next $$$y$$$ lines each contain four space separated integers: $$$r_1$$$, $$$c_1$$$, $$$r_2$$$, and $$$c_2$$$. $$$r_1$$$ and $$$c_1$$$ represent the row and column of a jellyfish swarm, and $$$r_2$$$ and $$$c_2$$$ represents a separate location the jellyfish swarm will move the submarine to if it stops in ($$$r_1$$$, $$$c_1$$$). Note that there are no jellyfish at both the starting location and the shipwreck, and that there cannot be two jellyfish swarms in one location. Additionally, note that all row and column locations are 0-indexed (given location ($$$r,c$$$), $$$0\leq r \lt n$$$ and $$$0\leq c \lt m$$$).

Output

Output an integer representing the minimum number of batteries required to reach the shipwreck from the starting location, or -1 if it is not possible to reach the shipwreck.

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

J. Seaside Streaming
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

On a serene seaside, jellyfish communicate with the shore using unique pulsating signals. These signals are of two types:

  • A Type 0 signal represents a jellyfish sending a pulsation intensity of value $$$v (0\leq v\leq 10^9)$$$ from a specific location $$$x (1\leq x\leq 10^9)$$$ in the sea. Note that a pulsation with intensity $$$0$$$ still counts as a pulsation.
  • A Type 1 signal is a call from the marine researchers on the shore. They want to detect sequences of jellyfish pulsations within a specific section of the sea, defined by the interval $$$[l, r] (1 \leq l \leq r \leq 10^9)$$$. Formally, a luminous dance is a sequence of pulsations that is continuous and has an intensity of $$$$$$\sum_{x \in [i, j]} v_x$$$$$$ if Type 0 signals have been sent from all points in $$$[i, j]$$$ and no pulsations were detected at point $$$i-1$$$ and point $$$j+1$$$. Researchers want to know how many luminous dances are completely contained in the given range, and what the total intensity of all these dances is. If no such luminous dance can be found in the specified section, the researchers note a value of $$$-1$$$ for both values.
Input

The first line contains $$$N (1\leq N\leq 2\cdot 10^5)$$$, the number of jellyfish signals received by the shore.

The next $$$N$$$ lines describe each of these signals:

  • 0 x v - This represents a Type 0 signal, where a jellyfish at location $$$x$$$ in the sea sends a pulsation with intensity $$$v$$$.
  • 1 l r - This represents a Type 1 signal, where the marine researchers wish to decode the sum of all continuous sequence of jellyfish pulsations between the sea locations $$$l$$$ and $$$r$$$, and the number of those sequences.

It's also guaranteed that all $$$x$$$ are distinct.

Output

For each type 1 query, print the answer on a new line. Print the number of continuous luminous dances, followed by a space, and then the intensity (sum) of all the luminuous dance intensities that are continuous for the interval $$$[l, r]$$$.

Examples
Input
6
0 1 2
1 1 4
0 3 4
1 1 4
0 2 3
1 1 4
Output
1 2
2 6
1 9
Input
3
0 1 1
0 2 1
1 1 1
Output
-1 -1
Input
10
0 10 68
1 3 9
1 3 4
0 3 9
1 1 8
0 4 70
0 9 35
1 1 8
0 2 55
0 1 1
Output
-1 -1
-1 -1
1 9
1 79
Note

For the first sample, let's denote the first 5 elements by index [1, 2, 3, 4, 5]. Then, the state after each 0 query will be:

  1. [2, 0, 0, 0, 0]
  2. [2, 0, 4, 0, 0]
  3. [2, 3, 4, 0, 0]

For the first query, we can see that there is one dance with intensity 2, so we print out 1 2

For the second query, we can see that there are two dances with total intensity 6, so we print out 2 6

For the third query, since dance $$$[2, 3, 4]$$$ is fully contained, but now there is one continuous dance, so we print 1 9