Archaeologist Monocarp is exploring some ancient ruins when the heavy stone exit door suddenly slams shut, trapping him inside.

In the center of the ruins, he discovers an ancient artifact shaped like a tree consisting of $$$n$$$ vertices connected by $$$n - 1$$$ magical branches (undirected edges). Each branch contains a glowing magical stone inscribed with an integer weight $$$w$$$.

Monocarp studies the artifact and deduces the ancient rules for traversing its magical pathways. The cost of a simple path between any vertex $$$i$$$ and vertex $$$j$$$, denoted as $$$c(i, j)$$$, is equal to the bitwise XOR of the weights of all edges on the simple path between $$$i$$$ and $$$j$$$. If $$$i = j$$$, the cost is $$$0$$$.

Furthermore, one can travel between two vertices $$$u$$$ and $$$v$$$ using a sequence of intermediate jumps. The total distance $$$d(u, v)$$$ is defined as the minimum possible value of $$$\sum_{i=1}^{k-1} c(a_i, a_{i+1})$$$ over all possible sequences of vertices $$$a_1, a_2, \ldots, a_k$$$ of any length $$$k \ge 1$$$ such that $$$a_1 = u$$$ and $$$a_k = v$$$.

As Monocarp observes the artifact, he realizes the ruins are highly unstable. Occasionally, the magical stones fluctuate and the entire tree changes: a magical surge of value $$$x$$$ occurs, updating the weight of every edge $$$j$$$ to $$$w_j \oplus x$$$ (where $$$\oplus$$$ denotes the bitwise XOR operation).

Desperate to leave, Monocarp finds another ruin near the locked door bearing a cryptic scripture. The scripture indicates that the door will only open if he can correctly answer a series of questions based on the artifact's current state. For a given source vertex $$$s$$$, he must compute the sum of the minimum distances from $$$s$$$ to all vertices $$$i$$$ in the tree, i.e., $$$\sum_{i=1}^n d(s, i)$$$.

You are given $$$q$$$ events (either a magical surge or a query from the scripture). Help Monocarp compute the answers for the scripture to open the door and escape!

Bog the Frog lives in a peaceful pond containing $$$n$$$ lily pads, uniquely numbered from $$$1$$$ to $$$n$$$. He wants to plan a journey to visit every single lily pad exactly once.

Bog can begin his journey from any lily pad. However, Bog has strict jumping rules: he can only leap from his current lily pad to the next one if the absolute difference between their numbers is a prime number.

Because Bog likes to keep his travel logs neatly organized, he wants his path to be the lexicographically smallest$$$^{\text{∗}}$$$ sequence possible. Can you help Bog find the perfect sequence of lily pads to jump to, or tell him if such a journey is impossible?

Alice and Bob are given an array $$$a$$$ consisting of $$$n$$$ integers. They decided to play a game on it.

The players take turns making moves, with Alice moving first. In each move, the player must choose two indices $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$) such that all of the following conditions are satisfied:

• $$$l = 1$$$ or $$$a_l \ne a_{l-1}$$$;
• $$$a_i = a_{i-1}$$$ for all $$$l \lt i \le r$$$;
• $$$r = n$$$ or $$$a_r \ne a_{r+1}$$$.

After that, the segment $$$[a_l, a_{l+1}, \ldots, a_r]$$$ is deleted from the array $$$a$$$. The player who cannot make a move loses.

Furthermore, Alice has the ability to arbitrarily rearrange the array before starting the game. Determine who wins, if Alice can rearrange the array before making the first move, and assuming that both players play optimally.

Kusuo had been trapped inside a cage by Kusuke. To free himself, he needs to solve Kusuke's problem and to do it, he requires your help—

…wait, never mind. He already freed himself. Looks like he didn't need your help after all. Anyway, here's the problem if you still want to give it a try.

Let $$$n$$$ be an even integer. You are given a permutation $$$ p = [p_1, p_2, \dots, p_n] $$$ of the integers from $$$0$$$ to $$$n-1$$$.

Define an $$$n \times n$$$ matrix $$$a = [a_{i,j}]$$$ as $$$$$$ a_{i,j} = \begin{cases} \mathrm{mex}(p[i..j]), & i \le j, \\ a_{j,i}, & i \gt j, \end{cases} $$$$$$ — where $$$\mathrm{mex}(p[i..j])$$$$$$^{\text{∗}}$$$ is the minimum excluded element of the subarray $$$[p_i, p_{i+1}, \dots, p_j]$$$.

The score of the permutation $$$p$$$ is defined as $$$ f(p) = \det(a) $$$ (the determinant of $$$a$$$)$$$^{\text{†}}$$$.

To make the problem harder, Kusuke added $$$q$$$ queries. In each query, two indices $$$x$$$ and $$$y$$$ are given, and you swap $$$p_x$$$ and $$$p_y$$$.

The queries are persistent, meaning each swap permanently modifies the permutation and affects all subsequent queries.

After each query, output the score of the current permutation.

In the ancient kingdom of Insomnia, the Royal Mathematician has discovered a strange and powerful sequence known as the Resonating Array. It is said that such an array holds the key to unlocking the kingdom's greatest secrets — but only if it is constructed correctly. The rule is simple yet mysterious.

