After years of experimentation, Kakashi has come up with the "square"-jutsu, a powerful technique that strikes lightning onto a large square area of land. Kakashi happens to be testing his jutsu on a mountain, which can be modeled by an $$$N \times N$$$ grid.

Each cell at row $$$1\leq i\leq N$$$ and column $$$1\leq j\leq N$$$ on the mountain has an elevation $$$c_{i, j}$$$. For every cell $$$(i,j)$$$ it is guaranteed that $$$c_{i,j} \leq \min \left(c_{i+1, j}, \space c_{i, j+1}, \space c_{i+1, j+1}\right)$$$ (treating cells outside the $$$N\times N$$$ grid as having infinite elevation). It is also guaranteed that $$$c_{1, 1} = 0$$$.

Kakashi's jutsu is powerful, but limited: square-jutsu can strike any $$$k\times k$$$ square block of mountain cells, but only if the entire $$$k\times k$$$ block lies within the bounds of the mountain grid and only if every cell in the block has elevation within a certain range $$$[a, b]$$$ inclusive ($$$a \leq c_{i, j} \leq b$$$ for all cells $$$(i,j)$$$ in the target square). Given the elevation of every mountain cell and the elevation range allowed by his jutsu, Kakashi wants to know the number of cells in the largest possible square block his jutsu can hit.

Angels are surprisingly violent, and love beating up one another! This has lead to lots of conflict in the angel world that you have decided to fix.

To do this, each group sends one of its angels to help defend. Every angel has a combat power $$$p$$$, and the combat power of the defense is the sum of combat powers of the $$$n$$$ angels sent by the groups. However, angel combat is complicated, and it requires perfect technique. In order to successfully defend against an attack of power $$$t$$$, the lowest $$$m$$$ bits of the defense's combat power must match the lowest $$$m$$$ bits of $$$t$$$. (Note that the defense's power need not be larger than that of the attacker's power.)

As the leader of the angels, you must figure out how to successfully defend against all attacks, even as angels join and leave the various groups. Hurry, you don't have much time left before the first attack!

In Attack on Titans, humanity lives in fear of giant humanoid creatures called Titans. In order to defend themselves, the humans built three walls: Wall Maria, Wall Rose, and Wall Sina. Wall Maria is made up of $$$n$$$ separate sections, with the $$$i$$$th section having height $$$m_i$$$. Wall Rose and Wall Sina also have $$$n$$$ sections each, with heights $$$r_i$$$ and $$$s_i$$$ respectively.

Find the tallest section height common to all three walls: the maximum value of $$$h$$$ with $$$h = m_i = r_j = s_k$$$ for some indices $$$1 \leq i,j,k \leq n$$$. Note that for a height $$$h$$$ to be common to all three walls, each wall must have a section of height $$$h$$$, but these sections are not required to be at the same position on all three walls.

To determine the fate of Immanity, Sora and Shiro are playing yet another game, this time against the flügel Azriel!

They are given a string $$$s$$$ of length $$$N$$$ consisting only of lowercase and uppercase English ASCII letters. They are also given a list $$$a$$$ of $$$N$$$ integers, each in the range $$$1 \leq a_i \leq 100$$$.

Azriel carefully constructs $$$M$$$ (not necessarily distinct) strings, also consisting only of lowercase and uppercase English ASCII letters.

Sora and Shiro then choose a (possibly empty) subset of lowercase and uppercase letters. Let's denote this set $$$S$$$.

Azriel's score $$$k$$$ is calculated through the following process:

• For all characters $$$c$$$ in $$$S$$$, replace all occurrences of $$$c$$$ in $$$s$$$ with a dot (.). Note that characters are being replaced, not removed. Denote the new string $$$t$$$.
• For each character $$$t_i$$$ in $$$t$$$, if $$$t_i$$$ is not equal to a dot, add $$$a_i$$$ to $$$k$$$.
• For each of Azriel's strings $$$r_i$$$, count how many times $$$r_i$$$ appears as a substring of $$$t$$$ and subtract $$$c_i$$$ from $$$k$$$ for each appearance. (Again, note that Azriel's strings are not necessarily distinct; so for instance if $$$r_i = r_j$$$, then Azriel's score decreases by $$$c_i+c_j$$$ for each appearance of $$$r_i$$$ in $$$t$$$.)

