The Republic of San Magnolia is at war against the autonomous Legion forces and is currently on the back foot. The Republic's military operates $$$n$$$ combat units on the battlefield, and if too many of them are destroyed, the Republic will be forced to abandon the front.

Each day, the Legion launches an attack on every unit exactly once. However, not all attacks are guaranteed to destroy a unit, as each unit is equipped with defensive systems. For the $$$i$$$-th unit, there is a $$$\dfrac{x_i}{y_i}$$$ probability that a single attack will destroy it. Otherwise, the attack is repelled, and the unit remains operational for the day, taking no damage.

All attacks across different units and on different days are independent. Once a unit is destroyed, it remains destroyed and cannot become operational again.

You are a citizen trying to understand how long the Republic can continue the war. However, due to misinformation and limited access to the battlefield, different sources report different states of the front lines. Each report claims that a subset of units is operational, which means all others are already destroyed.

The Republic can continue fighting as long as at least $$$k$$$ units remain operational. The front will collapse as soon as fewer than $$$k$$$ units remain.

For each report, determine the expected number of days the Republic can continue fighting, on the condition that the report is accurate.

This is an interactive problem. You must flush the output after printing each line. For example, in C++ use fflush(stdout), in Java — System.out.flush(), and in Python — sys.stdout.flush().

You have to find a hidden integer $$$X$$$ $$$(1 \le X \le 10^{15})$$$ using an interactive system.

Let the representation of $$$X$$$ in base $$$n$$$ be: $$$ X = d_k n^k + d_{k-1} n^{k-1} + \dots + d_1 n^1 + d_0 n^0 $$$, where $$$0 \le d_i \lt n$$$ for all $$$i$$$.

You may ask questions. In each question, you provide an integer base $$$n$$$ $$$(2 \le n \le 100)$$$ and a boolean value $$$b \in \{0, 1\}$$$.

The system will return:

• If $$$b = 0$$$, the sum of digits at even positions in the base $$$n$$$ representation of $$$X$$$: $$$\sum d_{2i}$$$ for $$$i \in \{0, 1, 2, \dots\}$$$.
• If $$$b = 1$$$, the sum of digits at odd positions in the base $$$n$$$ representation of $$$X$$$: $$$\sum d_{2i+1}$$$ for $$$i \in \{0, 1, 2, \dots\}$$$.

After at most $$$10$$$ questions, you have to output the value of $$$X$$$.

All numbers are in base 10 unless otherwise specified.

To ask a question, print a line in the format "? $$$n$$$ $$$b$$$" (without quotes), where $$$n$$$ is the base and $$$b$$$ is the boolean value. After each query, read an integer $$$S$$$ — the sum of digits returned by the system.

When you are ready to provide the answer, print a line in the format "! $$$X$$$" (without quotes), where $$$X$$$ is the hidden integer.

Your program can ask at most $$$10$$$ questions. Note that the final line "! $$$X$$$" is not counted as a question.

You are driving a jeep called Chander Gari along the hilly roads from Bandarban to Thanchi. The route consists of $$$n$$$ segments, where segment $$$i$$$ connects Checkpoint $$$i-1$$$ to Checkpoint $$$i$$$. The jeep is equipped with a fuel tank of maximum capacity $$$c$$$ liters and you begin your journey at Checkpoint $$$0$$$ with a full tank.

To travel from Checkpoint $$$i-1$$$ to Checkpoint $$$i$$$, the jeep consumes $$$w_i$$$ liters of fuel. If the tank contains less than $$$w_i$$$ liters of fuel before departure, the jeep stalls and the journey ends.

Upon arriving at any checkpoint $$$i$$$ $$$(1 \le i \le n)$$$, you have the option to refuel. Due to a severe crisis, fuel is strictly limited. If you choose to stop and refuel, the vendor will fill the jeep's tank with exactly $$$r$$$ liters of fuel. If this causes the fuel level to exceed the capacity $$$c$$$, the excess fuel overflows and is wasted.

Your task is to determine a refueling strategy that ensures the jeep safely reaches Checkpoint $$$n$$$ while minimizing the total number of times you stop to refuel.

You are given a rooted tree consisting of $$$n$$$ vertices, numbered from $$$1$$$ to $$$n$$$. Vertex $$$1$$$ is the root.

Each vertex $$$v$$$ initially stores a function

$$$$$$ f_v(x) = a_v x + b_v, $$$$$$

where $$$a_v$$$ and $$$b_v$$$ are positive integers.

You have to perform the following operation exactly $$$n-1$$$ times until only the root vertex remains:

