ICPC 2021

Time limit: 5 seconds

You are part of a scientific team developing a new technique to image crystal structures at the molecular level. The technique involves blowing a very fine wind over the surface of the crystal at various angles to detect boundaries (indicated by molecules that are exposed to the wind). This is repeated with different wind directions and the boundaries observed for each direction are recorded. Your team has already collected the data, but – as is often the case with applied science – now the real work, analysis, must begin.

For a given crystal, you will receive the directions in which wind blew over the surface, and the locations of all boundaries encountered by each of these winds. For a wind blowing in direction $(w_{x}, w_{y})$, a boundary is defined as a location $(x, y)$ such that a molecule exists at $(x, y)$ and no molecule exists at $(x- w_{x}, y- w_{y})$. Note that for technical reasons $w_{x}$ and $w_{y}$ are not necessarily relatively prime.

The data might not uniquely determine the structure of the crystal. You must find the two unique struc- tures with the minimal and maximal number of molecules consistent with the observations.

For example, in the first sample input, nine different molecules are directly encountered by the given winds. There must be a molecule at location $(3,3)$ because otherwise $(4,2)$ would be a boundary for the third wind. For similar reasons, there must be molecules at $(4,4)$ and $(5,5)$. There cannot be any further molecules as they would result in additional observations for some of the winds.

Input

The first line of input contains three integers $d_{x}$, $d_{y}$, and $k$, where $d_{x}$ and $d_{y}$ ($1 \le dx, dy \le 10^{3}$) are the maximum dimensions of the crystal structure, and $k$ ($1\le k \le 10$) is the number of times wind was blown over the crystal.

Each of the remaining $k$ lines specifies the data for one wind. These lines each start with two integers $w_{x}$ and $w_{y}$ ($- dx \le wx \le dx$ and $- dy \le wy \le dy$, but not both zero) denoting the direction of the wind. Then comes an integer $b$ ($0\le b\le 10^{5}$) giving the number of boundaries encountered by this wind. The line finishes with $b$ distinct pairs of integers $x, y$ ($1 \le x \le d_{x}$ and $1 \le y \le d_{y}$) listing each observed boundary.

You may assume the input is consistent with at least one crystal and that no molecules exist outside the specified dimensions.

Output

Output two textual representations of the crystal structure separated by an empty line. Each structure has $d_{y}$ rows of $d_{x}$ characters, with the top-left corner corresponding to location $(1,1)$. The first is the structure with the minimal number of molecules consistent with the observations, the second is the maximal one. Use ‘#’ for a location where a molecule exists and ‘.’ for a location where no molecule exists.

ICPC World Finals 2021 Problem A: Crystal Crosswind

Sample Input 1

6 6 3
1 1 3 3 1 1 3 2 2
0 2 6 3 1 1 3 2 2 6 4 5 3 4 2
1 -1 4 1 3 2 4 3 5 4 6

Sample Output 1

..#...
.#.#..
#.#.#.
.#.#.#
..#.#.
...#..
..#...
.#.#..
#.#.#.
.#.#.#
..#.#.
...#..

Sample Input 2

5 4 2
1 0 6 1 1 4 1 2 2 5 2 2 3 3 4
0 -1 7 1 1 4 1 5 2 2 3 3 4 4 4 5 4

Sample Output 2

#..#.
.#..#
.#...
..###
##.##
.##.#
.###.
..###

ICPC World Finals 2021 Problem A: Crystal Crosswind

Time limit: 5 seconds

The helix key Image generated by DALL-E Alice and Bob are in charge of testing a new escape room! In this escape room, customers are trapped in a dungeon and have to explore the entire area. The dungeon consists of $n$ rooms connected by exactly $n- 1$ corridors. It is possible to travel between any pair of rooms using these corridors.

Two of the dungeon rooms are special. One of these rooms contains a pro- tective idol known as the “helix key.” A different room contains a nasty “dome trap,” which prevents the player from moving once activated. Enter- ing the room with the trap before acquiring the key will result in the player being trapped in the dungeon forever. The player cannot start in the same room as the key or the trap.

