Luffy and Zoro are exploring a ruined island containing a row of $$$n$$$ ancient stone towers. The height of the tower at position $$$i$$$ is $$$a_i$$$.

For each query $$$[l,r]$$$, consider only the towers whose positions are between $$$l$$$ and $$$r$$$, inclusive. Towers outside this segment do not affect the query.

The destruction happens in rounds. In each round, a remaining tower at position $$$i$$$ crumbles if there exist two other remaining towers at positions $$$j$$$ and $$$k$$$ such that $$$l \le j \lt i \lt k \le r$$$ and $$$a_j \gt a_i$$$ and $$$a_k \gt a_i$$$.

In other words, a tower crumbles if there is at least one strictly taller remaining tower somewhere to its left and at least one strictly taller remaining tower somewhere to its right.

The towers at positions $$$j$$$ and $$$k$$$ do not need to be adjacent to the tower at position $$$i$$$. Any remaining towers on its left and right may satisfy the condition.

All towers satisfying the condition are removed simultaneously. The process is repeated until an entire round passes without any tower crumbling.

For each query, determine how many towers in the segment $$$[l,r]$$$ remain after the process ends.

The night sky was clear, and the moon reflected beautifully off the quiet ocean. Nami and Samer Samora sat close together on the deck of the Sunny. Samer Samora looked into Nami's eyes, gently took her hand, and promised to share all his adventures, treasures, and even his debts with her.

They mapped out their future using a cyclic array $$$a_{1}, a_{2}, \dots, a_{n}$$$ that sums to 0. A rotation represents a possible starting point for their new life, reading all $$$n$$$ items in a circle.

Because Nami loves money and Samer Samora deeply loves Nami, he wants to ensure she never feels insecure. A rotation is considered "safe" if their shared wealth (the prefix sums) never drops below zero. Help Samer Samora count the number of safe starting points so he can give Nami the perfect, secure, happy ending they deserve.

Chopper and Usopp find a giant plant shaped like a tree with $$$n$$$ vertices and $$$n-1$$$ branches. Vertex $$$v$$$ has a value $$$a_{v}$$$.

For each branch $$$i$$$, two values are written:

• $$$p_{i}$$$, its contribution if the branch is kept;
• $$$q_{i}$$$, its contribution if the branch is cut.

Consider any subset $$$K$$$ of branches. Branches in $$$K$$$ are kept, and all other branches are cut. The kept branches split the vertices into several connected components.

For a component $$$C$$$, define its value as: $$$$$$W(C) = \sum_{v \in C} a_{v}$$$$$$

The score of choice $$$K$$$ is: $$$$$$score(K) = \left(\prod_{i \in K} p_{i}\right) \left(\prod_{i \notin K} q_{i}\right) \left(\prod_{C} W(C)\right)$$$$$$ where the last product is over all connected components after cutting the branches not in $$$K$$$.

Define: $$$$$$F = \sum score(K)$$$$$$ In other words, $$$F$$$ is the sum of $$$score(K)$$$ over all $$$2^{n-1}$$$ possible choices of which branches are kept and which are cut.

All calculations are performed modulo 998244353.

You must process $$$Q$$$ updates. After each update, output the current value of $$$F$$$.

There are two types of updates:

• $$$1\ v\ x$$$: set $$$a_{v}=x$$$.
• $$$2\ i\ p\ q$$$: set $$$p_{i}=p$$$ and $$$q_{i}=q$$$.

Captain Kareem Elgoker is establishing a new pirate haven in the treacherous Algorithmic Seas. He has obtained an ancient map detailing the locations of $$$n$$$ uncharted islands. Due to the mystical properties of the ocean, each island emits a unique magnetic signature, denoted by an integer $$$a_i$$$.

The Captain must select exactly $$$k$$$ of these islands to form his secret archipelago territory. To ensure his crew can travel safely without being detected by the Royal Navy, he must connect all $$$k$$$ chosen islands into a single continuous network using hidden smuggling routes.

A smuggling route can be established between any two selected islands $$$u$$$ and $$$v$$$. The "Secrecy Level" (cost) of the route between island $$$u$$$ and island $$$v$$$ is exactly the Least Significant Bit (LSB) of the absolute difference of their magnetic signatures.

Formally, the weight of the edge between $$$u$$$ and $$$v$$$ is $$$LSB(\vert{}a_u - a_v\vert{})$$$.

(Note: $$$LSB(x)$$$ is the largest power of $$$2$$$ that divides $$$x$$$. For example, $$$LSB(12) = 4$$$, and $$$LSB(7) = 1$$$.)

To build a secure base, the network of islands will be connected by its Minimum Spanning Tree (MST) based on these Secrecy Levels. However, to maximize the overall obscurity of his territory, Captain Kareem wants to select the subset of $$$k$$$ islands such that the total weight of this MST is maximized.

Given the array $$$a$$$ representing the magnetic signatures of the islands, find the maximum possible weight of the MST if the Captain optimally chooses exactly $$$k$$$ islands.

