Pigeland University will host the 2224 Animal Collegiate Programming Contest (ACPC 2224). Unlike previous years, where teams from the host institution were marked as unofficial, Pigeland will send official teams to compete in the contest with three workstations for each team. Nevertheless, Pig-head, the coach of Pigeland University, remains uncertain about his teams' chances of securing gold medals. As a result, he decides to acquire the contest problems in advance from the AUS problem-setting group, using the excuse of needing to upload data to the online judge.

To prevent cheating, AUS attempts to encrypt the problems using a special cipher. Specifically, problems are represented by strings consisting of lowercase English letters. AUS wants to design a cipher function $$$f(x)$$$ that maps lowercase English letters to lowercase English letters. For a problem $$$S = s_1s_2\ldots s_{n}$$$, the encrypted version of the problem is another string given by $$$F(S) = f(s_1)f(s_2)\ldots f(s_{n})$$$. For example, when $$$S = \texttt{abcabc}$$$ and $$$f(\texttt{a}) = \texttt{a}$$$, $$$f(\texttt{b}) = \texttt{k}$$$, $$$f(\texttt{c}) = \texttt{a}$$$, the encrypted version is $$$F(S) = \texttt{akaaka}$$$.

As a member of AUS, your task is to design the cipher function $$$f$$$. The leader of AUS believes that the function is strong if and only if there exists at least one problem that can be encrypted into the same encrypted version as another, while not all problems produce the same encrypted output. To validate this, he will give you three problems $$$S_1$$$, $$$S_2$$$, and $$$S_3$$$, and you need to find a cipher function $$$f$$$ such that $$$F(S_1) = F(S_2)$$$ and $$$F(S_1) \neq F(S_3)$$$. Since AUS has several experienced members, your task is simply to determine whether such a cipher function exists.

There are $$$n$$$ little pigs in Pigeland. All of them are proficient in competitive programming, and the $$$i$$$-th of them has $$$a_i$$$ rating. If $$$k$$$ pigs $$$p_1, p_2, \cdots, p_k$$$ form a team, the rating of the team will be $$$a_{p_1}\ \&\ a_{p_2}\ \&\ a_{p_3}\ \& \cdots \&\ a_{p_k}$$$, where $$$\&$$$ denotes the bitwise AND operation.

There are some programming contests to take place. Pigeland can send exactly one team to participate in each contest. For the $$$i$$$-th competition, only the pigs numbered between $$$l_i$$$ and $$$r_i$$$ (both inclusive) have time to participate. Unfortunately, due to a shortage of funds, exactly one pig numbered between $$$l_i$$$ and $$$r_i$$$ has to be removed. Meanwhile, all other pigs in the interval will participate in the contest. Pig-head, the coach of Pigeland, needs to properly select pigs who will not participate so that the team's rating is maximized.

However, through training and participating in contests, the rating of pigs may be changed. As Pig-head's best friend, your task is to maintain the pigs' rating for the following $$$q$$$ events belonging to three types.

• $$$1 \; l \; r \; x$$$: Pig-head changes the rating of each pig numbered between $$$l$$$ and $$$r$$$ (both inclusive) by executing the bitwise AND operation with $$$x$$$. More formally, for all $$$l \le i \le r$$$, $$$a_i$$$ becomes $$$a_i\ \&\ x$$$.
• $$$2 \; s \; x$$$: Pig-head changes the rating of the $$$s$$$-th pig to $$$x$$$.
• $$$3 \; l \; r$$$: Pig-head asks for the maximum rating when forming a team by selecting pigs numbered between $$$l$$$ and $$$r$$$ (both inclusive) and removing exactly one of them.

BaoBao bought a telescope to observe a star in the night sky. The star is represented as a convex polygon $$$S$$$. However, there are $$$n$$$ convex polygonal moons $$$M_i$$$ that could obstruct his view. BaoBao can place his telescope anywhere on the $$$x$$$-axis between points $$$(l,0)$$$ and $$$(r,0)$$$, but he cannot place it exactly at $$$(l,0)$$$ or $$$(r,0)$$$.