Since Shiro and Sora must beat Azriel for the sake of Immanity, they must choose a subset of characters $$$S$$$ that minimizes Azriel's score. Help them by finding the minimum possible value of Azriel's final score, and also print a string $$$t$$$ which produces this score.

Saitama, the One-Punch Man, is on a mission to defeat a group of monsters in order to challenge the monster boss, Centichoro. The power level of each of the $$$i$$$ monsters is stored in an array, where $$$p_i$$$ denotes the power level of the monster at index $$$i.$$$ Saitama's goal is to defeat the most powerful group of monsters by finding the maximum sum of any contiguous subarray of monster strengths. If he does so, he will be able to fight against Centichoro to save humanity. Help Saitama calculate the sum of the power levels of the corresponding subarray!

Note: The subarray of $$$a$$$ is $$$a$$$ contiguous part of the array $$$a$$$, i.e. the array $$$a_i,a_{i+1}...,a_j$$$ for some $$$1 \leq i \leq j \leq n$$$.

By the wind storm's blast

From Mimuro's mountain slopes

Maples leaves are torn,

Which turn Tatsuta River

Into a rich brocade.

—

Chihaya and Taichi are playing a game of Karuta. During one round, they heard the song related to the poem above, and they remembered the following problem. Please help them solve it so they can continue playing!

A category-$$$k$$$ storm is coming and will blow the leaves off of a nearby tree. During the storm, the wind speed will vary: at time $$$t$$$ seconds after the storm begins, the wind speed is $$$w_t = a_t + k \cdot d_t$$$ units per second, for some time-varying additive and multiplicative base speeds $$$a_t$$$ and $$$d_t$$$.

There are $$$n$$$ leaves attached to a tree. The $$$i$$$th leaf starts at position $$$(0, y_i)$$$ and detaches from the tree at time $$$\ell_i$$$. In between times $$$t$$$ and $$$t+1$$$, any leaf that detached from the tree at time $$$t$$$ or earlier and hasn't yet hit the ground (at $$$y=0$$$) travels 1 unit down and $$$w_t$$$ units to the right; i.e. a leaf at position $$$(x,y)$$$ moves to $$$(x+w_t, y-1)$$$. Leaves that hit the ground never move again.

After the storm, you will need to rake up all the leaves, and need to know the farthest distance along the $$$x$$$-axis that any leaf will hit the ground. You might learn more accurate information about the storm in the future, and will need to recompute this farthest distance if $$$k$$$, $$$a_t$$$, or $$$d_t$$$ change.

Sophie has found herself trapped inside Howl's Moving Castle!

Howl's Moving Castle can be represented as a connected graph of $$$N$$$ rooms and $$$N-1$$$ (bidirectional) hallways connecting rooms. However, this isn't just any old castle – this is Howl's Moving Castle. Every morning, the castle comes to life, and the rooms shift such that some of the hallways become inaccessible, disconnecting the rooms adjacent to the hallways. This creates a distinct partition of rooms – a grouping of rooms into non-empty subsets such that each room is in exactly one subset, each subset forms a connected graph, and the subsets are disconnected from each other.

Sophie has a set of possible tasks (reload the trebuchets, feed the alligators in the moat, empty the chamber pot, etc.), which requires moving between two rooms. Specifically, for the $$$t$$$th task, Sophie starts at room $$$a_t$$$, and needs the path to the second room $$$b_t$$$ to be unobstructed.

How many possible partitions of Howl's Moving Castle are there such that every task can be completed?

You can assume that Sophie can teleport between tasks, i.e. teleport from room $$$b_t$$$ to room $$$a_{t+1}$$$.

Tyson is up to his beyblading ways again. In a beyblade battle, two players launch their beyblades (small spinning tops) into an arena to battle each other until one stops spinning.

This time, Tyson is up against a particularly defensive opponent, and needs to determine how close his beyblade can get to his opponent's since his own beyblade is equipped with a ranged attack. However, his opponent's beyblade has two defensive walls set up that try to keep other beyblades away.