1. Choose a vertex $$$u$$$ $$$(u \neq 1)$$$ that is currently a leaf in the tree.
2. Let $$$p$$$ be the parent of $$$u$$$.
3. Update the function stored at vertex $$$p$$$ to be the composition of the function at $$$u$$$ and the current function at $$$p$$$: $$$$$$ f_p(x) \leftarrow f_u(f_p(x)) $$$$$$
4. Remove vertex $$$u$$$ and the edge $$$(u, p)$$$ from the tree.

After $$$n-1$$$ operations, only vertex $$$1$$$ remains with a final function $$$F(x)$$$. Your task is to maximize the value of $$$F(0)$$$.

In the late 1950s, the renowned Bengali mathematician Professor Raj Chandra Bose was working to disprove Euler's long-standing conjecture on Latin Squares at Case Institute of Technology. During his visit, he noticed an exceptional undergraduate student attending his graduate level classes. Impressed by his ability, he invited the student, Donald Knuth, to assist with computational tasks.

As part of this work, Knuth needed to construct a permutation of length $$$n$$$, but only a partial version of the permutation is known.

He is given an array $$$a$$$ of length $$$n$$$, where some elements are known and others are missing. Missing elements are represented by $$$-1$$$.

Your task is to help Knuth replace each occurrence of $$$-1$$$ in $$$a$$$ with a value from $$$1$$$ to $$$n$$$ such that:

• The final array $$$a$$$ becomes a valid permutation of integers from $$$1$$$ to $$$n$$$.
• The value of the following expression is minimized: $$$$$$\sum_{i=2}^{n} (a_i - a_{i-1})$$$$$$

If multiple valid permutations achieve the minimum value, print any of them.

Note: A permutation of length $$$n$$$ is an array of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$, each appearing exactly once. For example, $$$[1]$$$, $$$[4, 3, 5, 1, 2]$$$, and $$$[3, 2, 1]$$$ are permutations, while $$$[1, 1]$$$ and $$$[4, 3, 1]$$$ are not.

For any positive integer $$$n$$$, let $$$S$$$ be its decimal representation without leading zeros. A subsequence of $$$n$$$ of length $$$k$$$ is formed by selecting $$$k$$$ indices $$$1 \le i_1 \lt i_2 \lt \dots \lt i_k \le |S|$$$.

Two subsequences are considered different if their sets of chosen indices are different, even if the resulting strings of digits are identical.

Let $$$F(n, k, d)$$$ be the number of different subsequences of $$$n$$$ of length $$$k$$$ that consist of exactly $$$d$$$ distinct digit values.

You are given a range $$$[L, R]$$$ and $$$Q$$$ independent queries. For each query $$$(k, d)$$$, calculate: $$$$$$ \sum_{i=L}^{R} F(i, k, d) $$$$$$

Since the result can be large, output it modulo $$$(10^9 + 7)$$$.

The Boro harvest in the haor region of Kishoreganj is in progress. A sudden flash flood alert warns that heavy upstream rains will flood the fields. To respond, all farming must be completed exactly within 1 day, neither earlier nor later.

The farming consists of two operations:

• Harvesting $$$x$$$ units of paddy
• Drying $$$y$$$ units of paddy

The village has unlimited workers. A configuration is defined by two positive integers $$$(p, q)$$$, where $$$p$$$ workers are assigned to harvesting and $$$q$$$ workers are assigned to drying. Each worker completes $$$1$$$ unit of work per day, and work is evenly divided among workers. A configuration is considered valid if the sum of the time required to complete harvesting and the time required to complete drying is exactly $$$1$$$ day.

For example, when $$$x = 1$$$ and $$$y = 2$$$:

• If $$$(p, q) = (3, 3)$$$, then harvesting takes $$$\frac{1}{3}$$$ day and drying takes $$$\frac{2}{3}$$$ day, so the total time is $$$1$$$ day.
• If $$$(p, q) = (2, 4)$$$, then harvesting takes $$$\frac{1}{2}$$$ day and drying takes $$$\frac{1}{2}$$$ day, so the total time is $$$1$$$ day.

Thus, both configurations are valid.

Your task is to find all valid configurations.

Rabiul is the quality inspector of a Bangladeshi fruit exporting company. Today, he is standing beside a conveyor belt carrying $$$n$$$ freshly harvested Himshagor mangoes, each tagged with a sweetness value $$$a_i$$$. A buyer from New Zealand has placed an order for a premium batch.

