Nezha caused conflicts due to the dominance of the Dragon Palace. In order to uphold justice and protect the people, Nezha caused three incidents in the sea. The specific process and outcome are as follows:

The 1st sea-tussle: Slayed the Yaksha Li Gen, took A hours;

The 2nd sea-tussle: Subdued Ao Bing, the third son of the Dragon King, took B hours;

The 3rd sea-tussle: Forced the Dragon King to submit, took C hours.

Nezha's disturbance in the sea would cause complaints. For every hour he causes trouble in the sea, he would generate D complaints. So, how many complaints did Nezha's disturbance in the sea cause in total?

You are given a binary matrix consisting of 0s and 1s. All the 1s form a single connected component under 4-directional connectivity (i.e., cells are connected if they share a side: up, down, left, or right).

Your task is to build a 2-layer LEGO structure exactly covering the region of 1s using the following three types of bricks:

• 1×1 brick: covers exactly one cell.
• 1×2 brick: covers two adjacent cells, and can be placed either horizontally or vertically.
• L-shape brick: covers three cells forming an "L" shape — for example, a cell and its top and right neighbors. All four 90-degree rotations of this shape are allowed.

Your goal is to cover all the 1s using the specified types of bricks on both two layers while leaving all the 0s empty on both two layers. In addition, the entire LEGO structure must be structurally stable — that is, it Does Not Fall Apart.

We define two bricks to be adjacent if they are in different layer and share at least one common cell. A LEGO structure is said Does Not Fall Apart if all bricks form a single connected component through such adjacency.

If any solution exists, output any one of them. Otherwise, output -1.

Formally, you are given an $$$n \times m$$$ binary matrix $$$A$$$. You need to output two $$$n \times m$$$ matrices $$$B_0$$$ and $$$B_1$$$ representing the brick IDs on the upper and lower layers. Your output must satisfy the following:

• Exact Coverage: If $$$A_{x, y} = 1$$$, then $$$B_{0,x,y}, B_{1,x,y} \in [1, 2nm]$$$. If $$$A_{x, y} = 0$$$, then $$$B_{0,x,y} = B_{1,x,y} = 0$$$.
• Valid Bricks: Each brick ID appears only on one layer. Its occupied cells must form a valid shape: 1×1, 1×2, or L-shaped.
• Does Not Fall Apart: Define two bricks $$$i$$$ and $$$j$$$ adjacent if there exists $$$(x, y)$$$ such that $$$\{B_{0,x,y}, B_{1,x,y}\} = \{i, j\}$$$. All bricks occur in $$$B$$$ must form a single connected component through such adjacency.

"My name is D'Arby, D-A-R-B-Y. The "D" has an apostrophe."

The Stardust Crusaders, after a long journey, finally arrived at their destination—Cairo, Egypt. They immediately visited a nearby café to inquire about Dio's mansion. A customer there calmly remarked, "I recall that mansion." When Joseph Joestar pressed for details, the customer demanded a gamble in exchange for information. Joseph and Polnareff wagered against this customer, the enemy Stand Master Daniel J. D'Arby, but lost and had their souls stolen. To reclaim their souls, Kujo Jotaro challenges D'Arby...

Jotaro and D'Arby play a poker game under these rules: They use a shuffled 52-card deck (no jokers)$$$^{\text{∗}}$$$, and each initially draws 5 random cards. Players know only their own hands. Jotaro can discard $$$k\ (k \gt 0)$$$ of his cards (without returning them to the deck) and draw $$$k$$$ new cards from the remaining deck. After this, both reveal their hands and compare the total point sums. If Jotaro's sum exceeds D'Arby's, he gains $$$k$$$ chips; if his sum is smaller, he loses $$$k$$$ chips; if equal, the chips remain unchanged.

Jotaro wants to compute the maximum expected value of chips he can obtain for each $$$k=1,2,\cdots,5$$$, assuming he makes optimal decisions when discarding and redrawing cards. Specifically, for each $$$k$$$, calculate the expected value of the maximum possible chip outcome.

All answers must be computed modulo $$$998244353$$$$$$^{\text{†}}$$$.