Sherbiny has set sail on a grand pirate conquest! He attacks a new island every day for $$$n$$$ days. Brook stands at the bow of the ship, playing a victorious tune on his violin.

On day $$$i$$$, Sherbiny loots $$$a_{i}$$$ pieces of gold. Brook wants to write a song about the crew's massive fortune.

Find the total amount of gold Sherbiny has collected after all $$$n$$$ days so Brook can finish his masterpiece.

Sanji is cooking a brand-new recipe in the galley, but he needs the perfect ratio of ingredients. Sherbiny gives him an array $$$a_1, a_2, \ldots, a_n$$$.

Consider all $$$2^n$$$ subsequences of the array, including the empty subsequence.

A subsequence is obtained by choosing some indices of the array and keeping the chosen elements in their original relative order. Different choices of indices are considered different subsequences, even if they produce the same sequence of values.

For a subsequence $$$b_1, b_2, \ldots, b_m$$$, define its flavor score as $$$\sum_{i=2}^{m} \gcd(b_i, b_{i-1}).$$$

We define $$$\gcd(0,0)=0$$$. The empty subsequence and every subsequence of length $$$1$$$ have a flavor score of $$$0$$$.

Sherbiny writes the flavor scores of all $$$2^n$$$ subsequences in non-increasing order. Equal scores are kept as separate entries in this order.

Sanji wants to find the $$$k$$$-th score in this order.

Luffy wants to form a team for an upcoming raid. There are $$$n$$$ pirates available, and the fighting power of the $$$i$$$-th pirate is $$$a_i$$$.

Luffy must choose a nonempty team and select exactly one pirate from that team as its captain.

After excluding the captain, the fighting powers of the remaining team members must be close to each other. More precisely, if the remaining pirates have minimum fighting power $$$x$$$ and maximum fighting power $$$y$$$, then the following condition must hold: $$$y-x \le d.$$$

A team containing only one pirate is always valid, since that pirate can be chosen as the captain.

Find the maximum possible number of pirates in a valid team.

Franky is building a massive movie projector to watch movies on the side of the Sunny. He receives $$$n$$$ video frames sorted by time. Frame $$$i$$$ arrives at time $$$T_{i}$$$ and needs $$$C_{i}$$$ cola-power to run.

He must cut the frames into continuous groups. For a group having frames $$$L, L+1, \dots, R$$$:

• its delay is $$$T_{R} - T_{L}$$$;
• its load is $$$\max(C_{L}, C_{L+1}, \dots, C_{R})$$$.

The total load is the sum of the loads of all groups. Sherbiny calculates the ship's engine limit and warns Franky that the total load must be $$$M$$$ or less. Find the smallest possible max delay among all groups so the movie doesn't lag.

Sherbiny and Elgoker just raided a marine base and stole a lockbox. To open it, they have to decipher treasure codes from an array $$$a$$$ of $$$n$$$ positive numbers.

Elgoker figures out the puzzle: a pair of places $$$(i, j)$$$ is a match if $$$1 \le i \lt j \le n$$$ and $$$a_{i} \oplus a_{j} \le \min(a_{i}, a_{j})$$$, where $$$\oplus$$$ is the bitwise XOR operation.

Help Sherbiny find the number of matches so they can pop the lock and get the loot!

Brook is trying to write a beautiful, soulful new song using a long string of lyrics $$$s$$$.

Robin reads over his sheet music and suggests cutting the lyric string into three specific non-empty parts A, B, and C such that $$$A + B + C = s$$$ to create an echoing effect so that:

• A is a prefix of C;
• B is a suffix of C.

A and B can overlap inside C. Different cuts are counted as completely different musical arrangements. Help Robin find the number of ways to cut the string so Brook can sing his song.

Zoro has somehow gotten completely lost again, this time on a flat island with $$$n$$$ landmarks. Sanji is furious and tries to guide him using a map. The $$$i$$$-th landmark is at $$$(x_{i}, y_{i})$$$.

To make things easier for Zoro's terrible sense of direction, Sanji decides to erase up to two landmarks from the map. The "lost diameter" of the map is the biggest Manhattan distance between any two remaining landmarks.

The Manhattan distance between $$$(x_{1}, y_{1})$$$ and $$$(x_{2}, y_{2})$$$ is $$$|x_{1}-x_{2}| + |y_{1}-y_{2}|$$$. If less than two landmarks are left, the diameter is 0.

Find the smallest possible lost diameter Sanji can achieve after removing at most two landmarks.

Elgoker locked the ship's treasure inside a secure safe. He encoded the master key as the constant term, $$$P(0)$$$, of a secret polynomial $$$P(x)$$$ of degree at most $$$k-1$$$. All calculations are heavily secured and evaluated modulo $$$10^{9}+7$$$.