There are $q$ different scenarios that Alice and Bob wish to examine. In the $i$th scenario, the player starts in room $s_{i}$, the key is in room $k_{i}$, and the trap is in room $t_{i}$. For each scenario, compute the minimum amount of time needed to explore the entire dungeon without getting trapped.

Input

The first line of input contains two integers $n$ and $q$, where $n$ ($3 \le n \le 2 000$) is the number of rooms and $q$ ($1\le q \le 200 000$) is the number of scenarios to consider. Rooms are numbered from $1$ to $n$. The next $n- 1$ lines each contain three integers $u$, $v$, and $w$ indicating that there is a corridor between rooms $u$ and $v$ ($1\le u, v \le n, u=v$) that takes time $w$ ($1\le w \le 10^{9}$) to traverse.

Then follow $q$ lines: the $i$th of these lines contains three distinct integers $s_{i}$, $k_{i}$, and $t_{i}$ ($1 \le si, ki, ti \le$ $n$) indicating the room where the player starts, the room with the key, and the room with the trap, respectively.

Output

For each scenario, output the minimum amount of time needed to visit every room at least once. If it is impossible to visit every room at least once, output impossible.

Sample Input 1

5 4
1 2 3
1 3 1
3 4 4
3 5 2
1 2 4
1 4 2
5 2 1
4 3 1

Sample Output 1

15
17
impossible
12

ICPC World Finals 2021 Problem B: Dungeon Crawler

Sample Input 2

7 4
1 2 1
1 3 1
1 4 1
1 5 1
1 6 1
1 7 1
1 2 3
5 4 1
3 1 4
2 4 5

Sample Output 2

11
impossible
10
10

ICPC World Finals 2021 Problem B: Dungeon Crawler

Time limit: 3 seconds

Image by ZedH at Pixabay After sailing the Seven Seas and raiding many ships, Cap’n Red and his crew of fellow pirates are finally ready to divide their loot. According to ancient traditions, the crew stands in a circle ordered by a strict pirate hierarchy. Cap’n Red starts by taking a fraction $f$ of the loot and passing the remainder on to the next pirate. That pirate takes the same fraction $f$ of the loot left over by the previous pirate and passes the remainder on to the following pirate. Each pirate behaves in the same way, taking a fraction $f$ of what is left and passing on the rest. The last pirate in the hierarchy passes the remainder on to Cap’n Red, who starts another round of this “fair” division, and so on, indefinitely.

Fortunately, pirates in the 21st century can use a computer to avoid this lengthy process and constant nitpicking when the fraction $f$ does not ex- actly divide the loot at some step. You have been captured by the pirates and asked to come up with a suitable fraction $f$. As an incentive, Cap’n Red has promised to leave you alive if you succeed.

The fraction $f$ needs to be a rational number strictly between $0$ and $1$. It is not necessary that $f$ exactly divides the loot remaining at any step of the round-robin process described above. However, the total loot that would be assigned to each pirate by carrying out this process infinitely needs to be an integer.

Input

The input contains one line with two integers $n$ and $m$, where $n$ ($6\le n\le 10^{6}$) is the number of pirates including Cap’n Red and $m$ ($1\le m\le 10^{18}$) is the total value of their loot.

Output

Output one line with two positive integers $p$ and $q$, where $f = ^{p}$ $q$ as specified above. If there are multiple suitable fractions, choose one with the smallest $q$. Among multiple suitable fractions with the same smallest $q$ choose the one with the smallest $p$. If there is no suitable fraction, output impossible instead and hope for mercy.

Sample Input 1

8 51000

Sample Output 1

1 2

Sample Input 2

6 91000

Sample Output 2

2 3

Sample Input 3

10 1000000000000000000

Sample Output 3

impossible

ICPC World Finals 2021 Problem C: Fair Division

Time limit: 5 seconds

Your local art gallery is about to host an exciting new exhibition of sculptures by world-renowned artists, and the gallery expects to attract thousands of visitors. Unfortunately, the exhibition might also attract the wrong kind of visitors, namely burglars who intend to steal the works of art. In the past, the gallery directors did not worry much about this problem, since their permanent collection is, to be honest, not really worth stealing.