Your task is to help BaoBao find the total length of the segments on the x-axis where he can position his telescope such that he has an unobstructed view of the star $$$S$$$, and whether he can find a position at all. An unobstructed view means that no line segment from the chosen point on the x-axis to any point inside or on $$$S$$$ properly intersects any of the moons $$$M_i$$$. The line segment is allowed to touch the boundary of the moons but not cross through them.

Alice got a sequence $$$A$$$ constructed by her neighbors. Since Alice doesn't like long sequences, she decides to divide the sequence into two (possibly empty) sequences $$$B$$$ and $$$C$$$ and give them back to her neighbors. Her division should meet the following constraints:

• $$$B$$$ and $$$C$$$ are both subsequences of sequence $$$A$$$.
• Each element of $$$A$$$ belongs to exactly one of the sequences $$$B$$$ or $$$C$$$.
• $$$B\leq C$$$ in lexicographical order.

Here we define a sequence $$$P = p_1, p_2, \cdots, p_u$$$ of length $$$u$$$ to be lexicographically smaller than a sequence $$$Q = q_1, q_2, \cdots, q_v$$$ of length $$$v$$$ if one of the following constraints is true:

• $$$u \lt v$$$ and $$$P$$$ is a prefix of $$$Q$$$.
• There exists an integer $$$1 \le k \le \min(u, v)$$$ such that $$$p_i = q_i$$$ for all $$$1 \le i \lt k$$$ and $$$p_k \lt q_k$$$.

As a fair girl, Alice hopes to divide fairly such that the lexicographical order of $$$C$$$ is as small as possible. Please tell Alice the minimum possible $$$C$$$.

There is a building with $$$10^9$$$ floors but only $$$1$$$ elevator. Initially, the elevator is on the $$$f$$$-th floor.

There are $$$n$$$ people waiting for the elevator. The $$$i$$$-th person is currently on the $$$l_i$$$-th floor and wants to take the elevator to the $$$r_i$$$-th floor ($$$l_i \lt r_i$$$). Because the elevator is so small, it can carry at most $$$1$$$ person at a time.

It costs $$$1$$$ unit of electric energy to move the elevator $$$1$$$ floor upwards. No energy is needed if the elevator moves downwards. That is to say, it costs $$$\max(y - x, 0)$$$ units of electric energy to move the elevator from the $$$x$$$-th floor to the $$$y$$$-th floor.

Find the optimal order to take all people to their destinations so that the total electric energy cost is minimized.

More formally, let $$$a_1, a_2, \cdots, a_n$$$ be a permutation of $$$n$$$ where $$$a_i$$$ indicates that the $$$i$$$-th person to take the elevator is $$$a_i$$$. The total electric energy cost can be calculated as

$$$$$$\sum\limits_{i = 1}^n (\max(l_{a_i} - r_{a_{(i - 1)}}, 0) + r_{a_i} - l_{a_i})$$$$$$

where $$$a_0 = 0, r_0 = f$$$ for convenience.

Recall that a sequence $$$a_1, a_2, \cdots, a_n$$$ of length $$$n$$$ is a permutation of $$$n$$$ if and only if each integer from $$$1$$$ to $$$n$$$ (both inclusive) appears exactly once in the sequence.

In Pigeland, there are $$$n$$$ universities, numbered from $$$1$$$ to $$$n$$$. Each year, several ranking organizations publish rankings of these universities. This year, there are $$$k$$$ ranking lists, where each list is a permutation of integers from $$$1$$$ to $$$n$$$, representing the universities. In each ranking, the closer a university is to the beginning of the permutation, the better its ranking is in this list.

A true story in the 2024 ICPC World Final.

Supigar, a year-4 student who wants to apply for PhD programs in Pigeland, has his own method to evaluate the $$$n$$$ universities comprehensively. He considers that university $$$x$$$ is superior to another university $$$y$$$ if and only if:

• $$$x$$$ is ranked better than $$$y$$$ in at least one list, or
• $$$x$$$ is ranked better than $$$z\ (z \neq x, z \neq y)$$$ in at least one list, and $$$z$$$ is superior to $$$y$$$.