For every pair of consecutive elements in the array, the remainder when the first element is divided by the second must be exactly $$$1$$$.

Formally, if the array is $$$a_1, a_2, \dots, a_n$$$, then for every $$$1 \le i \lt n$$$, we must have $$$a_i \bmod a_{i+1} = 1$$$.

The king has requested the lexicographically smallest$$$^{\text{∗}}$$$ such array of length $$$n$$$, using positive integers.

Can you help the Royal Mathematician find it before the kingdom falls into chaos?

There are $$$n$$$ players in the academy, numbered from $$$1$$$ to $$$n$$$. To practice quick decision-making, they introduce a drill with the following rules:

• Initially, each player has exactly one ball.
• Each player must pass their ball exactly once.
• A player must pass the ball to another player (passing to themselves is not allowed).
• After all passes are made, a player may receive balls from multiple teammates or from none.
• A player is called forgotten if they do not receive a ball from any player.

Your task is to determine the number of possible passing arrangements such that exactly one player is forgotten.

Since the answer may be large, print it modulo $$$998\,244\,353$$$.

Alice and Bob are playing a game on an array of integers.

They are given an array $$$a$$$ of length $$$n$$$. The players take turns making moves, with Alice moving first.

In a move, the player must select a non-empty subsequence$$$^{\text{∗}}$$$ of the array such that there exists at least one element in the subsequence which is not equal to the $$$\gcd$$$ of all elements in the subsequence.

Let $$$\text{g}$$$ denote the gcd of the selected subsequence. After selecting the subsequence, the player must replace all the elements in the chosen subsequence with the value $$$\text{g}$$$.

More formally, suppose the chosen subsequence corresponds to the indices $$$i_1, i_2, \ldots, i_k$$$. Let $$$$$$ \text{g} = \gcd(a_{i_1}, a_{i_2}, \ldots, a_{i_k}) $$$$$$ The subsequence is valid only if and only if $$$$$$ \exists j \in \{1,2,\ldots,k\} \text{ such that } a_{i_j} \ne \text{g} $$$$$$ After choosing a valid subsequence, set $$$a_{i_j} := \text{g}$$$ for all $$$1 \le j \le k$$$.

The players continue alternating moves on the updated array.

The first player who cannot make a move $$$\color{red}{\text{wins}}$$$.

Assuming both players play optimally, determine who will win the game.

You are given a weighted undirected graph with $$$n$$$ nodes and $$$m$$$ edges. Each edge has a weight $$$w$$$, representing the time required to travel through that edge.

You start at node $$$a$$$ and want to reach node $$$b$$$.

Some nodes contain shelters. If you arrive at a shelter, you may stop and rest there. Resting resets your continuous travel time counter to zero, and resting does not add to the travel time.

It is raining, and you cannot travel continuously under the rain for more than $$$k$$$ units of time.

Formally, along any path from $$$a$$$ to $$$b$$$, the sum of edge weights between two consecutive shelter nodes must not exceed $$$k$$$. The same restriction also applies between the start node $$$a$$$ and the first shelter visited, and between the last shelter visited and the destination node $$$b$$$.

Determine whether it is possible to reach node $$$b$$$ from node $$$a$$$ while respecting this constraint.

You are given two integer sequences: $$$[a_1, a_2, \ldots , a_{n-1}]$$$ and $$$[c_1, c_2, \ldots , c_n]$$$.

You build a random rooted tree $$$T_n$$$ with vertex set $$${1, 2, \ldots , n}$$$ as follows:

• Initially, $$$T_n$$$ consists of only vertex $$$1$$$ which is the root.
• For each $$$i = 2, 3, \ldots , n$$$, we add vertex $$$i$$$ and connect it by an edge to exactly one vertex $$$j \in \{1, 2, ... , i−1\}$$$. The vertex $$$j$$$ is chosen randomly with probability $$$\frac{a_j}{a_1 + a_2 + \ldots + a_{i-1}}$$$.
• When $$$T_n$$$ is built, the process stops.

Let $$$$$$F = \sum_{i \in S}{c_i}$$$$$$

where $$$S$$$ is the set of leaf vertices$$$^{\text{∗}}$$$ in $$$T_n$$$.

Find the expected value of $$$F$$$.

Jasper is a world-renowned jeweler who has just acquired $$$n$$$ rare gemstones. Each gemstone has a certain luster value $$$a_i$$$. To showcase them in his gallery, Jasper needs to arrange these stones into exactly $$$k$$$ non-empty display cases.

Jasper is a perfectionist. For any display case $$$s$$$ containing $$$m$$$ stones, he defines the Visual Strain $$$f(s)$$$ as the sum of the differences between the maximum and minimum luster seen so far as a visitor walks past the case from left to right. Formally, if the stones are placed in the order $$$s_1, s_2, \dots, s_m$$$, the strain is:

$$$$$$ f(s) = \sum_{i=1}^{m} \left( \max_{1 \le j \le i} \{s_j\} - \min_{1 \le j \le i} \{s_j\} \right) $$$$$$