The gallery consists of rooms, and each sculpture in the new exhibition will be placed in a different room. Each room has a security guard and an alarm to monitor the artwork. When an alarm sounds, the guard will run (without leaving the room) from their post to a position where they can see the sculpture directly. This is to check whether the sculpture has in fact been stolen, or whether this is yet another false alarm.

To figure out where to best station the security guard, the gallery directors would like to know how long it takes for the guard to see a given sculpture. They hope that you can help!

Every room is on a single floor, and the layout of the walls can be approximated by a simple polygon. The locations of the guard and the sculpture are distinct points strictly inside the polygon. The sculpture is circular, with a negligibly small (but positive) radius. To verify that the sculpture is still present, the guard needs to be able to see at least half of it.

Figure D.1 illustrates two examples. In each case, the guard starts at the blue square on the left, and the sculpture is located at the red circle on the right. The dotted blue line shows the optimal path for the guard to move. Once the guard reaches the location marked by the green diamond, half of the sculpture

Figure D.1: Illustration of sample inputs.

Input

The first line of input contains an integer $n$ ($3 \le n \le 100$), the number of vertices that describe the polygon. This is followed by $n$ lines each containing two integers $x$ and $y$ ($0 \le x, y \le 1 000$), giving the coordinates of the polygon vertices in counterclockwise order. The next line contains two integers $x_{g}$ and $y_{g}$, which specify the location of the guard. Finally, the last line contains two integers $x_{s}$ and $y_{s}$, which specify the location of the center of the sculpture. The polygon is simple, that is, its vertices are distinct and no two edges of the polygon intersect or touch, other than consecutive edges which touch at their common vertex. In addition, no two consecutive edges are collinear.

ICPC World Finals 2021 Problem D: Guardians of the Gallery

Output

Output the minimum distance that the guard has to move to be able to see at least half the sculpture. Your answer must have an absolute or relative error of at most $10^{- 6}$.

Sample Input 1

8
0 0
20 0
20 30
60 30
60 0
80 0
80 50
0 50
10 10
70 10

Sample Output 1

58.137767414994535

Sample Input 2

11
0 0
4 0
4 1
5 1
5 0
7 0
7 2
3 2
3 1
2 2
0 2
1 1
6 1

Sample Output 2

2.0

ICPC World Finals 2021 Problem D: Guardians of the Gallery

Time limit: 2 seconds

Example placement of cards for $k = 5$ There is a fairly well-known mentalism trick known as the Fitch Cheney trick. From a deck of $n$ playing cards, $k$ are selected uniformly at random and given to an assistant while the magician is out of the room. The assistant places $k- 1$ of the selected cards on a table, face up, and the single re- maining card face down. The cards are placed in a single row with the face-down card at the end (see the picture for an example). The magician enters the room, looks at the cards on the table, and announces what the $k$th card is, although its face is hidden. The trick is typically done with $n= 52$ and $k = 5$.

The assistant uses two ways of passing information to the magician. First, they can pick which one of the $k$ cards to keep hidden. Second, they can rearrange the other $k- 1$ cards in a specific way. For the case $n = 52$ and $k = 5$ both techniques are needed, since there are only $24$ ways of rearranging four cards, which is not enough to reliably signal the fifth card. It is an interesting exercise to come up with a simple, easy-to-remember strategy for executing this trick, but right now you have another concern.

You were planning to perform this trick today, but just now you have learned that the deck has more cards than you expected. The trick may be impossible! In desperation, you have decided to cheat a little. You have $m$ distinguishable ways of marking the backs of the playing cards. You have marked the backs of all $n$ cards, allowing you to narrow down the possibilities for the $k$th card. For example, if there are $6$ cards marked with a particular method, and you see that the back of the $k$th card is marked with that method, you know it must be one of those $6$ cards.

Determine the probability that you will successfully guess the $k$th card, assuming you and the assistant execute an optimal (but likely very complicated!) strategy.

Input

The input contains one line with several integers. The first integer gives $k$ ($2\le k \le 10$), the number of cards that will be selected. The second integer gives $m$ ($1 \le m \le 10$), the number of ways of marking the cards. The line is completed by $m$ positive integers, giving the number of cards marked with each distinct method. The sum of these $m$ integers is $n$ ($k \le n\le 10^{9}$), which is the size of the deck.