To ensure the safe could be opened later, Elgoker distributed $$$k+2$$$ access codes to Chopper. Each access code is a coordinate pair $$$(x_{i}, y_{i})$$$, where $$$y_{i} = P(x_{i}) \pmod{10^{9}+7}$$$.

However, a mischievous monkey managed to infiltrate the ship and tampered with exactly one of the $$$k+2$$$ access codes, altering its $$$y_{i}$$$ value to a fake integer to lock everyone out. The remaining $$$k+1$$$ codes are completely untouched and lie perfectly on the original polynomial curve.

Given the $$$k+2$$$ access codes, your task is to help Chopper identify the corrupted code, discard it, and recover the master key $$$P(0) \pmod{10^{9}+7}$$$ so they can access the treasure!

Sherbiny and Samer Samora are optimizing the core database engine for the Sunny's navigation logs. They need to implement a buffer pool of capacity $$$C$$$ to keep frequently accessed data pages in fast memory.

The pool can hold up to $$$C$$$ distinct pages, each identified by a positive integer. When a page is read or written, it is brought into the pool and becomes the most recently accessed page. If the pool is already at full capacity $$$C$$$ and a new page must be brought in, the Least Recently Used (LRU) page is evicted to make room.

A write operation modifies a page, marking it as dirty. If a dirty page is evicted from the pool, it is completely removed and is no longer considered dirty.

You must process $$$Q$$$ queries of the following four types:

• 1 $$$x$$$ — Read: Access page $$$x$$$. Bring it into the pool (evicting the LRU page if necessary). Page $$$x$$$ becomes the most recently accessed. If $$$x$$$ was already in the pool, its dirty status remains unchanged.
• 2 $$$x$$$ — Write: Access page $$$x$$$ using the exact same LRU rules as a read, but additionally mark page $$$x$$$ as dirty.
• 3 — Flush: Print the total number of dirty pages currently in the pool, then mark all of them as clean (not dirty).
• 4 $$$x$$$ — Status: Print whether page $$$x$$$ is currently in the pool, and whether it is dirty. This query does not count as an access and does not change the LRU order.

Usopp and Robin are analyzing a massive island shaped like a rooted tree with $$$n$$$ vertices. The root is vertex 1. Each branch (edge) connecting the vertices has an integer value representing the wind speed, and each vertex $$$v$$$ has a wind tolerance $$$k_{v}$$$.

Usopp can shoot a signal flare from a vertex $$$u$$$ to a descendant $$$v$$$ if the difference between the maximum and minimum wind speeds (edge values) on the path from $$$u$$$ to $$$v$$$ is at most the receiver's tolerance $$$k_{v}$$$:

max(w on the path from u to v) - min(w on the path from u to v) $$$\le k_{v}$$$.

Robin notes that the tolerance used here belongs to the receiver $$$v$$$, not to the sender $$$u$$$.

If $$$u=v$$$, the path contains zero edges. In this case, the difference is defined as 0, so every vertex can successfully receive a signal from itself.

For every vertex $$$u$$$, find how many descendants ($$$u$$$ included) can receive a signal from $$$u$$$.

Note: a descendant of $$$u$$$ is any node $$$v$$$ in the subtree of $$$u$$$, including node $$$u$$$

This is an interactive problem. Refer to the Interaction Protocol section below for better understanding.

Sherbiny has hidden a secret permutation $$$p$$$ of length $$$n$$$ (an array containing every integer from 1 to $$$n$$$ exactly once). Luffy's task is to reconstruct this permutation using at most $$$n-1$$$ queries.

Luffy cannot see the elements of $$$p$$$, but he can ask Sherbiny to evaluate specific subsets of indices. When Luffy queries a subset, Sherbiny isolates the elements at those indices—keeping them in their original relative order—and tells Luffy exactly how many inversions exist just among those isolated elements.

Formal Query Definition: Specifically, if Luffy queries a subset of $$$k$$$ indices $$$1 \le i_{1} \lt i_{2} \lt \dots \lt i_{k} \le n$$$, Sherbiny constructs a new sequence $$$a = [p_{i_{1}}, p_{i_{2}}, \dots, p_{i_{k}}]$$$. Sherbiny then returns the total number of inversions in $$$a$$$.

The number of inversions in an array is the number of pairs of indices $$$u, v$$$ such that $$$u \lt v$$$ and $$$a_{u} \gt a_{v}$$$.

For each test case, after reading $$$n$$$, you may ask at most $$$n-1$$$ questions before you must output your guess.

To ask a question, output a line in the following format:

• ? $$$k$$$ $$$i_1$$$ $$$i_2$$$ $$$\ldots$$$ $$$i_k$$$

After each question, read one integer from the judge — the number of inversions among the values at the chosen positions.

After printing each line, flush the output. For example:

• cout « endl or fflush(stdout) in C++;
• System.out.flush() in Java;
• sys.stdout.flush() in Python.

When you have determined the hidden permutation, output a single line:

• ! $$$p_1$$$ $$$p_2$$$ $$$\ldots$$$ $$$p_n$$$