Jasper knows the order within a case matters. For each case, he will expertly rearrange the stones he is given to ensure the Visual Strain is as small as possible. Let $$$g(s)$$$ be the minimum possible value of $$$f(s)$$$ across all $$$m!$$$ permutations of the stones in $$$s$$$.

Your task is to partition the $$$n$$$ gemstones into exactly $$$k$$$ disjoint non-empty subsequences $$$s_1, s_2, \dots, s_k$$$ such that every gemstone belongs to exactly one subsequence, and the total Visual Strain $$$\sum_{i=1}^{k} g(s_i)$$$ is minimized.

Alice is tracking her mood swings for the next $$$n$$$ days. Each day her mood will randomly be either bad ($$$0$$$) or good ($$$1$$$), independently with equal probability.

After $$$n$$$ days, Alice looks back at the sequence of moods and wants to remember a period where her mood only improves or stays the same. To do this, she selects a subsequence$$$^{\text{∗}}$$$ of days such that her mood never gets worse as time goes forward. In other words, once she chooses a day with mood $$$1$$$, she cannot later choose a day with mood $$$0$$$.

Among all such subsequences, Alice always chooses one with the maximum possible length. Let $$$f(S)$$$ denote this length for a mood sequence $$$S$$$.

Since the moods are generated randomly, Alice wonders what value to expect.

Formally, consider all binary strings $$$S$$$ of length $$$n$$$, each occurring with probability $$$\frac{1}{2^n}$$$. Compute the expected value of $$$f(S)$$$.

The ancient Kingdom of Lumina consists of $$$n$$$ cities connected by $$$m$$$ bidirectional magical leylines. Each leyline possesses a base resonance, represented by an integer $$$w$$$. This resonance can be positive (harmonious), negative (dissonant), or even zero (inert).

The High Mage wishes to establish a grand unified network—a subset of exactly $$$n - 1$$$ leylines that connects all $$$n$$$ cities together so that magic can flow freely between any two cities.

The overall instability of a chosen network is defined as the product of the resonances of its constituent leylines. To prevent a catastrophic magical surge, the High Mage must select a network that minimizes this instability.

Because the leylines are powerful, the minimum instability can be an exceptionally large positive or negative number. You are tasked with finding the minimum possible instability and reporting it modulo $$$10^9 + 7$$$.

Note on Modulo Arithmetic: The answer must be the mathematically correct modulo. If the true minimum product is $$$P$$$, you should output $$$(P \pmod{10^9 + 7} + 10^9 + 7) \pmod{10^9 + 7}$$$. You are minimizing the actual integer product first, and then applying the modulo to that minimum value.

You are given two integers $$$n$$$ and $$$m$$$.

Find the number of ordered pairs $$$(a, b)$$$ that satisfy:

• $$$1 \le a \le n$$$;
• $$$1 \le b \le m$$$;
• $$$(a \bmod b)$$$ $$$+$$$ $$$(b \bmod a)$$$ $$$=$$$ $$$(a$$$ $$$|$$$ $$$b)$$$.

Note that $$$|$$$ denotes the bitwise OR operator.

Anup was working tirelessly to finalize the problem set for the upcoming Insomnia contest. Meanwhile, Darsh, having absolutely nothing better to do, wandered over to demand a treat(chapo in local lingo). Hoping to get back to work, Anup struck a deal: Darsh would get his chapo, but only if he could first solve a seemingly innocent, yet "not-so-simple" problem.

Anup describes a process to build a tree:

Given an integer $$$n$$$, construct an array $$$a[a_1,a_2,\ldots,a_n]$$$ of size $$$n$$$ consisting of zeroes and ones where $$$a_1= 0 $$$. Consider a tree with $$$n+1$$$ vertices labeled $$$0, 1, 2, \ldots, n$$$, where vertex $$$0$$$ is designated as the root.

For each $$$i = 1, 2, 3, \ldots, n$$$, if:

• $$$a_i = 0$$$, add an edge between vertex $$$i$$$ and vertex $$$i-1$$$;
• $$$a_i = 1$$$, add an edge between vertex $$$i$$$ and vertex $$$i-2$$$.

Let $$$h(a)$$$ be the height of the tree for one possible valid array $$$a$$$. Anup asks Darsh to find the sum of $$$h(a)$$$ over all possible valid arrays of $$$0$$$s and $$$1$$$s where $$$a_1 = 0$$$. Since this sum can be incredibly large, output the answer modulo $$$10^9 + 7$$$.

You are given an array $$$a$$$ of length $$$n$$$ consisting of positive integers.

An index $$$i$$$ $$$(1 \le i \lt n)$$$ splits the array into two non empty subarrays: $$$[a_1, a_2, \dots, a_i]$$$ and $$$[a_{i+1}, a_{i+2}, \dots, a_n]$$$.

We call an index $$$i$$$ good if it is possible to make

$$$$$$ \gcd(a_1, a_2, \dots, a_i) = \gcd(a_{i+1}, a_{i+2}, \dots, a_n) $$$$$$

by changing the value of at most one element in the array to any positive integer.

Note that the modification (if any) can be applied to any position in the array and is considered independently for each index.

Your task is to determine the number of good indices.