Supigar has $$$q$$$ queries, where the $$$i$$$-th query can be represented by three integers $$$id_i$$$, $$$l_i$$$ and $$$r_i$$$ ($$$l_i \le r_i$$$). For each query, he will consider the $$$id_i$$$-th rank list and all the universities between the $$$l_i$$$-th position and the $$$r_i$$$-th position (both inclusive) in that list. He wants to know, among these universities, how many pairs of them are fuzzy. Note that the definition of fuzzy pairs requires considering the superior relationships among all $$$k$$$ rank lists.

BaoBao is picking mushrooms in a forest. There are $$$n$$$ locations in the forest, and in the $$$i$$$-th location there grows an infinite amount of mushrooms of type $$$t_i$$$. Each location also has a wooden sign. The sign of the $$$i$$$-th location points to location $$$a_i$$$ (it is possible that $$$a_i = i$$$).

As it is very foggy in the forest, BaoBao decides to move between locations according to the signs just for safety. Starting from location $$$s$$$ with an empty basket, each time BaoBao walks into a location $$$c$$$ (including the starting location $$$c = s$$$, and regardless of whether he has visited location $$$c$$$ before), he will pick one mushroom of type $$$t_c$$$ into his basket and move to location $$$a_c$$$.

Given an integer $$$k$$$, for each $$$1 \le s \le n$$$, determine the first type of mushroom that appears at least $$$k$$$ times in the basket.

Heavy-light Decomposition (HLD) is a useful technique applied to trees for efficiently querying chains of vertices. Let's first review the definition of HLD in case you forget.

You are given a rooted tree with $$$n$$$ vertices, numbered from $$$1$$$ to $$$n$$$. You need to classify each non-root vertex as either heavy or light. Each non-leaf vertex has exactly one child classified as heavy, and the remaining vertices as light.

For any non-root vertex $$$v$$$, let $$$u$$$ be its parent. Vertex $$$v$$$ can be classified as heavy only if the size of its subtree is among the largest of all the children of $$$u$$$. More formally, denote the size of the subtree rooted at vertex $$$v$$$ as $$$s_v$$$, and let $$$\text{ch}(u)$$$ represent the set of children of $$$u$$$. Then, $$$v$$$ can be heavy only if $$$s_v \geq s_w$$$ for all $$$w \in \text{ch}(u)$$$. Note that there might be several children of $$$u$$$ satisfying this constraint; in this case, you should choose one of them to be heavy, and the others to be light.

After that, all vertices of the tree can be decomposed into several non-overlapping heavy chains, where each vertex belongs to exactly one heavy chain. A heavy chain is a sequence of vertices $$$x_1, x_2, \ldots, x_k$$$ satisfying all the following constraints.

• $$$x_1$$$ is either the root or a light vertex.
• For all $$$2 \leq i \leq k$$$, $$$x_i$$$ is $$$x_{i-1}$$$'s child and is a heavy vertex.
• $$$x_k$$$ is a leaf.

An HLD example. Heavy chains are marked with solid red edges.

For example, the above figure shows a valid HLD of the given tree with $$$12$$$ vertices, where the heavy chains are $$$[1, 2, 3, 4, 5]$$$, $$$[9, 10, 11]$$$, $$$[7, 8]$$$, $$$[6]$$$, and $$$[12]$$$.

Pig100Ton is a very experienced competitive programming contestant in Pigeland. He wants to know whether it is possible to recover the original tree from the heavy chains after HLD. Specifically, he will give you the number of vertices $$$n$$$ of the original tree and $$$k$$$ heavy chains. The $$$i$$$-th chain is described by two integers $$$l_i$$$ and $$$r_i$$$, indicating a heavy chain $$$l_i, l_i + 1, \ldots, r_i$$$.

Your task is to construct a tree satisfying the following constraints or to tell Pig100Ton it is impossible:

• It is a rooted tree that contains $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$.
• The $$$k$$$ chains provided by Pig100Ton should form a valid HLD of the tree. A valid HLD refers to a valid way to classify each non-root vertex as either light or heavy, and then decompose the tree into several non-overlapping heavy chains.

