Bakhtiar sir's Artificial Intelligence Lab is famous for its exciting 'Pacman' challenges. But some students, unwilling to risk their marks solving the tasks on the spot, have been secretly studying previous years' solutions passed down by seniors. However, this time Bakhtiar sir outsmarted them by introducing a brand new lab task — a twist on the classic Pacman game where the ghosts are replaced by Vampires.

The game proceeds in turns. In each turn, Pacman moves first, and then the vampires move one by one. Pacman will eat the food pellet immediately after reaching it. The game ends as soon as Pacman eats the food pellet and exits the game, or after $$$10^7$$$ turns.

The input of the task is a two-dimensional grid world containing:

• Walkable empty spaces (.)
• Impassable walls (#)
• The starting position of Pacman (P)
• One food pellet (F)
• Vampires (V)

The moves available to Pacman are:

• U (Up): Pacman moves one cell up if the cell above is within the grid and not a wall. Otherwise, Pacman stays in place.

• D (Down): Pacman moves one cell down if the cell below is within the grid and not a wall. Otherwise, Pacman stays in place.

• L (Left): Pacman moves one cell to the left if the cell to the left is within the grid and not a wall. Otherwise, Pacman stays in place.

• R (Right): Pacman moves one cell to the right if the cell to the right is within the grid and not a wall. Otherwise, Pacman stays in place.

• S (Stay): Pacman remains in the current cell.

• E (Exit): Ends the game immediately if Pacman has already eaten the food pellet. Otherwise, Pacman stays in place.

The moves available to each Vampire are:

• U (Up): Vampire moves one cell up if the cell above is within the grid and not a wall. Otherwise, Vampire stays in place.

• D (Down): Vampire moves one cell down if the cell below is within the grid and not a wall. Otherwise, Vampire stays in place.

• L (Left): Vampire moves one cell to the left if the cell to the left is within the grid and not a wall. Otherwise, Vampire stays in place.

• R (Right): Vampire moves one cell to the right if the cell to the right is within the grid and not a wall. Otherwise, Vampire stays in place.

• S (Stay): Vampire remains in the current cell.

After the end of any turn, if a Vampire that hasn't bitten Pacman yet is in the same cell as Pacman, it will bite it. Each Vampire can bite Pacman at most once, but multiple Vampires can bite Pacman after the same turn.

The output of the lab task is a sequence of moves for Pacman. After a student submits his move sequence, Bakhtiar sir's AI will read it and control the Vampires optimally to maximize the number of Vampires that can bite Pacman before the game ends.

Pacman gets +500 points for eating the food pellet. However, each time a Vampire bites Pacman, -10 points is added to the score (Pacman loses 10 points). The final score can be negative.

To obtain full marks in the lab, a student must submit a move sequence that maximizes the final score, despite the Vampires moving optimally.

Tanbir, surprised by this new task, wants to solve it carefully. Before actually finding a move sequence, he wants to know the maximum score that is theoretically achievable for a given grid and initial position of Pacman and vampires. Your task is to calculate this.

After Roman Reigns' historic 1316-day title reign came to an end at WrestleMania 40, his cousin Dwayne "The Rock" Johnson decided to write a 1316-page book chronicling the reign.

To make it iconic, he wants to number each page using Roman numerals. Unfortunately, The Final Boss is not very good at counting.

You need to help him convert the page numbers from standard representation to Roman numerals.

Roman numerals are a number system that uses letters from the Latin alphabet to represent values. The basic symbols and their corresponding values are:

Roman numerals are usually written from largest to smallest. When this rule is followed strictly, the numeral is evaluated as a sum of its parts. This is called additive notation. For example: $$$1316 = 1000 + 100 + 100 + 100 + 10 + 5 + 1 = \texttt{MCCCXVI}$$$.

However, to avoid repeating the same symbol four or more times in a row, Roman numerals also allow a smaller value to appear before a larger one. In such cases, the smaller value is subtracted from the larger. This is called subtractive notation. Examples: $$$\texttt{IV} = 5 - 1 = 4$$$, $$$\texttt{IX} = 10 - 1 = 9$$$, $$$\texttt{XL} = 50 - 10 = 40$$$, $$$\texttt{XC} = 100 - 10 = 90$$$, $$$\texttt{CD} = 500 - 100 = 400$$$, $$$\texttt{CM} = 1000 - 100 = 900$$$.

Using both additive and subtractive notation, the number $$$1248$$$ can be expressed as MCCXLVIII.

You are given a cursed number $$$m$$$ and an array $$$a$$$ of length $$$n$$$.

You will then be given $$$q$$$ queries. Each query is of one of the following two types:

1. 1 i x — Assign $$$a_i \gets x$$$.
2. 2 l r k — Determine the $$$k$$$-goodness of the subarray $$$a[l\,\dots\,r]$$$.

Your task is to process all the queries and print the result for each type 2 query.

A number is called good if it is not divisible by the cursed number $$$m$$$.

A number $$$x$$$ is called $$$k$$$-good if $$$x$$$ remains good after adding $$$k$$$ to it any number of times.

The $$$k$$$-goodness of an array $$$a$$$ is the number of elements in the array that are $$$k$$$-good.

A subarray of an array is a contiguous portion of it. Formally, if $$$a$$$ is an array of size $$$n$$$ and $$$1 \le l \le r \le n$$$, an array $$$a[l\,\dots\,r] = [a_l, a_{l+1}, \dots, a_r]$$$ is called a subarray of $$$a$$$.

The $$$k$$$-goodness of the subarray $$$a[l\,\dots\,r]$$$ is the number of integers $$$i \: (l \le i \le r)$$$ such that $$$a_i$$$ is $$$k$$$-good.

You were already dead from the neck up, now from the neck down.

— Thrall, the Disruptor

After winning a hard-fought battle against Ogre Magi, Thrall returned to his manufactory in upland Druud to repair his stormcrafting device. He was tinkering around with the plates of a faulty circular parallel plate capacitor that he retrieved from the heart of the device. Both of the circular plates have a uniform radius of $$$r$$$ units. Thrall wanted to control the distance $$$d$$$ between the two plates, and so he decided to join them by soldering many equally spaced strings of length $$$L$$$. One end of each string was soldered to the side of the $$$+ve$$$ plate, while the other end was soldered to the side of the $$$-ve$$$ plate.

(a) The circular plates of the capacitor.	(b) Thrall's contraption.

Figure 1: Salvaging the spoils of war.

This contraption enabled him to rotate one of the circular plates (say, the $$$+ve$$$ plate) and consequently calibrate the value of $$$d$$$.

(a) $$$\theta = 60^\circ$$$	(b) $$$\theta = 90^\circ$$$	(c) $$$\theta = 120^\circ$$$

Figure 2: Rotating the $$$+ve$$$ plate by different angles ($$$\theta$$$).

If Thrall rotates the $$$+ve$$$ circular plate by an angle of $$$\theta$$$ degrees, what would be the corresponding value of $$$d$$$, the distance between the circular plates?

After a grueling Division 2 contest, Nayeem fell asleep. The next morning, he woke up in a strange place called Borderland, where he was forced to participate in a peculiar challenge: the "Queen of Diamonds" game!

In the game arena, there is a line of $$$n$$$ bottles, each having a color label. Nayeem is armed with a special pistol. His task is to shoot and remove some (possibly none) bottles such that, in the remaining bottles, every color appears an even number of times.

Nayeem has to play multiple rounds. In each round, he will survive the game if and only if he can achieve this condition.

Your task is to determine the total number of different ways Nayeem can shoot the bottles. Two results are considered different if there is at least one bottle whose state (removed or kept) differs between them. Since the answer can be very large, output it modulo $$$1000000007$$$.

The garden at the Institute of Unbearable Torture (IUT) is known for its breathtaking beauty. Rows of vibrant flower columns line the pathways, each a testament to nature's charm. But lately, the greenery has started to fade.

There are $$$n$$$ flower columns in the garden. Each column has a total of $$$t_i$$$ flowers, out of which $$$s_i$$$ are healthy and green. To restore the garden's full glory, the campus gardening team will plant $$$m$$$ magical seeds. Each seed, when planted in a column, instantly grows into a new healthy flower.

The beauty score of a column is defined as: $$$\text{Score}_i = \dfrac{1}{t_i - s_i + 1}$$$

Your task is to determine the maximum average beauty score across all columns after planting the $$$M$$$ seeds optimally.

Faris loves to play with numbers. Today, he's looking for an interesting array. He defines an array of $$$n$$$ positive integers to be interesting if it satisfies the following property: $$$$$$\gcd(a_1, a_2, \dots, a_n) \lt \gcd(a_1, \dots, a_{i - 1}, a_{i + 1}, \dots, a_n) \text{ for all integer } i \text{ where } 1 \le i \le n$$$$$$

In other words, the GCD of the entire array is strictly less than the GCD of any subset formed by removing exactly one element.

Being amazed by this property, Faris has challenged you, a famous mathematician, to construct any such interesting array of size $$$n$$$ — but with an extra challenge: the LCM of the elements of the array cannot exceed $$$l$$$.

Given two integers $$$n$$$ and $$$l$$$, your task is to construct such an array, or report that it is impossible.

The greatest common divisor or GCD of a set of positive integers is the largest positive integer that divides all of them. Formally, $$$$$$\gcd(a_1, a_2, \dots, a_n) = \max \Bigl\{ d \in \mathbb{Z}^+ \ \big|\ d \mid a_i \ \forall i \in \{1, 2, \dots, n\} \Bigr\} $$$$$$

The least common multiple or LCM of a set of positive integers is the smallest positive integer that is divisible by all of them. Formally, $$$$$$\mathrm{lcm}(a_1, a_2, \dots, a_n) = \min \Bigl\{ m \in \mathbb{Z}^+ \ \big|\ a_i \mid m \ \forall i \in \{1, 2, \dots, n\} \Bigr\}$$$$$$

Little Pythagoras has a semicircular playhouse of radius $$$r$$$, where he loves to play with triangular toys. But he's very picky about his toys — he only plays with special ones he calls Pythagorean triangles.

A Pythagorean triangle is a non-degenerate triangle that has one right angle and all three of its side lengths are integers.

Today, Pythagoras is visiting the fair, which has toys of all possible shapes and sizes. Pythagoras wants to buy every Pythagorean triangle from the fair that can somehow fit entirely inside his playhouse.

Your task is to count the number of toys that Pythagoras will buy, i.e., the number of different Pythagorean triangles that can somehow fit inside his playhouse (one triangle at a time).

Two triangles are considered the same if their three side lengths are the same when sorted in non-decreasing order. For example, triangles with sides $$$(3,4,5)$$$ and $$$(5,3,4)$$$ are considered the same because their sorted side lengths are the same, i.e., $$$(3,4,5)$$$.

Flatland is on the verge of collapse.

Tensions between the East and the West have reached an all-time high, and civil unrest threatens to erupt at any moment. As a last-ditch effort to save the nation, both sides have agreed to a peace negotiation — and Pranto has been elected as the neutral mediator. The negotiations are scheduled to begin soon, but there's a problem: Pranto overslept. Woken up by a call from Shanto, Pranto realizes he has very little time left to reach the Negotiation Hall on the other side of Flatland. To make matters worse, private cars have been banned in Flatland to reduce traffic congestion. Now, Pranto must rely entirely on public transportation.

Flatland is organized as a grid of size $$$n \times m$$$, where each cell is a city. Pranto starts at city $$$u$$$, and the Negotiation Hall is at city $$$v$$$. A city is identified as a pair $$$(r, c)$$$, representing the city in the $$$r$$$-th row and $$$c$$$-th column. Additionally, each city has a boarding cost $$$B_{r,c}$$$ and a traffic jam $$$J_{r,c}$$$.

There are two types of public transport in Flatland:

• Trains travel horizontally between any two cities in the same row. A train ride takes exactly the horizontal distance between the start and end cities. Formally, you can go from a city $$$(r, c_1)$$$ to another city in the same row $$$(r, c_2)$$$ in time $$$|c_2 - c_1|$$$ using a train.

• Buses travel vertically between any two cities in the same column. A bus ride takes the vertical distance between the start and end cities plus the total traffic jam from all intermediate cities on that column, not including the endpoints. Formally, you can go from a city $$$(r_1, c)$$$ to another city in the same column $$$(r_2, c)$$$ in time $$$|r_2 - r_1| + \displaystyle\sum_{r = \min(r_1, r_2) + 1}^{\max(r_1, r_2) - 1} J_{r,c}$$$.

To board a train or a bus at city $$$(r, c)$$$, Pranto must pay a boarding cost of $$$B_{r,c}$$$. This cost is the same regardless of the destination or travel distance.

Your task is to help Pranto find the minimum total cost to reach the Negotiation Hall within at most $$$T$$$ units of time, or report that it is impossible.

Given two integers $$$L$$$ and $$$R$$$, your task is to compute the following three values:

• $$$A$$$: the bitwise AND of all integers from $$$L$$$ to $$$R$$$ inclusive.
• $$$O$$$: the bitwise OR of all integers from $$$L$$$ to $$$R$$$ inclusive.
• $$$X$$$: the bitwise XOR of all integers from $$$L$$$ to $$$R$$$ inclusive.

Formally, you need to compute: $$$$$$ A = L\ \&\ (L+1)\ \&\ (L+2)\ \&\ \dots\ \&\ R $$$$$$ $$$$$$ O = L\ |\ (L+1)\ |\ (L+2)\ |\ \dots\ |\ R $$$$$$ $$$$$$ X = L\ \oplus\ (L+1)\ \oplus\ (L+2)\ \oplus\ \dots\ \oplus\ R $$$$$$

Bitwise operations work on the binary representation of integers, operating on bits of the same positions of the numbers involved.

• & denotes the bitwise AND operation — the result has a $$$1$$$ only in bit positions where both numbers have a $$$1$$$. For example: $$$ 6 = 0110_2,\ 10 = 1010_2,\ 6\ \&\ 10 = 0010_2 = 2 $$$

• | denotes the bitwise OR operation — the result has a $$$1$$$ in bit positions where at least one number has a $$$1$$$. For example: $$$ 6 = 0110_2,\ 10 = 1010_2,\ 6\ | \ 10 = 1110_2 = 14 $$$

• $$$\oplus$$$ denotes the bitwise XOR operation — the result has a $$$1$$$ in bit positions where the bits of the two numbers are different. For example: $$$ 6 = 0110_2,\ 10 = 1010_2,\ 6\ \oplus\ 10 = 1100_2 = 12 $$$

This is an interactive problem.

You are Professor Utonium, the brilliant scientist of Townsville. You were about to start your project of creating the 'perfect little girls'. Unfortunately, you discover that your lab assistant Jojo has removed all the labels from the chemical containers in the lab.

Now, you have $$$N$$$ unlabeled chemicals, numbered from $$$1$$$ to $$$N$$$. Among them are two very dangerous chemicals – Chemical X and Chemical Y. When these two are mixed in the same mixture, they react explosively.

To identify the exact indices of Chemical X and Chemical Y, you'll need to carry out a series of controlled experiments. In each experiment, you may mix a subset of the chemicals in a secure environment. If both Chemical X and Chemical Y are present in the mixture, it results in "Kaboom" – an explosion! If not, you'll simply observe a "Noboom", meaning the mixture is stable.

But there's a catch — you can perform at most $$$20$$$ experiments before the Mayor and Miss Bellum shut the lab down for safety violations!

The interaction begins by reading the value of $$$N$$$.

After that, the experiments begin.

For performing an experiment, output $$$(m + 1)$$$ integers $$$(1 \le m \le N)$$$ in a line in the following format (without the quotes):

• "? m $$$c_1 \ c_2 \ \dots \ c_m$$$" $$$(1 \le c_i \le N \text{, where } 1 \le i \le m)$$$

Here, $$$\{c_1, c_2, \dots, c_m\}$$$ are the indices of the $$$m$$$ selected chemicals for the mixture. After each experiment, the judge will respond with:

• "Kaboom", if the experiment causes an explosion, i.e., the indices of Chemical X and Chemical Y are present in $$$\{c_1, c_2, \dots, c_m\}$$$.
• "Noboom", if the experiment doesn't cause an explosion.

After performing at most $$$20$$$ experiments, you must output your final answer in a line in the following format (without the quotes):

• "! x y" $$$(1 \le x \lt y \le N)$$$

Here, $$$x$$$ and $$$y$$$ are the indices of the explosive chemicals.

After printing a line, do not forget to output the end of the line and flush the output. Otherwise, you will get Idleness Limit Exceeded. To flush the output, you can use:

• fflush(stdout) in C;
• fflush(stdout), std::cout.flush() or std::cout « std::flush in C++;
• System.out.flush() in Java;
• sys.stdout.flush() in Python;
• std::io::stdout().flush() in Rust;
• Appropriate flush operation in any language.