Tyson has done some preliminary calculations and determined that the arena can be modeled as the $$$2D$$$ plane with the opponent's beyblade at the origin. The walls protecting the opponent's beyblade are both infinite lines that pass through the origin (forming an X-shape with the origin at the crossing). The first wall makes an angle of $$$\alpha$$$ degrees measured counterclockwise from the positive $$$x$$$-axis, and the second wall makes an angle of $$$\beta$$$ degrees (also measured counterclockwise from the positive $$$x$$$-axis). Tyson's beyblade begins at location $$$(p_x, p_y)$$$, and Tyson launches it at an angle of $$$\theta$$$ degrees (measured counterclockwise with respect to the vector extending from $$$(p_x,p_y)$$$ in the positive $$$x$$$ direction). When the beyblade collides with either wall, it reflects off the wall perfectly with angle of incidence equal to the angle of reflection, much like light bounces off of a mirror. Assuming that Tyson's beyblade keeps traveling for infinite time, what is the closest distance it will get to his opponent's beyblade, and how many total times will it bounce off of a wall?

It is guaranteed that $$$0 \leq \alpha \lt \beta \lt 180$$$, $$$\beta - \alpha \gt 10^{-2}, 180 - (\beta - \alpha) \gt 10^{-2}$$$, and that Tyson's beyblade starts at least distance $$$10^{-2}$$$ away from either wall. Furthermore, the minimum distance between Tyson's beyblade and the origin along its path of motion is at least $$$10^{-6}$$$ units.

Umaru's older brother Taihei is off to work again, which means it is time for her to sit back, relax, play some video games, and enjoy delicious snacks including potato chips and cola. Taihei has been trying to teach Umaru the importance of sharing, so to put this into practice, she will be buying bags of chips to distribute to her friends.

The town Umaru lives in can be modeled as a set of $$$N$$$ houses and $$$N - 1$$$ roads such that there is a unique simple (no edges or nodes reused) path between any two houses. Additionally, Umaru has $$$a_i$$$ friends that live in the $$$i$$$-th house. Taihei will be gone for $$$Q$$$ hours, so Umaru plans to go on at most $$$Q$$$ "snack runs". At the $$$i$$$-th point in time (for each $$$i$$$ at most $$$Q$$$), one of two things may happen. The first possibility is that Umaru will go on a snack run. If so, Umaru travels from house $$$u_i$$$ to house $$$v_i$$$ and gives snacks to her friends along the way. If not, she tells her friends to gather at a particular house $$$w_i$$$, in which case the number of friends that live at house $$$w_i$$$ becomes multiplied by a factor of $$$f_i$$$ (these friends come from out of town, friends never leave their houses).

Umaru is having trouble figuring out how many snacks to bring with her on each snack run. Being lazy, she wants to bring the smallest positive integer number of snacks that will be evenly divisible by the number of people in each of the houses that she visits along the way (including her starting city and destination). Given information regarding each of her snack runs, can you help her figure out how many snacks to bring?

Light Yagami is once again playing games with the detective L. This time, L has invited Light to a fancy restaurant and has brought 3 piles of canned potato chips to the table; unknowingly, this happens to be one of Light's favorite snacks. While waiting for their order, the detective offers a game: Light and L will alternate between taking chips, where each person can take some number of chips $$$1 \leq c_i \leq p_i$$$ from one of the piles i (where $$$p_i$$$ is the number of chips in pile i), or take some number of chips $$$1 \leq c_i \leq \min\{p_i\}$$$ (where $$$\min\{p_i\}$$$ is the minimum amount of chips across all piles) from all three of the piles. Being a gentleman, L offers Light to go first. Is it possible for Light to take the last chip if both play optimally?

It's Fantastic Friday, so Izuku Midoriya goes to the local anime trading card dealership to explore the latest releases. He is currently trying to collect the entire "Plus Ultra" card set of anime characters. Unfortunately for him, he does not know how many characters are in this set. He does, however, see that each character has a unique "quirk number."

He has brought his own collection containing $$$N$$$ cards, some of which may be duplicates. His goal is to collect one of each character in a contiguous run of quirk numbers starting at $$$1$$$. More formally, he would like to collect exactly one card each with quirk number $$$1, 2, 3, \ldots K$$$ for some positive integer $$$K$$$. He does not want any duplicates or any extra character cards whose quirk numbers are not part of the contiguous run: this would ruin the collection.