Output

Output the highest possible probability of guessing the $k$th card correctly, accurate up to an absolute error of $10^{- 9}$.

Sample Input 1

4 1 28

Sample Output 1

0.96

Sample Input 2

3 3 5 12 3

Sample Output 2

0.854385964912

ICPC World Finals 2021 Problem E: Hand of the Free Marked

Time limit: 2 seconds

You might never have heard of the island group of Iceepeecee, but that suits their inhabitants just fine. Located in a remote part of the South Pacific, they are truly off the beaten track, without any regular air or sea traffic, and they have remained a tropical paradise with unspoiled local fauna and flora.

Being off the map is great when you don’t want to be overrun by hordes of tourists, but not so ideal when you actually do need a map for some reason. One such reason came up recently: Iceepeecee’s central government needs an exact map of the islands to apportion government funds. Even tropical paradises need money, so Iceepeecee needs a map!

The easiest way to create a map would be an aerial survey. After dismissing chartering planes as too expensive, building an air balloon as too dangerous, and fitting carrier pigeons with cameras as too cruel to animals, they had a brilliant idea. Even with its remote location, there are still plenty of commercial airplanes crossing the skies above Iceepeecee. What if one mounted cameras on flights that are already scheduled to fly anyway? That would be a cheap solution to the problem!

Iceepeecee’s plan is to install line-scan cameras on the planes. These cameras point straight downwards and collect images one line segment at a time, orthogonal to the flight path. The photographed line segment will be determined by the altitude that the plane is flying at, and the camera’s aperture angle $\theta$ (see Figure F.1). Greater angles $\theta$ mean that the camera can see more, but also that the camera is more expensive.

Moreover, Iceepeecee wants to make sure that each island is observed in its entirety by at least one flight. That means it is not sufficient that an island is only partially photographed by multiple flights, even if the combination of the photographs covers the whole island.

Flight paths follow straight line segments in three-dimensional space, that is, $(x_{1}, y_{1}, z_{1})- (x_{2}, y_{2}, z_{2})$ (see Figure F.2), where the $z$-coordinates give the altitude of the plane. Photographs are taken only along these line segments.

Given the location of their islands and flights, Iceepeecee wants to find the smallest aperture angle $\theta$ that

Figure F.2: Surveying three islands via two flight paths. This corresponds to the first sample input.

ICPC World Finals 2021 Problem F: Islands from the Sky

Input

The input describes a set of islands and flight paths. It starts with a line containing two integers $n$ and $m$, the number $n$ of islands, and the number $m$ of flight paths, respectively ($1 \le n, m \le 100$). This is followed by descriptions of the $n$ islands. Each island description starts with a line containing a single integer $n_{i}$, the number of vertices of the polygon describing the $i$th island ($3\le ni \le 100$). It is followed by $n_{i}$ lines, each containing two integers $x_{ij}$, $yij (|xij|,|yij| \le 10^{6})$, specifying the vertices for the $i$th island in counterclockwise order. Each island’s polygon is simple, that is, its vertices are distinct and no two edges of the polygon intersect or touch, other than consecutive edges which touch at their common vertex. Different islands do not intersect or touch.

The input concludes with another $m$ lines, each describing a flight path. Each such line contains six integers $x_{1}$, $y_{1}$, $z_{1}$, $x_{2}$, $y_{2}$, $z_{2}$ ($|x_{i}|,|y_{i}|,|z_{i}| \le 10^{6}$, $zi >0$ and $(x_{1}, y_{1})= (x_{2}, y_{2})$). They specify that a flight takes place from $(x_{1}, y_{1}, z_{1})$ to $(x_{2}, y_{2}, z_{2})$.

Output

Output the smallest angle $\theta$ (in degrees) that allows for a complete survey of the islands with the given flights. The answer should be exact to an absolute or relative error of $10^{- 6}$. If there is no such angle, then output impossible. The input is chosen such that if the coordinates of the island vertices are changed by at most $\pm 10^{- 8}$, then the answer will not change more than the allowed rounding error.

Sample Input 1