This is an interactive problem.

Grammy has an undirected cyclic graph of $$$n$$$ ($$$4 \le n \le 10^9$$$) vertices numbered from $$$1$$$ to $$$n$$$. An undirected cyclic graph is a graph of $$$n$$$ vertices and $$$n$$$ undirected edges that form one cycle. Specifically, there is a bidirectional edge between vertex $$$i$$$ and vertex $$$((i\bmod n)+1)$$$ for each $$$1 \le i \le n$$$.

Grammy thinks that this graph is too boring, so she secretly chooses a pair of non-adjacent vertices and connects an undirected edge (called a chord) between them, so that the graph now contains $$$n$$$ vertices and $$$(n+1)$$$ edges.

Your task is to guess the position of the chord by making no more than $$$40$$$ queries. Each query consists of two vertices $$$x$$$ and $$$y$$$, and Grammy will tell you the number of edges on the shortest path between the two vertices.

Note that the interactor is non-adaptive, meaning that the position of the chord is pre-determined.

To ask a query, output one line. First output ? followed by a space, then output two vertices $$$x$$$ and $$$y$$$ ($$$1 \le x, y \le n$$$) separated by a space. After flushing your output, your program should read a single integer indicating the number of edges on the shortest path between the two vertices.

To guess the position of the chord, output one line. First output ! followed by a space, then output two vertices $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$) separated by a space, indicating that the chord connects vertices $$$u$$$ and $$$v$$$. After flushing your output, your program should read a single integer $$$r$$$ ($$$r \in \{1, -1\}$$$) indicating the correctness of your guess. If $$$r = 1$$$ then your guess is correct, and your program should continue processing the next test case, or exit immediately if there are no more test cases. Otherwise if $$$r = -1$$$ then your guess is incorrect, and your program should exit immediately to receive a Wrong Answer verdict. Note that your guess does not count as a query.

To flush your output, you may use:

• fflush(stdout) (if you use printf) or cout.flush() (if you use cout) in C and C++.
• System.out.flush() in Java.
• stdout.flush() in Python.

Grammy is designing a new trading card game (TCG) based on her favorite Japanese music media franchise, BanG Dream!. By her design, there are $$$n_1$$$ character cards and $$$n_2$$$ music cards in total. Now she needs to assign an integer between $$$1$$$ and $$$m$$$ (both inclusive) for each card, representing the magic power it contains.

In every TCG game, there must be some certain combos that may cause extra damage. Grammy now is considering a special rule that relates to the value assigned to cards. Specifically, $$$k$$$ pairs of integers $$$(a_1, b_1), (a_2, b_2), \cdots, (a_k, b_k)$$$ are chosen, satisfying $$$1 \le a_i, b_i \le m$$$. Grammy wants to make sure each of these value combos can be played in her game. Therefore, for each pair of integers $$$(a_i, b_i)$$$, the assignment must meet at least one of the two following constraints:

• $$$a_i$$$ can be found on a character card and $$$b_i$$$ can be found on a music card.
• $$$a_i$$$ can be found on a music card and $$$b_i$$$ can be found on a character card.

Please help Grammy count the number of valid card-value assignments.

Let $$$\mathbb{C}$$$ be the multi-set of the integers on the character card and $$$\mathbb{M}$$$ be the multi-set of the integers on the music card. We say two assignments are different if their $$$\mathbb{C}$$$s are different or their $$$\mathbb{M}$$$s are different.

Recall that an integer can appear multiple times in a multi-set. We say two multi-sets $$$\mathbb{X}$$$ and $$$\mathbb{Y}$$$ are different if there exists an integer $$$k$$$ such that the number of times $$$k$$$ appears in $$$\mathbb{X}$$$ is not equal to that in $$$\mathbb{Y}$$$.

There is a grid with $$$n$$$ rows and $$$m$$$ columns. The cells in the grid are numbered from $$$1$$$ to $$$n \times m$$$, where the cell on the $$$i$$$-th row and the $$$j$$$-th column is numbered as $$$((i - 1) \times m + j)$$$.