"Take this, DIO! 20-meter radius Emerald Splash—!"

The Stardust Crusaders, after overcoming countless obstacles and repelling waves of enemies, finally arrived in Egypt for their ultimate confrontation with Dio. Facing Dio, their strategy involved Joseph Joestar and Kakyoin engaging in tactical retreats while fighting, while Kujo Jotaro and Polnareff pursued from the rear, forming a pincer attack. Amidst the chaos, Kakyoin devised a plan to uncover the abilities of Dio's Stand "The World", by setting traps across nearby structures.

As Dio pursued Kakyoin, he became ensnared in the barrier deployed by Kakyoin's Hierophant Green. The ensuing confrontation unleashed a concentrated barrage of Emerald Splash attacks...

Kakyoin has deployed a barrier of "Hierophant Green" within a cuboid region. For calculation purposes, we place the cuboid in a Cartesian coordinate system, with one vertex at the origin $$$(0,0,0)$$$ and the opposite vertex at $$$(a,b,c)$$$, where $$$a$$$, $$$b$$$, and $$$c$$$ represent the length, width, and height of the cuboid respectively. The barrier contains several tentacles, each defined as a line segment from $$$(x_1,y_1,z_1)$$$ to $$$(x_2,y_2,z_2)$$$, where both endpoints lie on the boundary of the cuboid.

Dio may appear at any position within the cuboid (including boundaries). According to the plan, Dio will execute a single attack by generating an infinitely large plane perpendicular to one of the coordinate axes ($$$x-$$$, $$$y-$$$, or $$$z-$$$ axis) and centered at his position. All tentacles intersecting Dio's attack range (i.e., there exists a point that lies on both the tentacle and Dio's attack plane) will be severed. Each severed tentacle will launch an Emerald Splash attack against Dio exactly once.

Kakyoin wants to determine: What is the maximum number of Emerald Splash attacks Dio could receive considering all possible positions he might occupy and all valid attack directions after the barrier is deployed?

Formalized statement: Given $$$n$$$ line segments in three-dimensional space with their endpoints restricted to a given cuboid, determine the maximum number of segments intersected by any plane that is perpendicular to one of the coordinate axes. A line segment is considered to intersect a plane if and only if there exists a point that lies on both the line segment and the plane.

We use $$$|s|$$$ to denote the length of string $$$s$$$, and $$$s_i$$$ to denote the $$$i$$$-th character of $$$s$$$. A substring of $$$s$$$, denoted $$$s_{l\ldots r}$$$ ($$$1 \le l \le r \le |s|$$$), refers to the string formed by concatenating the $$$r - l + 1$$$ characters $$$s_l, s_{l+1}, \ldots, s_r$$$. We say that $$$s$$$ is a $$$k$$$-fold string if and only if there exists a string $$$t$$$ such that $$$s = t^k$$$, i.e., $$$k$$$ copies of $$$t$$$ concatenated end-to-end exactly form $$$s$$$.

Aqua wants to know, given string $$$s$$$ and positive integers $$$x, y$$$, how many pairs of positive integers $$$l, r$$$ satisfy $$$x \le l \le r \le y$$$ and the substring $$$s_{l\ldots r}$$$ can be rearranged to become a $$$k$$$-fold string. Since Aqua likes high-performance programs, you need to answer $$$q$$$ queries $$$(x_1, y_1), (x_2, y_2), \ldots, (x_q, y_q)$$$.

Red Dragon Dew's master believes that she has been eating too much recently, causing her to wobble when taking off and reducing her cruising time. Therefore, he ordered her to control her caloric intake.

Over the next $$$n$$$ days, suppose that on the $$$i$$$-th day, Dew consumed $$$r_i$$$ calories and metabolized $$$c_i$$$ grams of mass. According to the characteristics of her dragon species, the mass loss should be $$$c_i = p \times c_{i-1} + (1 - p) \times r_{i-1}$$$, where the parameters $$$r_0$$$, $$$c_0$$$, and $$$p$$$ ($$$0 \lt p \lt 1$$$) have been measured by her master.