3 2
3
20 30
50 50
10 50
4
40 20
60 10
75 20
60 30
4
45 60
55 55
60 60
55 65
0 30 20 78 70 5
55 0 20 70 60 10

Sample Output 1

48.031693036

Sample Input 2

1 1
4
0 0
10 0
10 10
0 10
5 5 10 15 5 10

Sample Output 2

impossible

ICPC World Finals 2021 Problem F: Islands from the Sky

Time limit: 6 seconds

The International Center for the Preservation of Ceramics (ICPC) is searching for motifs in some ancient mosaics. According to the ICPC’s definition, a mosaic is a rectangular grid where each grid square contains a colored tile. A motif is similar to a mosaic but some of the grid squares can be empty. Figure G.1 shows an example motif and mosaic.

The rows of an $rq\times cq$ mosaic are numbered $1$ to $r_{q}$ from top to bottom, and the columns are numbered $1$ to $c_{q}$ from left to right.

A contiguous rectangular subgrid of the mosaic matches the motif if every tile of the motif matches the color of the corresponding tile of the subgrid. Formally, an $rp\times cp$ motif appears in an $rq \times cq$ mosaic at position $(r, c)$ if for all $1\le i\le r_{p}$, $1\le j \le c_{p}$, the tile $(r+i- 1, c+j- 1)$ exists in the mosaic and either the square $(i, j)$ in the motif is empty or the tile at $(i, j)$ in the motif has the same color as the tile at $(r+i- 1, c+j- 1)$ in the mosaic.

Given the full motif and mosaic, find all occurrences of the motif in the mosaic.

Figure G.1: Motif (left) and mosaic (right) of Sample Input 1.

Input

The first line of input contains two integers $r_{p}$ and $c_{p}$, where $r_{p}$ and $c_{p}$ ($1 \le rp, cp \le 1 000$) are the number of rows and columns in the motif. Then $r_{p}$ lines follow, each with $c_{p}$ integers in the range $[0,100]$, denoting the color of the motif at that position. A value of $0$ denotes an empty square.

The next line of input contains two integers $r_{q}$ and $c_{q}$ where $r_{q}$ and $c_{q}$ ($1 \le rq, cq \le 1 000$) are the number of rows and columns in the mosaic. Then $r_{q}$ lines follow, each with $c_{q}$ integers in the range $[1,100]$, denoting the color of the mosaic at that position.

ICPC World Finals 2021 Problem G: Mosaic Browsing

Output

On the first line, output $k$, the total number of matches. Then output $k$ lines, each of the form $r c$ where $r$ is the row and $c$ is the column of the top left tile of the match. Sort matches by increasing $r$, breaking ties by increasing $c$.

Sample Input 1

2 2
1 0
0 1
3 4
1 2 1 2
2 1 1 1
2 2 1 3

Sample Output 1

3
1 1
1 3
2 2

ICPC World Finals 2021 Problem G: Mosaic Browsing

Time limit: 6 seconds

Clay tablet with undeciphered script Source: Wikimedia Commons Archaeologists have discovered exciting clay tablets in deep layers of Alutila Cave. Nobody was able to decipher the script on the tablets, ex- cept for two symbols that seem to describe nested structures not unlike opening and closing parentheses in LISP. Could it be that humans wrote programs thousands of years ago?

Taken together, the tablets appear to describe a great piece of work – perhaps a program, or an epic, or even tax records! Unsurprisingly, af- ter such a long time, the tablets are in a state of disorder. Your job is to arrange them into a sequence so that the resulting work has a prop- erly nested parenthesis structure. Considering only opening and closing parentheses, a properly nested structure is either

• (), or

• ($A$), where $A$ is a properly nested structure, or

• $AB$, where $A$ and $B$ are properly nested structures.

Input

The first line of input contains one integer $n$ ($1\le n\le 10^{6}$), the number of tablets. Each of the remaining $n$ lines describes a tablet, and contains a non-empty string of opening and closing parentheses; symbols unrelated to the nesting structure are omitted. The strings are numbered from $1$ to $n$ in the order that they appear in the input. The input contains at most $10^{7}$ parentheses.

Output

Output a permutation of the numbers from $1$ to $n$ such that concatenating the strings in this order re- sults in a properly nested structure. If this happens for multiple permutations, any one of them will be accepted. If there is no such permutation, output impossible instead.

