You are given a sequence of non-negative integers $$$a_1, a_2, \dots, a_n$$$ of length $$$n$$$.

There are $$$q$$$ queries. Each query provides an interval $$$[l, r]$$$. For each query, you need to consider the multiset $$$V$$$ formed by the elements in the interval $$$[l, r]$$$, and select a subset $$$M \subseteq V$$$ of maximum size such that all elements in $$$M$$$ have pairwise distinct values.

After that, you may choose any subset $$$T \subseteq M$$$ (including the empty set). Let $$$|M|$$$ denote the size of set $$$M$$$, and let $$$X_T$$$ denote the bitwise XOR of all elements in $$$T$$$ (the XOR of the empty set is defined as $$$0$$$). Your task is to compute the minimum possible value of $$$|M| \oplus X_T$$$.

This problem is online. The query inputs $$$l', r'$$$ are encrypted. Let the answer to the previous query be $$$lastans$$$ (initially $$$lastans = 0$$$). The actual query endpoints $$$l, r$$$ are obtained as follows:

$$$$$$l = (l' \oplus lastans) \bmod n + 1$$$$$$

$$$$$$r = (r' \oplus lastans) \bmod n + 1$$$$$$

After decryption, if $$$l \gt r$$$, you should swap $$$l$$$ and $$$r$$$.

There are $$$n$$$ consecutive bus seats arranged in a line, numbered from $$$1$$$ to $$$n$$$. Due to long-term disrepair, $$$m$$$ of these seats are broken.

Alice and Bob take turns seating passengers, with Alice moving first. In each move, the current player must choose an unbroken and currently empty seat $$$i$$$ for a passenger, subject to the following condition:

All seats $$$j$$$ satisfying $$$|j - i| \le k$$$ and $$$j \ne i$$$ must be empty (that is, all other seats within distance at most $$$k$$$ from $$$i$$$ must be unoccupied. Note that broken seats do not affect this distance check; the distance is still computed across broken seats).

After the passenger sits down, seat $$$i$$$ becomes occupied. If the current player can no longer find any legal empty seat for seating a passenger, the game ends immediately. Alice wants the total number of seated passengers to be as large as possible, while Bob wants it to be as small as possible. Both players play optimally.

Please output the final possible seat configuration of the bus as a string.

The Ao–Tai Line is a high-altitude hiking route connecting Aoshan and Taibai Mountain in the Qinling Mountains. It is famous for its unpredictable weather, steep terrain, and thin oxygen, and is known as a dangerous route that "walks along the backbone of China." Along this route, each type of terrain corresponds to a different level of expedition difficulty and resource supply.

As an experienced explorer, Fanfan needs to plan a safe path from the starting point to the destination. Whenever Fanfan reaches a location, a certain amount of stamina is consumed, and some supplies are either consumed or replenished. We use an $$$n \times m$$$ mountain map to model this route, where each location is marked with a value.

You need to start from the upper-left corner $$$(1,1)$$$ and reach the lower-right corner $$$(n,m)$$$. You may move in the four directions: up, down, left, and right, and you may visit the same location multiple times.

Suppose the values of the locations along the explorer's path are $$$a_1, a_2, \ldots, a_k$$$, where $$$a_1$$$ is the value at the starting point $$$(1,1)$$$ and $$$a_k$$$ is the value at the ending point $$$(n,m)$$$. Define:

The stamina consumed as $$$OR = a_1 \mid a_2 \mid \ldots \mid a_k$$$ (bitwise OR),

The supplies remaining as $$$AND = a_1 \& a_2 \& \ldots \& a_k$$$ (bitwise AND).

Your task is to minimize the stamina consumed, and among all such paths, maximize the supplies remaining. Output the minimum stamina consumption and the maximum supplies remaining satisfying the condition.

Taffy gives you an integer $$$c$$$.

You need to help Taffy find two positive integers $$$a$$$ and $$$b$$$ such that $$$a + b = c$$$, and their least common multiple $$$\text{lcm}(a, b)$$$ is maximized.

The least common multiple of two positive integers $$$a$$$ and $$$b$$$ is the smallest positive integer that is divisible by both $$$a$$$ and $$$b$$$.

As everyone knows, Cirno's favorite number is $$$9$$$!

Today, Cirno gets a positive integer $$$x$$$. She suddenly wonders: can she find another positive integer $$$k$$$ such that their product $$$x \cdot k$$$ becomes a number whose every digit is $$$9$$$ (for example, $$$9$$$, $$$99$$$, $$$999999$$$, and so on)?

Fanfan has a valid bracket sequence $$$s$$$ containing $$$n$$$ bracket pairs, and all bracket pairs are numbered from $$$1$$$ to $$$n$$$. The numbering is assigned according to the order in which the left brackets appear: the first left bracket that appears and its matching right bracket form bracket pair $$$1$$$, the second left bracket that appears and its matching right bracket form bracket pair $$$2$$$, and so on.

Based on this valid bracket sequence, Fanfan constructs a binary tree according to the following rules:

For the bracket pair numbered $$$p$$$ (whose corresponding bracket positions in the sequence are $$$s_i$$$ and $$$s_j$$$, where $$$s_i$$$ is a left bracket and $$$s_j$$$ is the matching right bracket), we examine $$$s_{i+1}$$$ and $$$s_{j+1}$$$:

If $$$s_{i+1}$$$ is a left bracket, then let the corresponding bracket pair be numbered $$$l$$$, and make $$$l$$$ the left child of $$$p$$$;

If $$$s_{j+1}$$$ is a left bracket, then let the corresponding bracket pair be numbered $$$r$$$, and make $$$r$$$ the right child of $$$p$$$.

Now, Fanfan has lost the original bracket sequence $$$s$$$, but the constructed binary tree structure is still available. Your task is to reconstruct the original valid bracket sequence $$$s$$$ from the given binary tree.

Mage Taffy is fighting against $$$N$$$ goblins. She will cast $$$N$$$ magic missiles, where the $$$i$$$-th missile is fixed to attack the $$$i$$$-th goblin.

It is known that the $$$i$$$-th missile has penetration power $$$A_i$$$ and potential damage $$$C_i$$$, while the $$$i$$$-th goblin has defense $$$B_i$$$. The missile deals $$$C_i$$$ damage if and only if its penetration power is at least the goblin's defense, that is, $$$A_i \ge B_i$$$; otherwise, it deals $$$0$$$ damage.

Taffy has one chance to use a secret spell: before damage is resolved, she may choose at most one missile and forcibly change its penetration power to $$$X$$$ (or she may choose not to modify any missile).

Now there are $$$Q$$$ independent queries. Each query gives a value $$$X$$$. For the current given $$$X$$$, please determine the maximum total damage Taffy can deal to the goblins under the optimal modification strategy.

Please note the special time limit and memory limit for this problem.

Little t has recently become very interested in fascinating number sequences and binary representations.

He defines a generalized recurrence sequence $$$f(i)$$$ with parameter $$$a$$$, formally given by: $$$$$$ f(i) = \begin{cases} 0 & \text{if } i = 0, \\ 1 & \text{if } i = 1, \\ a \cdot f(i-1) + f(i-2) & \text{if } i \ge 2. \end{cases} $$$$$$

At the same time, Little t defines the function $$$g(x)$$$ as the number of 1s in the binary representation of a positive integer $$$x$$$ (that is, the popcount). For example, $$$g(5) = g(101_{(2)}) = 2$$$.

Now, Little t has an extremely large positive integer $$$n$$$. Since it is too large, he can only write it as a binary string $$$s$$$ without leading zeros. He is also given the parameter $$$a$$$ of the recurrence sequence.

He really wants to know the value of the following summation: $$$$$$ \sum_{i=1}^{n} f(g(i)) \pmod{10^9+7} $$$$$$

However, since the number $$$n$$$ is far too large, Little t's computer was unable to compute the answer. Can you write a program to help him?

On Sunday afternoon, the HZAU ACM training room is filled with the sound of keyboards. To reward the students who are working hard on programming problems, Fan Ge decides to order some milk tea from Mixue Bingcheng.

There are $$$n$$$ students in the training room, and Fan Ge needs to buy exactly $$$n$$$ cups of milk tea.

After opening the food delivery app, Fan Ge finds that the shop offers two ways to buy:

• Single order: buying 1 cup of milk tea costs $$$a$$$ yuan.
• Couple set: buying 2 cups of milk tea costs only $$$b$$$ yuan.

Now, please help Fan Ge calculate the minimum amount of money needed to buy exactly $$$n$$$ cups of milk tea.

You are given a rooted tree with root $$$1$$$ and $$$N$$$ nodes. Each node $$$i$$$ has an initial weight $$$M_i$$$. At all times, the system strictly maintains the following property: for any non-root node $$$x$$$, its weight never exceeds that of its parent, that is, $$$M_{\text{parent}(x)} \ge M_x$$$.

You need to process $$$Q$$$ operations online. The operations are of the following two types:

• 1 u w: Query. Starting from node $$$u$$$, move upward along the tree edges toward the root, and find the first node whose weight is at least $$$w$$$ (including $$$u$$$ itself). Output the index of that node. If no such node exists all the way up to the root, output -1.
• 2 x v: Update. Attempt to add $$$v$$$ to the weight of node $$$x$$$ ($$$v$$$ may be negative), that is, let $$$M_x \leftarrow M_x + v$$$. To avoid violating the tree property, a legality check must be performed before the update:
  • If $$$x \neq 1$$$ and $$$M_x + v \gt M_{\text{parent}(x)}$$$, then the update fails.
  • If $$$x$$$ is not a leaf node and $$$M_x + v \lt \max_{y \in \text{children}(x)} M_y$$$, then the update fails.
  If both checks pass, then the update is actually performed and SUCCESS is output; otherwise, the update is rejected, the state of the tree remains unchanged, and FAILED is output.

You are given an undirected tree with $$$n$$$ nodes, numbered from $$$1$$$ to $$$n$$$. Each node $$$i$$$ on the tree has a weight $$$p_i$$$. It is guaranteed that the weights $$$p_1, p_2, \dots, p_n$$$ form a permutation.

For a connected component on the tree (that is, a connected subgraph consisting of some nodes of the tree and the edges between them), we define its MEX value as the smallest non-negative integer that does not appear in the set of node weights within this connected component.

Now there are $$$q$$$ queries. Each query gives two integers $$$A$$$ and $$$B$$$. For each query, you need to determine how many connected components in the tree satisfy both of the following conditions:

1. The connected component contains node $$$A$$$.
2. The MEX value of the connected component is exactly $$$B$$$.

Since the number of connected components satisfying the conditions may be very large, output the answer to each query modulo $$$10^9 + 7$$$.

• Permutation: If a sequence of length $$$n$$$ contains every integer from $$$0$$$ to $$$n-1$$$ exactly once, then it is called a permutation of $$$0$$$ to $$$n-1$$$. For example, $$$[2, 0, 3, 1]$$$ is a permutation, while $$$[0, 1, 1, 3]$$$ is not.

You are assigned to manage a severely congested grid parking lot. The parking lot can be viewed as an $$$N \times M$$$ matrix. Each cell in the matrix is either empty (denoted by .), or occupied by a car with a fixed driving direction, which can be one of the four types: U (up), D (down), L (left), or R (right).

You may send a "leave" signal to these cars in any order. After receiving the signal, a car will successfully leave the parking lot if and only if, starting from its current position and moving straight toward the boundary in the direction it is facing, there is no other car blocking its path. Once a car leaves, its current cell becomes empty (.).

Determine whether there exists an order of sending signals such that all cars in the parking lot can be evacuated. If it is possible, output the sequence of coordinates of the cars to which signals are sent in order; otherwise, if the cars block each other in a deadlock and cannot all be evacuated, output $$$-1$$$.

Little t gives you a sequence of $$$n$$$ positive integers $$$a_1, a_2, \dots, a_n$$$, as well as a constant $$$P$$$. You need to partition this sequence into $$$m$$$ ($$$1 \le m \le n$$$) consecutive and non-empty subsegments. Each element must belong to exactly one subsegment. Suppose one of the subsegments you obtain is $$$[L, R]$$$ ($$$1 \le L \le R \le n$$$). For any given subsegment $$$[L, R]$$$, we define $$$W(L, R)$$$ as the sum of all positive odd numbers corresponding to the indices in this interval. Formally, $$$$$$W(L, R) = \sum_{i=L}^R (2i - 1)$$$$$$ At the same time, define $$$G(L, R)$$$ as the greatest common divisor of all elements in this interval. Formally, $$$$$$G(L, R) = \gcd(a_L, a_{L+1}, \dots, a_R)$$$$$$ Each time you create a subsegment, a cost of $$$P$$$ is incurred. Therefore, for the interval $$$[L, R]$$$, its weight is calculated as follows: $$$$$$\mathcal{E}(L, R) = W(L, R) \times G(L, R) - P$$$$$$ Little t wants you to find a partition scheme such that the total weight of these $$$m$$$ subsegments is as large as possible.