Midoriya cannot bring himself to simply throw a card away; however the card dealership will allow him to trade in any character card he owns for any other card of his choice for $$$A$$$ yen. Midoriya can also buy any character card of his choice outright for $$$B$$$ yen. (It's possible that $$$A \gt B$$$: the card dealer loves anime, but may not be great at economics.) The shop has an unlimited supply of cards of every quirk number. In order to satisfy his wish of possessing a contiguous run of quirk numbers, what is the minimum amount of money Izuku Midoriya needs to spend?

My Hero Academia (you) has taken a break from saving my grades and has now decided to help me with my burgeoning photography hobby. I have taken an image with my camera, but there are a few problems with it. Please help me fix it.

Specifically, I will provide you with my image, represented as a matrix of $$$n \times m$$$ integers. The edges of the matrix "loop around", meaning that the left-most column is considered adjacent to the right-most column, and the top-most row is considered adjacent to the bottom-most row. To fully process the image, we will apply $$$k$$$ transformations sequentially on the image. These transformations will be of the following form (where +x is to the right, +y is up):

• Blur: Given a pixel $$$(i, j)$$$ in the image, replace its value with the average (rounded down to the nearest integer) of its $$$3\times 3$$$ neighboring pixels in the input image (from the original unblurred image), with the edge pixels wrapping around to the opposite side of the image.
• Shift x y: Shift each pixel by $$$x$$$ units horizontally in the +x (right) direction and $$$y$$$ units vertically in the +y direction (up), with the edge pixels wrapping around to the opposite side of the image.
• Sharpen: Given a pixel $$$(i, j)$$$ in the image, if its value is larger than all of its $$$3\times 3$$$ neighboring pixels in the input image (excluding itself, of course), add $$$100$$$ to its value. If its value is less than the minimum value among its $$$3\times 3$$$ neighboring pixels (excluding itself, of course), subtract $$$100$$$ from its value. Again, the edge pixels should wrap around the opposite side of the image when determining neighbors.
• Rotate CW: Rotate the image 90 degrees clockwise.
• Rotate CCW: Rotate the image 90 degrees counter-clockwise.
• Flip Horizontal: Flip the image across the y-axis.
• Flip Vertical: Flip the image across the x-axis.

Given the image and a list of $$$k$$$ operations, please be My Hero Photographia and provide me with the final image.

In Attack on Titan, Titans are a constant threat to humanity. These giant humanoid creatures can cause significant destruction and loss of life, and identifying them is crucial to protect civilians and defend against them.

In this fictional world, there are two primary nations, Marley and Paradis, and a number of small unnamed nations.

A long, long time ago, there were $$$N$$$ humans with the power of the Titans (initially all from different, small unnamed nations). As history progressed, smaller nations inevitably merged into the larger two nations, and many titan-transformers from the smaller nations were forced to join either Marley or Paradis.

As a historian, you are trying to recover some information about the battles between the nations, and the ultimate fates of each titan-transformer. You've collected a list of $$$Q$$$ historical records and sorted them in decreasing order of credibility. Each of the $$$Q$$$ statements describe a battle between Marley and Paradis and takes one of two forms:

• 0 a b: Titans $$$a$$$ and $$$b$$$ fought together and then both joined the same nation (either both joined Paradis or both joined Marley; the record doesn't specify which).
• 1 a b Titans a and b fought against each other and then both joined different nations (either Titan a joined Paradis and b joined Marley, or vice-versa).

Process each historical record in order. For each record $$$q_i$$$, if the information in that record contradicts facts derivable from previous records, print IMPOSSIBLE. Record $$$q_i$$$ is then discredited as potentially fake and you should ignore its information when considering all future records.

If $$$q_i$$$ does not contradict previous records, print the maximum number of titan-transformers that a single nation could have, based on the records you've processed so far. Also print the maximum number of different nations (including Marley and Paradis) that could harbor at least one of the $$$N$$$ Titans based on the records so far.

Important: a historical record might specify a battle involving the same Titan twice, where $$$a=b$$$. A record of the form 1 a a that specifies a Titan joined a different nation than themselves is a self-contradiction and automatically discredited.

Misaka has recently discovered the existence of one-way magical portals that allow quick travel between cities in Japan. She wants to investigate these portals, but she is too busy fighting the Russian military, the Russian Orthodox Church, and the Roman Catholic Church. Thankfully, she can command a network of clones of herself who can investigate the portals in her stead.