A batch is defined as a contiguous segment of at least $$$k$$$ mangoes from the belt. A batch is called premium if its representative sweetness is exactly $$$x$$$.

For a batch of size $$$m$$$ with sweetness values $$$b_1, b_2, \dots, b_m$$$, the representative sweetness is defined as the sweetness value of the element at position $$$\displaystyle \left\lfloor \frac{m+1}{2} \right\rfloor$$$ after sorting the $$$m$$$ sweetness values in non-decreasing order. For example, the representative sweetness of the batch $$$[4, 7, 5, 7]$$$ is $$$5$$$.

Help Rabiul determine whether there exists any such premium batch on the conveyor belt.

Alice has recently been appointed as the commander of a mercenary guild in the dangerous realm of Iron Escort. Her first contract requires her to travel safely through $$$N$$$ consecutive regions in order, from region $$$1$$$ to region $$$N$$$, but the roads are treacherous.

Alice starts her journey alone, with $$$0$$$ guards. Before stepping into any region, she evaluates her current party size, let's denote it as $$$u$$$, and decides on a new party size, $$$v$$$. Due to logistical constraints, she can adjust her party size by at most $$$K$$$ guards at a time. This means the absolute difference between $$$u$$$ and $$$v$$$ cannot exceed $$$K$$$, and her party size $$$v$$$ can never be negative.

Managing her escort party requires spending coins:

• Alice pays a hiring fee of $$$H$$$ coins for every new guard she hires.
• Alice pays a wage of $$$S$$$ coins to every guard currently in her newly chosen party of $$$v$$$.

If Alice decides to dismiss guards to reach her new party size, she receives no refunds, but she successfully avoids paying wages for those dismissed individuals. Overall, her total logistical cost before entering a region is exactly $$$H \cdot \max(0, v - u) + S \cdot v$$$.

Once the logistics are settled and wages are paid, Alice's party steps into the $$$i$$$-th region. Danger strikes immediately upon crossing the border, where the party faces the region's innate danger level, $$$D_i$$$. If Alice's chosen guard count $$$v$$$ is strictly less than $$$D_i$$$, bandits ambush the under-protected caravan, forcing her to pay a steep penalty of $$$P_i \cdot (D_i - v)$$$ coins, dictated by the region's specific ambush penalty multiplier, $$$P_i$$$.

After surviving the initial perils of the border, the party must travel deeper into the local warlord's territory. These warlords are fiercely territorial and strictly enforce a martial limit, $$$M_i$$$, refusing to let massive private armies freely roam their lands. If Alice's party arrives at these checkpoints with a guard count exceeding $$$M_i$$$, the local forces permanently confiscate the excess guards without offering any compensation. This abruptly forces her party size down to exactly $$$M_i$$$ guards before she can proceed to the next region, whereas a smaller party is allowed to pass with its numbers intact.

Help Alice find the minimum total number of coins she needs to spend to successfully complete her contract and travel through all $$$N$$$ regions.

In the heart of 17th-century Dhaka, the construction of the Lalbagh Fort is underway. To secure the southern gate, the royal architect has designed a complex locking mechanism consisting of $$$n$$$ interlocking brass gears.

The total number of gears, $$$n$$$, is determined by the number of days $$$k$$$ spent on the gate's construction. On the $$$1$$$st day, $$$1$$$ gear was installed. On each subsequent day, the builders added the next consecutive odd number of gears ($$$3$$$ on the second day, $$$5$$$ on the third, and so on).

Each gear in the system is unique, numbered $$$1, 2, \ldots, n$$$. A gear numbered $$$x$$$ has exactly $$$x$$$ teeth. For the mechanism to rotate without friction, the architect only selects gears that are mechanically stable.

The stability of a gear is determined by its rotational partitions. A gear with $$$x$$$ teeth can be partitioned into $$$m$$$ equal-sized segments, where $$$m$$$ is any integer that divides $$$x$$$. A gear is mechanically stable only if the number of ways to partition it into segments containing an even number of teeth is perfectly balanced by the number of ways to partition it into segments containing an odd number of teeth.

For example, consider gear $$$6$$$. It can be partitioned into segments of size $$$1$$$, $$$2$$$, $$$3$$$, or $$$6$$$.

• Segments of size $$$2$$$ and $$$6$$$ are even-sized.
• Segments of size $$$1$$$ and $$$3$$$ are odd-sized.

Since there are exactly two even-sized partition options and two odd-sized partition options, gear $$$6$$$ is stable.

Given the number of construction days $$$k$$$, calculate how many mechanically stable gears are in the Lalbagh gate.