Sample Input 1

2
())())()
((()

Sample Output 1

2
1

ICPC World Finals 2021 Problem H: Prehistoric Programs

Sample Input 2

5
(
))
((
))
(

Sample Output 2

1
5
3
2
4

Sample Input 3

2
((
)

Sample Output 3

impossible

ICPC World Finals 2021 Problem H: Prehistoric Programs

Time limit: 6 seconds

Image by FBR Charlotte the spider sits at the center of her spiderweb, which consists of a series of silken straight strands that go from the center to the outer boundary of the web. Charlotte’s web also has bridges, each of which connects two adjacent strands. The two endpoints of a bridge always have the same distance to the center of the spiderweb.

When Charlotte has finished a late-night feasting in the cen- ter and wants to retreat to some corner, she walks to the edge on autopilot. To do this, she picks a starting strand, and walks along it until she meets the first bridge on that strand. She will cross the bridge and go to the other strand, and then keeps walking outwards until she meets another bridge. Then she will cross that bridge, and repeat this process, until there are no more bridges on the current strand, and then she will walk to the end of the current strand. Note that Charlotte must cross all the bridges that she meets. Figure I.1 illustrates one path Charlotte could take.

Charlotte’s favorite corner to sleep in during the daytime is at the end of strand $s$. For each possible starting strand, she wants to know the minimum number of bridges to add to the original web in order to end at $s$. Charlotte can add a bridge at any point along the strand, as long as the added bridge does not touch any other bridge. The two endpoints of any added bridge must have the same distance to the center of the spiderweb, and the bridge must connect two adjacent strands.

Figure I.1: The path starting from strand $4$ on the spiderweb in Sample Input 1.

ICPC World Finals 2021 Problem I: Spider Walk

Input

The first line of input has three integers $n$, $m$, and $s$, where $n$ ($3 \le n \le 200 000$) is the number of strands, $m$ ($0 \le m \le 500 000$) is the number of bridges, and $s$ ($1 \le s \le n$) is Charlotte’s favorite strand. Strands are labeled from $1$ to $n$ in counterclockwise order. Each of the remaining $m$ lines contains two integers $d$ and $t$ describing a bridge, where $d$ ($1 \le d \le 10^{9}$) is the bridge’s distance from the center of the spiderweb and $t$ ($1\le t\le n$) is the first strand of the bridge in counterclockwise order. Specifically, if $1\le t < n$, then the bridge connects strands $t$ and $t+1$. If $t=n$, then the bridge connects strands $1$ and $n$. All bridge distances $d$ are distinct.

Output

Output $n$ lines, where the $i$th line is the minimum number of bridges Charlotte needs to add in order to end at strand $s$ after walking on autopilot from strand $i$.

Sample Input 1

7 5 6
2 1
4 3
6 3
8 7
10 5

Sample Output 1

2
1
1
1
0
1
2

Sample Input 2

4 4 2
1 1
2 2
3 3
4 4

Sample Output 2

1
1
0
1

ICPC World Finals 2021 Problem I: Spider Walk

Time limit: 3 seconds

Ganga-Brahmaputra delta (ESA, CC BY-SA 3.0 IGO) A splitstream system is an acyclic network of nodes that processes finite sequences of numbers. There are two types of nodes (illustrated in Figure J.1):

• A split node takes a sequence of numbers as input and dis- tributes them alternatingly to its two outputs. The first number goes to output $1$, the second to output $2$, the third to output $1$, the fourth to output $2$, and so on, in this order.

• A merge node takes two sequences of numbers as input and merges them alternatingly to form its single output. The output contains the first number from input $1$, then the first from input $2$, then the second from input $1$, then the second from input $2$, and so on. If one of the input sequences is shorter than the other, then the remaining numbers from the longer sequence are simply transmitted without being merged after the shorter

Figure J.1: Illustration of how split and merge nodes work.

The overall network has one input, which is the sequence of positive integers $1,2,3, . . . , m$. Any output of any node can be queried. A query will seek to identify the $k$th number in the sequence of numbers for a given output and a given $k$. Your task is to implement such queries efficiently.

Input

The first line of input contains three integers $m$, $n$, and $q$, where $m$ ($1 \le m \le 10^{9}$) is the length of the input sequence, $n$ ($1\le n\le 10^{4}$) is the number of nodes, and $q$ ($1\le q \le 10^{3}$) is the number of queries.

The next $n$ lines describe the network, one node per line. A split node has the format S $x y z$, where $x$, $y$ and $z$ identify its input, first output and second output, respectively. A merge node has the format M $x y z$, where $x$, $y$ and $z$ identify its first input, second input and output, respectively. Identifiers $x$, $y$ and $z$ are distinct positive integers. The overall input is identified by $1$, and the remaining input/output identifiers form a consecutive sequence beginning at $2$. Every input identifier except $1$ appears as exactly one output. Every output identifier appears as the input of at most one node.

ICPC World Finals 2021 Problem J: Splitstream Each of the next $q$ lines describes a query. Each query consists of two integers $x$ and $k$, where $x$ ($2\le x\le 10^{5}$) is a valid output identifier and $k$ ($1\le k \le 10^{9}$) is the index of the desired number in that sequence. Indexing in a sequence starts with $1$.

Output

For each query $x$ and $k$ output one line with the $k$th number in the output sequence identified by $x$, or none if there is no element with that index number.

Sample Input 1

200 2 2
S 1 2 3
M 3 2 4
4 99
4 100

Sample Output 1

100
99

Sample Input 2

100 3 6
S 1 4 2
S 2 3 5
M 3 4 6
6 48
6 49
6 50
6 51
6 52
5 25

Sample Output 2

47
98
49
51
53
100

Sample Input 3

2 3 3
S 1 2 3
S 3 4 5
M 5 2 6
3 1
5 1
6 2

Sample Output 3

2
none
none

ICPC World Finals 2021 Problem J: Splitstream

Time limit: 4 seconds

The Internet can be so fickle. You work for a small ad agency, Mimi’s Mammoth Memes. Your ad campaigns are very cheap, and rely on the hope of producing the next hit viral meme. Unfortunately, the last four hundred or so memes have failed to take off, despite having been precisely engineered to appeal to every single person on Earth. You’re not sure what exactly went wrong, but you’ve decided to try a new approach: crowd sourcing!

According to your scientific meme theory, all memes can be rated from $- \infty$to $\infty$on two scales: xan- thochromism, and yellowishness, also known as $(x, y)$ values. Obviously (you think), the best memes are memorable for being particularly xanthochromic, yellowish, unxanthochromic, or unyellowish. You feel that the “quality” of any meme is directly measurable as its squared Euclidean distance ($x ^{2}+y^{2}$) from the Base Meme $(0,0)$, otherwise known as All Your Base.

To produce the ultimate viral meme, you’ll be taking your company’s last few failed memes and throwing them into a tournament, decided by online voting. The tournament can be represented as a rooted tree. Input memes come in at the leaves, and at each internal node, a vote will be held among its $k$ child memes $(x_{1}, y_{1}), . . . ,(x_{k}, y_{k})$. After the vote, all the memes will be horrifically mangled and merged into a brand new meme, specifically calculated to emphasize the winner and de-emphasize all the losers: the resultant $x$ value will be $k$ $X$

$i=1$ $wi\cdot xi,$

where $w_{i}$ is $1$ if the $i$th child won, and $- 1$ otherwise. The $y$ value is computed similarly. This new meme will move on to the next vote in the tournament – or, if there is no parent, it will be declared the champion and the ultimate meme!

You already have the structure of the tournament planned out, including all the input memes and the internal voting nodes. What is the largest possible quality for any meme that the tournament could produce?

Input

The first line of input contains an integer $n$ ($1 \le n \le 10^{4}$), giving the total number of nodes in the tournament tree. The next $n$ lines each describe a single tree node indexed from $1$ to $n$. The line for node $i$ starts with an integer $k_{i}$ ($0\le ki \le 100$), the number of children of that node. If $k_{i}$ is $0$, then node $i$ is an input meme and there will be two more integers $x_{i}$ and $y_{i}$ ($- 10 ^{3}\le xi, yi \le 10^{3}$) describing it. If $ki > 0$, then $k_{i}$ different integers $j$ ($i < j \le n$) will follow, giving the indices of the $k_{i}$ nodes entering this voting step.

All input memes will eventually be merged into the final output meme at node $1$. The complete tree will have a height of no more than $10$.

Output

Output the largest possible quality for the champion meme at node $1$.

ICPC World Finals 2021 Problem K: Take On Meme

Sample Input 1

4
3 2 3 4
0 10 1
0 3 6
0 2 7

Sample Output 1

169

Sample Input 2

8
3 4 2 5
2 3 8
0 -3 9
0 -5 -7
2 6 7
0 1 4
0 -3 -1
0 1 4

Sample Output 2

314

ICPC World Finals 2021 Problem K: Take On Meme

Time limit: 2 seconds

Who am I? What am I? Why am I? These are all difficult questions that have kept philosophers reliably busy over the past millennia. But when it comes to “Where am I?”, then, well, modern smartphones and GPS satellites have pretty much taken the excitement out of that question.

To add insult to the injury of newly unemployed spatial philosophers formerly pondering the “where” question, the Instant Cartographic Positioning Company (ICPC) has decided to run a demonstration of just how much more powerful a GPS is compared to old-fashioned maps. Their argument is that maps are useful only if you already know where you are, but much less so if you start at an unknown location.

For this demonstration, the ICPC has created a test area that is arranged as an unbounded Cartesian grid. Most grid cells are empty, but a finite number of cells have a marker at their center (see Figure L.1(a) for an example with five marked cells). All empty grid cells look the same, and all cells with markers look the same. Suppose you are given a map of the test area (that is, the positions of all the markers), and you are placed at an (unknown to you) grid cell. How long will it take you to find out where you actually are? ICPC’s answer is clear: potentially a very, very long time, while a GPS would give you the

Figure L.1: Sample grid and the order in which test subjects explore the grid.

In the trial, test subjects will explore their environment by following an expanding clockwise spiral whose first few steps are shown in Figure L.1(b). The starting cell is labeled “0”, and the numbers show the order in which other cells are visited. The test subjects can see a marker only if they are at its grid cell, and they will stop their exploration as soon as they know where they are based on the grid cells that they have seen so far. That means that the observed sequence of empty and marked grid cells could have begun only at a single possible starting position. The grid is unbounded, but the exploration will be finite since once a test subject has seen all markers on the grid, they’ll definitely know where they are.

Having hundreds of test subjects literally running in circles can be expensive, so the ICPC figures that writing a simulation will be cheaper and faster. Maybe you can help?

ICPC World Finals 2021 Problem L: Where Am I?

Input

The input describes a single grid. It starts with a line containing two integers $d_{x}, d_{y}$ ($1\le dx, dy \le 100$). The following $d_{y}$ lines contain $d_{x}$ characters each, and describe part of the test grid. The $i$th character of the $j$th line of this grid description specifies the contents of the grid cell at coordinate $(i, dy- j+1)$. The character is either ‘.’ or ‘X’, meaning that the cell is either empty, or contains a marker, respectively.

The total number of markers in the grid will be between 1 and 100, inclusive. All grid cells outside the range described by the input are empty.

Output

In ICPC’s experiment, a test subject knows they will start at some position $(x, y)$ with $1 \le x \le d_{x}$, $1\le y \le d_{y}$.

Output three lines. The first line should have the expected number of steps needed to identify the starting position, assuming that the starting position is chosen uniformly at random. This number needs to be exact to within an absolute error of $10^{- 3}$.

The second line should have the maximum number of steps necessary until one can identify the starting position.

The third line should list all starting coordinates $(x, y)$ that require that maximum number of steps. The coordinates should be sorted by increasing $y$-coordinates, and then (if the $y$-coordinates are the same) by increasing $x$-coordinates.

Sample Input 1

5 5
....X
.X...
.....
X..X.
..X..

Sample Output 1

9.960
18
(1,4) (4,5)

Sample Input 2

5 1
..XX.

Sample Output 2

4.600
7
(1,1) (5,1)

ICPC World Finals 2021 Problem L: Where Am I?