Given a permutation $$$p_1, p_2, \cdots, p_{n \times m}$$$ of $$$n \times m$$$, we're going to perform $$$n \times m$$$ operations according to the permutation. For the $$$i$$$-th operation, we'll mark cell $$$p_i$$$. If after the $$$b$$$-th operation, there is at least one row such that all the cells in that row are marked, and $$$b$$$ is as small as possible, then we say $$$b$$$ is the "bingo integer" of the permutation.

You're given the chance to modify the permutation at most $$$k$$$ times (including zero times). Each time you can swap a pair of elements in the permutation. Calculate the smallest possible bingo integer after the modifications.

Recall that a sequence $$$p_1, p_2, \cdots, p_{n \times m}$$$ of length $$$n \times m$$$ is a permutation of $$$n \times m$$$ if and only if each integer from $$$1$$$ to $$$n \times m$$$ (both inclusive) appears exactly once in the sequence.

In Pigeland, Pishin is a popular open-world action RPG where users can play multiple characters. Each character has an independent adventure rank, which increases as they earn experience points (EXP) while being played. Initially, every character starts with an adventure rank of level $$$0$$$ and can progress up to a maximum level of $$$m$$$. To advance from level $$$(i-1)$$$ to level $$$i$$$ ($$$1 \leq i \leq m$$$), the character is required to earn $$$b_i$$$ EXP. The higher the current rank, the more difficult it becomes to level up, meaning $$$b_i \leq b_{i+1}$$$ always holds for all $$$i$$$ from $$$1$$$ to $$$m$$$.

Grammy plans to play Pishin for the next $$$n$$$ days. As a rich girl, her Pishin account has an infinite number of characters. However, being a lazy girl, all characters in her account start with an adventure rank of level $$$0$$$ at the beginning of the $$$n$$$ days. Each day, Grammy will select exactly one character to play, but once she stops playing a character, she cannot resume playing that character on any future day. In other words, she can only continue playing the same character on consecutive days.

On the $$$i$$$-th day, Grammy will earn $$$a_i$$$ EXP for the character she plays. This means that if she plays a character continuously from the $$$l$$$-th day to the $$$r$$$-th day (both inclusive), the character's adventure rank will increase to level $$$k$$$, where $$$k$$$ is the largest integer between $$$0$$$ and $$$m$$$ such that the total EXP earned (which is $$$\sum\limits_{i=l}^r a_i$$$) is greater than or equal to the requirement of leveling up to $$$k$$$ (which is $$$\sum\limits_{i=1}^{k} b_i$$$).

Being a greedy girl, Grammy wants to maximize the total sum of adventure ranks across all her characters after the $$$n$$$ days. However, as a single-minded girl, she doesn't want to play too many different characters. To balance this, she introduces a penalty factor of $$$c$$$. Her goal is to maximize the total sum of adventure ranks across all characters after the $$$n$$$ days, minus $$$c \times d$$$, where $$$d$$$ is the number of different characters she plays. As Grammy's best friend, your task is to compute the maximum value she can achieve under the optimal strategy for selecting characters.

Given a sequence $$$a_1, a_2, \cdots, a_n$$$ of length $$$n$$$ containing positive integers, we say an interval $$$[l, r]$$$ ($$$1 \le l \le r \le n$$$) is a divisible interval if there exists an integer $$$d$$$ such that $$$l \le d \le r$$$ and for all $$$l \le i \le r$$$, $$$a_i$$$ is divisible by $$$a_d$$$. We say the whole sequence is a divisible sequence if for all $$$1 \le l \le r \le n$$$, $$$[l, r]$$$ is a divisible interval.

Given another sequence $$$b_1, b_2, \cdots, b_n$$$ of length $$$n$$$ and an integer $$$k$$$, find all integers $$$x$$$ such that $$$1 \le x \le k$$$ and the sequence $$$b_1 + x, b_2 + x, \cdots, b_n + x$$$ is a divisible sequence. As the number of such integers might be large, you just need to output the number and the sum of all such integers.