Of course, Red Dragon Dew indicated that she would not fully obey commands from her "cook" . She stated that over the next $$$n$$$ days, there are $$$k$$$ days when she will have indulgent meals. The caloric intake on these $$$k$$$ days is predetermined, and the daily caloric intake must be within the range $$$[L, R]$$$, i.e. all $$$r_i$$$ should in range $$$[L,R]$$$.

Given these conditions, Dew wants to arrange the days without indulgent meals to maximize the difference between the total caloric consumption and intake over the next $$$n$$$ days, i.e. $$$\max\sum_{i=1}^n (c_i-r_i)$$$.

Alice is exploring a dangerous large maze. This maze has $$$n$$$ caves (labeled from $$$1$$$ to $$$n$$$) and $$$m$$$ one-way passages connecting any two of these caves (because some traps in the passages make it difficult to return once passed). Each passage is represented as $$$(u, v)$$$, where $$$u$$$ is the starting cave and $$$v$$$ is the destination cave. Each passage $$$(u, v)$$$ has a difficulty value $$$d_{(u, v)}$$$. In other words, you can think of the entire cave system as a weighted directed graph.

At the beginning, Alice has an initial stamina (or it can be called 'energy') $$$x$$$. When she traverses a passage with difficulty value $$$d$$$, her stamina $$$x$$$ changes to $$$\lfloor \frac{x}{d} \rfloor$$$ (where $$$\lfloor\ \rfloor$$$ is the floor function). When Alice's stamina drops to $$$0$$$, it is considered that her stamina is exhausted, and she can no longer continue exploring.

For a example: Suppose Alice starts with a stamina value of $$$9$$$. After traversing a passage with difficulty $$$2$$$, her stamina becomes $$$4$$$ (since $$$\lfloor \frac{9}{2}\rfloor = 4$$$). If she then traverses another passage with difficulty $$$2$$$, her stamina drops to $$$2$$$ ($$$\lfloor \frac{4}{2}\rfloor = 2$$$). Finally, after traversing a passage with difficulty $$$3$$$, her stamina becomes $$$0$$$ ($$$\lfloor \frac{2}{3}\rfloor = 0$$$), at which point her stamina is exhausted.

Since Alice has a poor sense of direction in the maze, at any point during her exploration, she does not know which cave she is currently in or where each passage leads. Therefore, Alice has $$$Q$$$ questions. For the $$$i$$$-th question, she wants to ask: If she starts from cave $$$p_i$$$ with an initial stamina of $$$x_i$$$, and each time she randomly chooses a passage she can take, what is the minimum number of passages she must traverse before her stamina is exhausted? ($$$\textbf{Note}$$$: If Alice traverses a passage she has taken before, her stamina will still decrease in the same way, i.e., from $$$x$$$ to $$$\lfloor \frac{x}{d}\rfloor$$$.)

It is guaranteed that every cave has at least one outgoing one-way passage (the starting and ending caves of a passage may be the same).

Red Dragon Dew forwarded a picture of a Bingo game:

The above is an example of a $$$5\times 5$$$ Bingo game.

For an $$$n\times n$$$ Bingo game, the player must read the description on each cell and check off all the cells that satisfy the description. If the checked cells form at least one line (horizontally, vertically, or along either of the two diagonals), then the player is considered to have succeeded in the game.

Now, Red Dragon Dew wants to know the maximum number of cells that can be checked while ensuring the player still fails. That task is too simple, so she further wants to know: how many different schemes are there for checking the maximum number of cells such that the player fails?

Specifically, if there is a cell that is unchecked in one scheme and checked in another, then the two schemes are considered different. To avoid excessively large outputs, the final answer is taken modulo $$$998244353$$$.

TreeQwQ is busy dating with girls. There are $$$n$$$ time slots in a day numbered from $$$1$$$ to $$$n$$$. TreeQwQ is going on some dates today. He will give you a binary string $$$s$$$ to describe his schedule. $$$s_i = 1$$$ denotes TreeQwQ is dating in time slot $$$i$$$ while $$$s_i = 0$$$ denotes he is free in time slot $$$i$$$.

However, he finds his schedule boring because he has too many girls to date with. So you can help him by performing the following operation on his schedule exactly once.

