You are given an integer interval $$$[l,r]$$$. At first, your score $$$sco$$$ is equal to $$$0$$$.

Repeat the following process:

1. Choose an integer $$$x\in [l,r]$$$ uniformly at random, and update $$$sco := sco + x$$$.
2. If $$$l=r$$$, stop. Otherwise, replace $$$[l,r]$$$ by a uniformly random proper subinterval of $$$[l,r]$$$ and go back to step 1. In other words, letting $$$len=r-l+1$$$, there are $$$\frac{len(len+1)}{2}-1$$$ proper subintervals of $$$[l,r]$$$, each chosen with equal probability.

Your task is to find the expected value of $$$sco$$$. Output the answer modulo $$$998\,244\,353$$$.

Formally, let $$$M = 998\,244\,353$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x \lt M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

You are given a tree with $$$n$$$ nodes, rooted at node $$$1$$$. Each node $$$i$$$ contains $$$k_i$$$ items, all having the same price $$$p_i$$$.

You need to process several queries. Each query is described by four integers: $$$u$$$, $$$d$$$, $$$p_{\text{lower}}$$$, and $$$p_{\text{upper}}$$$.

For each query, you must determine the number of items that satisfy all of the following conditions:

• Their price lies within the range $$$[p_{\text{lower}}, p_{\text{upper}}]$$$.
• Their corresponding node lies within distance $$$d$$$ from node $$$u$$$.
• Their node lies on the shortest path from node $$$u$$$ to the root node (node $$$1$$$).

You have an infinite-storey building. Each floor has exactly $$$n$$$ rooms, and each room can accommodate one person.

Placing one person on floor $$$x$$$ (where floors are $$$1$$$-indexed: $$$x=1,2,3,\dots$$$) costs $$$2^{x}$$$ units of budget. You are given a total budget of $$$m$$$ and you must spend all of it.

Your task is to determine the maximum possible number of people you can accommodate while spending exactly $$$m$$$. If it is impossible to spend the budget exactly, output $$$-1$$$.

Fahim had only been at CloseAI for two weeks, but he already knew two things with absolute certainty:

1. The company's tokenization system was held together with duct tape, prayers, and legacy Bash scripts.
2. He did not like the CEO, Saltman, who walked around the office wearing sunglasses indoors and calling everyone "chat-bros".

One morning, Saltman burst into the engineering floor holding a pile of printed stack traces like a kindergarten art project gone wrong.

"Tokenization is broken again!" he shouted. "If we don't fix this, our shareholders will replace me with a bag of potatoes!"

Fahim stared at him. A thought crossed his mind: If I fix this, maybe they'll replace him with me.

The challenge? Every model at CloseAI was panicking because they had forgotten how to tokenize words. They needed a clean implementation of tokenization, or as Saltman called it, "that spicy token cruncher thing".

So Fahim sat down, cracked his knuckles, and dove into the problem:

You're given $$$n$$$ lowercase English words, and you must apply tokenization to them, like a hero saving a collapsing startup. Each unique character from 'a' to 'z' starts as its own token — basic, simple, unlike Saltman's understanding of machine learning.

Then comes the tokenization loop:

Fahim has to count all adjacent token pairs across all words. He must find the most frequent adjacent token— the one that appears more than anything else. If there's a tie, he chooses the lexicographically smallest adjacent token. Then he merges that pair into a new token, like smashing two puzzle pieces together with pure engineering rage. Fahim also has to handle overlapping cases properly. For example, in a word like 'aaa', the pair 'aa' appears twice but overlaps — he only merges the leftmost occurrence first, so 'aaa' becomes ['aa', 'a'] in one merge step.

He repeats this: count, pick, merge, replace everywhere. He keeps going until there are no adjacent pairs of tokens. That's when the algorithm ends, and all the final tokens must be printed.

As he coded, something incredible happened: the errors stopped. The server logs went silent. The models started tokenizing again without screaming across the datacenter. Before anyone realized, the entire company was running smoothly.

Saltman strutted over and said, "Nice work, chat-bro. You've saved CloseAI."

Fahim smiled. One step closer to taking your job, Saltman.

The Metropolitan University campus has a long street with $$$n$$$ streetlights arranged in a row, numbered from $$$1$$$ to $$$n$$$. Each streetlight is either on (represented by $$$1$$$) or off (represented by $$$0$$$).

The streetlights have a peculiar automatic control system. Every minute, the system updates all streetlights simultaneously according to the following rule:

For a streetlight at position $$$i$$$ (where $$$1 \le i \le n$$$), we define its neighbors as all positions $$$j$$$ such that $$$|i - j| = 1$$$ and $$$1 \le j \le n$$$.

A streetlight at position $$$i$$$ (where $$$1 \le i \le n$$$) toggles its state (on $$$\to$$$ off or off $$$\to$$$ on) if and only if it has exactly two neighbors and both of them were on in the previous minute.

You are given the initial state of all streetlights. Your task is to determine the state of all streetlights after exactly $$$k$$$ minutes.

Alice and Bob have been close ever since high school. Now they both study at Martian University (MU), but in different departments located far apart. Their schedules are packed, and their classes take place in buildings scattered across the campus. Even though they want to spend time together, they can only meet during the short breaks between their classes.

The campus has $$$N$$$ buildings connected by $$$M$$$ undirected roads. Each road requires a certain amount of time to walk. Both Alice and Bob have several classes throughout the day, each class occurs at a specific building and lasts between a given start and end time. Class intervals do not overlap for each student. Since days on Mars do not follow Earth's fixed length, MU measures time on its own continuous scale, and a single day may be arbitrarily long. As a result, class start and end times can be large values.

Between two consecutive classes of their own, a student may roam the campus freely, traveling along any roads and visiting any buildings, as long as they arrive at their next class on time. Alice and Bob can meet only if they are in the same building at the same moment, during free periods for both. They are dedicated to their studies and will not be late to any class. They also work part time before and after their class schedules, so they will only meet between classes, never before the first class or after the last one.

Alice and Bob may choose different buildings to meet during different free intervals. Your task is to determine the maximum total time they can spend together during the day.

You are given a tree consisting of $$$N$$$ nodes numbered from $$$1$$$ to $$$N$$$, connected by $$$N-1$$$ edges.

You are also given a list of $$$M$$$ distinct "special" nodes. The remaining $$$N-M$$$ nodes are "normal."

You can move between nodes along the tree edges.

• Normal nodes can be visited any number of times.
• Each special node can be visited at most once during your entire journey.

For each node $$$i$$$ $$$(1 \le i \le N)$$$, determine the maximum number of distinct nodes that can be visited in a single continuous journey starting from node $$$i$$$.

This is an interactive problem. You must flush the output after printing each line. For example, in C++ use fflush(stdout), in Java — System.out.flush(), in Pascal — flush(output), and in Python — sys.stdout.flush().

Two players, A and B, are playing on a pile of $$$N$$$ stones. Player A moves first, and then they alternate turns. On each move, a player may remove any number of stones from $$$1$$$ to $$$k$$$, but not more than the number currently in the pile. A player who cannot move loses.

The value of $$$k$$$ is an unknown integer satisfying $$$1 \le k \le 1000$$$. Your task is to determine this unknown value.

You may ask queries. A query is a single integer $$$N$$$ ($$$1 \le N \le 10^{18}$$$). For this $$$N$$$, the system simulates optimal play and replies with "A" if player A wins, or "B" if player B wins.

You may ask at most $$$70$$$ queries (not counting the final answer).

You are playing a 3D version of Fruit Ninja. A strange fruit appears — it is shaped like a tetrahedron, defined by $$$4$$$ points in 3d-space that do not lie on the same plane.

To get a perfect score, you must slice the fruit with a single plane so that the two pieces have exactly equal volume.

The fruit's vertices are:

$$$$$$P_1(x_1,y_1,z_1), P_2(x_2,y_2,z_2), P_3(x_3,y_3,z_3), P_4(x_4,y_4,z_4)$$$$$$

Your task is to output any plane that cuts the tetrahedron into two equal-volume parts.

A plane is written as: $$$ax + by + cz + d = 0$$$

A correct answer is guaranteed to exist, and if there are multiple such slicing planes, you may output any.

You are given an array $$$a$$$ of size $$$n$$$ consisting of non-negative integers. At first, your score is $$$0$$$.

You can perform the following operation:

• Choose an index $$$i$$$ $$$(1 \leq i \lt |a|)$$$, increase your score by $$$(a_i + a_{i+1})$$$.
• Then, insert $$$(a_i + a_{i+1})$$$ between $$$a_i$$$ and $$$a_{i+1}$$$. Note that after inserting, the size of the array is increased by $$$1$$$.

You need to answer $$$q$$$ independent queries. For the $$$i$$$-th query, given a number $$$x_i$$$, you should find the maximum score you can obtain after performing exactly $$$x_i$$$ operations. Since the answer may be large, output the answer modulo $$$998\,244\,353$$$.