• First, select an range $$$[l,r](1\leq l\leq r\leq n)$$$ such that there are exactly $$$k$$$ dating time slots from time slot $$$l$$$ to time slot $$$r$$$(inclusive).
• After selection, you can arbitrarily modify the states of the time slots(that is changing a time slot from dating to free, vice versa) from the $$$l$$$-th to the $$$r$$$-th time slot any times.
• After all the modifications, you need to guarantee that there are still exactly $$$k$$$ dating time slots from time slot $$$l$$$ to time slot $$$r$$$(inclusive).

TreeQwQ wants to know how many possible schedules he can get after performing the operation. Since the number may be very large. You need to tell TreeQwQ the number modulo $$$998244353$$$.

Note that two schedules are called different if there exists a time slot that TreeQwQ is dating in one schedule while he is free in the same time slot in the other schedule.

Red Dragon Dew has recently become obsessed with Plants vs. Zombies Fusion Edition (by the Lan Piaopiao team). Like the original Plants vs. Zombies, there is a plant called the Hot Pepper, which can damage all zombies in a row simultaneously. Based on this, Dew came up with a problem:

On an infinite two-dimensional grid, each cell can hold at most one pepper. There are two types of peppers: one that explodes vertically (parallel to the y-axis) and one that explodes horizontally (parallel to the x-axis). Now, there are already $$$k$$$ peppers with fixed types on the grid, and Dew wants to know the minimum number of additional peppers that need to be placed so that every pepper is burned by at least one other pepper.

Formally, given a set of triples $$$S=\{(x,y,w)\}$$$, where $$$(x,y,w)\in U$$$ and $$$U=N\times N\times \{0,1\}$$$, the problem asks for the minimum number of additional elements $$$(x,y,w)\in U$$$ to be added to $$$S$$$ such that for every $$$(x_0,y_0,w_0)\in S$$$, there exists either an element $$$(x_0,y',0) \in S,y'\not=y_0$$$ or an element $$$(x',y_0,1)\in S,x'\not=x_0$$$. Meanwhile, the set must satisfy that for any two elements $$$(x_1,y_1,w_1)$$$ and $$$(x_2,y_2,w_2)$$$ in $$$S$$$, it is not the case that both $$$x_1=x_2$$$ and $$$y_1=y_2$$$ simultaneously.

You have $$$n$$$ stone statues, each with a nose. The statues can face $$$4$$$ directions: front, right, back, or left.

Each time you can either:

• Press the nose of one statue, causing all other statues to rotate $$$90^{\circ}$$$ clockwise simultaneously; or
• Press your own nose, causing all statues to rotate $$$90^{\circ}$$$ clockwise.

What is the minimum number of presses needed to make all statues face front?

redemption

nothingness

rebirth

Why are you crying?

Luvia gives you a tree with $$$n$$$ nodes numbered $$$1 \sim n$$$, and $$$q$$$ queries $$$l,r,x$$$,

you should answer the LCA of nodes numbered $$$l \sim r$$$ when the root of the tree is $$$x$$$.

LCA means the lowerest common ancestor.

Little T and Little J are playing a coin-flipping game with $$$n$$$ coins, all initially facing up. First, they agree on a number $$$k$$$. Little T then flips exactly $$$k$$$ coins to face down, but Little J does not know which ones.

After that, Little J must assign each coin to one of four operations:

1. Place in the first pile (no flip)
2. Place in the first pile and flip
3. Place in the second pile (no flip)
4. Place in the second pile and flip

Example: When $$$n=5$$$ with operation sequence 12341:

• Coins 1, 2, 5 $$$\to$$$ first pile (coin $$$2$$$ is flipped)
• Coins 3, 4 $$$\to$$$ second pile (coin $$$4$$$ is flipped)

The game is won by Little J if and only if both piles have the same number of coins facing up after all operations. One of the piles is allowed to contain zero coins.

Your task is to determine whether there exists an operation sequence that guarantees Little J's victory for any possible choice of $$$k$$$ flipped coins by Little T. If such a sequence exists, construct it; otherwise, output $$$-1$$$.