SMRT Information Sign

The MRT Information System tells commuters when the next train will arrive. However, Bob is worried that displaying the next train's arrival time too directly may encourage commuters to run towards the platform, which is dangerous.

Bob is a software developer working on the next iteration of these information signs with safety in mind.

A day starts at time $$$0$$$. There are $$$n$$$ platforms. For platform $$$j$$$, trains arrive every $$$t_j$$$ minutes; that is, trains serving platform $$$j$$$ arrive at times $$$$$$0, t_j, 2t_j, 3t_j, \cdots$$$$$$ The station also has $$$m$$$ information signs. A commuter is estimated to take $$$d_{i,j}$$$ minutes to walk from sign $$$i$$$ to platform $$$j$$$.

Suppose a commuter leaves sign $$$i$$$ at time $$$x$$$ and walks to platform $$$j$$$. The sign displays the number of minutes from time $$$x$$$ until the earliest train they can catch. Formally, a commuter who starts walking from sign $$$i$$$ reaches platform $$$j$$$ at time $$$$$$ x + d_{i,j}. $$$$$$ The sign should display the difference between time $$$x$$$ and the arrival time of the earliest train at platform $$$j$$$ that arrives at or after time $$$x + d_{i,j}$$$.

For example, suppose it takes $$$d_{1,1} = 5$$$ minutes to walk from sign $$$1$$$ to platform $$$1$$$, and trains arrive at platform 1 every $$$t_{1} = 6$$$ minutes.

• At time $$$x = 1$$$, the commuter reaches the platform at time $$$6$$$. The earliest train they can catch arrives at time $$$6$$$, so the sign displays $$$6-1 = 5$$$.
• At time $$$x = 2$$$, the commuter reaches the platform at time $$$7$$$. The earliest train they can catch arrives at time $$$12$$$, so the sign displays $$$12 - 2 = 10$$$.

Help Bob answer $$$q$$$ queries. For each query $$$(x,i,j)$$$, output the number of minutes displayed on sign $$$i$$$ for platform $$$j$$$ at time $$$x$$$ minutes from the start of the day.

Once upon a time, Billy had an array $$$a$$$ of length $$$n$$$ such that $$$a_i = i$$$ for all $$$1\leq i \leq n$$$, and an integer $$$m$$$ ($$$m \gt n$$$). The array $$$a$$$ was then cyclically shifted to the right by $$$k$$$ positions to form the array $$$b$$$.

For example, when $$$n= 5$$$ and $$$k = 2$$$, the arrays $$$a$$$ and $$$b$$$ are given as follows: $$$$$$ a = [1,2,3,4,5] \longrightarrow \text{cyclic right-shift by 2} \longrightarrow b=[4,5,1,2,3] $$$$$$

Billy may perform one type of operation on array $$$b$$$, consisting of two steps:

1. Choose two integers $$$l$$$ and $$$r$$$ such that $$$1\leq l \leq r \leq n$$$
2. For each index $$$i \in [l, r]$$$, set $$$b_i \leftarrow (b_i + 1) \text{ mod } m$$$

Billy especially loves arrays in which every element is $$$0$$$. Help Billy find the minimum number of operations required to transform $$$b$$$ into $$$[0, 0,\cdots, 0]$$$.

At Britain's Got Talent 2026, Rafferty wants to perform a card trick using a deck of $$$n$$$ cards in a predetermined order.

Each card has:

• a face-up number from $$$1$$$ to $$$13$$$,
• a face-down handwritten letter, which is one of B, E, L, I, V.

The trick begins with all cards in the deck face-up.

1. The audience member chooses an index $$$i$$$ ($$$1 \le i \le n-6$$$), discards the first $$$i-1$$$ cards, and keeps the next $$$7$$$ cards, namely positions $$$i,i+1,\dots,i+6$$$.
2. These $$$7$$$ cards are then arranged in increasing order of their face-up numbers.

from left to right.

Final result of the trick$$$^{1}$$$. The face-down letters of the cards at positions $$$i$$$ to $$$i+6$$$ spell BELIEVE when arranged in ascending order of face-up numbers. The BGT crowd goes wild — somehow, this is inspirational.

In other words, for the chosen window of $$$7$$$ cards:

• after sorting the cards by face-up number in increasing order,
• the corresponding face-down letters must be B, E, L, I, E, V, E.
• all face-up numbers must be distinct. Otherwise, cards with equal numbers could be reordered arbitrarily, which may destroy the word BELIEVE.

Your task is to construct the entire deck so that this works for every valid choice of $$$i$$$ ($$$1\leq i \leq n-6$$$).

$$$^{1}$$$ Watch the trick at https://www.youtube.com/watch?v=BCHkMexXu40&t=6m14s.

Alice and Bob play a Duel of Ten on an array $$$a$$$ of length $$$n$$$ ($$$\boldsymbol{-10^9} \leq a_i \leq 10^9$$$). They take turns making moves, with Alice going first. The rules of "Duel-of-Ten" are as follows:

• Let the current length of the array $$$a$$$ be $$$m$$$ (initially $$$m = n$$$).
• On Alice's turn, Alice chooses two distinct indices $$$x$$$ and $$$y$$$ ($$$1\leq x \lt y \leq m$$$) and removes elements $$$a_x$$$ and $$$a_y$$$ from $$$a$$$, then inserts $$$\min(a_x, a_y)$$$ into $$$a$$$.
• On Bob's turn, Bob chooses two distinct indices $$$x$$$ and $$$y$$$ ($$$1\leq x \lt y \leq m$$$) and removes elements $$$a_x$$$ and $$$a_y$$$ from $$$a$$$, then inserts $$$\max(a_x, a_y)$$$ into $$$a$$$.

The game ends when the array $$$a$$$ contains only one element. If the remaining element has an absolute value less than 10, Alice wins. Otherwise, Bob wins.

Given an array $$$a$$$, determine who wins if both players play optimally.

Alice initially has a weighted undirected tree $$$T$$$ of $$$n$$$ nodes and $$$n-1$$$ edges. Each edge has a positive integer weight.

Alice wants to design a route so that she can walk for as long as possible, but she does not want to walk forever. To do so, she chooses a direction for every edge of the tree. In other words, for each undirected edge $$$(u,v)$$$, she replaces it with exactly one of the directed edges $$$u\rightarrow v$$$ or $$$v\rightarrow u$$$, preserving its weight $$$w_{uv}$$$. This produces a directed graph $$$T'$$$.

After constructing $$$T'$$$, Alice chooses a starting vertex $$$r$$$ ($$$1\leq r\leq n$$$), and performs the following walk:

• Suppose Alice is currently at vertex $$$u$$$.
• If $$$u$$$ has no outgoing edge in $$$T'$$$, her walk ends.
• Otherwise, she chooses one outgoing neighbour $$$v$$$ uniformly at random from all vertices $$$v$$$ such that $$$u\rightarrow v$$$ in $$$T'$$$, and traverses that edge.

Over all possible choices of edge directions and the starting vertex $$$r$$$, help Alice maximize the expected total distance she walks, modulo $$$10^9 + 7$$$.

It can be shown that the answer can always be written as a fraction $$$\frac{P}{Q}$$$, where $$$Q \not\equiv 0 \pmod{10^9+7}$$$. Therefore, output the value $$$$$$ P\cdot Q^{-1} \text{ mod }(10^9 + 7) $$$$$$

Jon has $$$n$$$ tasks and $$$m$$$ units of time. There are also $$$m$$$ cash prizes, where prize $$$j$$$ is worth $$$v_j$$$ dollars.

Task $$$i$$$ requires a duration of $$$a_i$$$ to complete. If Jon completes task $$$i$$$, he becomes eligible for cash prize $$$p_i$$$ where $$$$$$ p_i = \lfloor\frac{m}{a_i}\rfloor, $$$$$$ receiving $$$v_{p_i}$$$ dollars. If several completed tasks correspond to the same prize, Jon receives that prize only once.

Jon may choose any subset of tasks and complete them in any order, as long as the total time taken by the chosen tasks does not exceed $$$m$$$.

Find the maximum amount of money, in dollars, that Jon can receive today.

You live in a city with a mysterious transportation network consisting of $$$n$$$ locations and $$$m$$$ bi-directional roads. For the $$$i$$$-th road ($$$1\leq i \leq m$$$), the time taken to travel across it is $$$2^{i-1}$$$ minutes.

Alice is new to the city and is getting ready for her road trips. However, to her horror, Google Maps is not available in this city!

Alice turns to you, an aspiring competitive programmer. Alice's house is located at location $$$1$$$. For every location $$$v$$$ ($$$2\leq v \leq n$$$), please help Alice find the minimum travel time from location $$$1$$$ to location $$$v$$$, and output that time modulo $$$998244353$$$.

Apollo, the god of prophecy, has hidden an integer $$$n$$$ ($$$1\leq n\leq 10^8$$$). Mortals are not allowed to know $$$n$$$ directly, but Apollo may answer queries and perform divisions for you.

One of Apollo's prophecies states that an integer $$$x$$$ is sacred if and only if $$$x$$$ has at most $$$8$$$ positive divisors.

Although mortals do not know Apollo's value of $$$n$$$, Apollo believes you are no mere mortal. Prove your worthiness by reducing $$$n$$$ to a sacred value $$$n'$$$ (where $$$n' \leq n$$$).

For the purposes of this interaction, the jury acts on Apollo's behalf.

The interaction begins when you ask your first query. On your turn, you can make one of three types of queries:

• gcd d ($$$1\leq d \leq 10^{18}$$$) followed by a newline. The jury then returns $$$\gcd(n, d)$$$. The value of $$$n$$$ is unchanged by this query.
• div d ($$$1\leq d \leq 10^{18}$$$) followed by a newline. If $$$d$$$ divides $$$n$$$, the jury replaces $$$n$$$ with $$$n/d$$$ and returns 1; otherwise $$$n$$$ is unchanged and the jury returns 0.
• ! followed by a newline. This declares that the current value of $$$n$$$ is sacred. Your program should terminate immediately after this.

In the event that you read -1 instead of valid data, your program must terminate immediately. This indicates that your submission has made an invalid query or has otherwise received a Wrong Answer verdict.

You are given an infinite sequence of points $$$p_0, p_1, p_2,\cdots$$$ defined as: $$$$$$ p_0=(1,0), \quad p_1=(1,\frac{1}{2}), \quad p_i=(\frac{1}{i}, \frac{1}{i+1}) \quad \mathrm{for}\ i\geq 1 $$$$$$ The sequence continues indefinitely and approaches the point $$$(0,0)$$$. See the figure in the sample test case for an illustration of the sequence and the polygon $$${\cal P}$$$.

The polygon $$${\cal P}$$$ is created by connecting the points in order with line segments $$$$$$ p_0\rightarrow p_1\rightarrow p_2\rightarrow \cdots $$$$$$ The boundary is completed by adding the segment from $$$(0,0)$$$ to $$$p_0$$$.

Answer $$$q$$$ queries. Each query $$$(n_x, d_x, n_y, d_y)$$$ represents a point $$$$$$ Q =(\frac{n_x}{d_x},\frac{n_y}{d_y} ). $$$$$$ For each query, compute the minimum Euclidean distance from $$$Q$$$ to the region enclosed by $$${\cal P}$$$. Thus, if $$$Q$$$ lies inside or on the boundary of $$${\cal P}$$$, the distance is $$$0$$$.

There are $$$n$$$ streets in a city, numbered from $$$1$$$ to $$$n$$$. For every $$$1\leq i \leq n-1$$$, street $$$i$$$ and $$$i+1$$$ are connected by a two-way road with travel time $$$t_i$$$ units.

There is also one police station on each street. The $$$i$$$-th station is located on street $$$i$$$, has a forwarding time delay of $$$f_i$$$ units, and a response time delay of $$$r_i$$$ units.

Station $$$s$$$ receives an emergency call reporting a crime at street $$$d$$$. The receiving station then chooses one of the following actions:

• Forward the call: If there exists a station $$$k$$$ on a higher-indexed street ($$$k \gt s$$$) with shorter response time delay, that is, $$$r_k \lt r_s$$$, station $$$s$$$ may forward the call to the nearest such station $$$k^*$$$. After a forwarding time delay of $$$f_s$$$ time units, station $$$k^*$$$ receives the forwarded call.
• Respond to the call: After a response time delay of $$$r_s$$$ time units, a police car is dispatched from street $$$s$$$ and travels by road to street $$$d$$$, incurring the corresponding road travel time.

The city receives $$$q$$$ emergency calls of the form $$$(s,d)$$$. For each call, find the minimum total response time if station $$$s$$$ initially receives a call of a crime at street $$$d$$$.

A suspicious streamer named TLE Creators proposed an algorithm to sort a permutation. Note that the code below uses one-indexed positions.

Function CyclicSort(arr):
     pos = 1
     WHILE (arr is not sorted) DO
        index = find the index of the minimum element in arr[pos...n]
        shifts = index - pos
        FOR (i = 1...shifts) DO
            cyclically shift left arr[pos...n] by one position
        END
        pos = pos + 1
     END  
END

Let's consider an example by performing CyclicSort on the permutation $$$p = [2,4,1,3,5]$$$.

• pos $$$=1$$$. The minimum element is at position $$$3$$$ ($$$p_3 = 1$$$), and the subarray $$$p_{1\cdots 5}$$$ is cyclically shifted to the left by one position twice, incurring $$$2$$$ operations. The resulting array is $$$p^{(1)} = [1,3,5,2,4]$$$.
• pos $$$=2$$$. The minimum element is at position $$$4$$$ ($$$p^{(1)}_4 = 2$$$), and the subarray $$$p_{2\cdots 5}^{(1)}$$$ is cyclically shifted to the left by one position twice, incurring $$$2$$$ operations. The resulting array is $$$p^{(2)} = [1,2,4,3,5]$$$.
• pos $$$=3$$$. The minimum element is at position $$$4$$$ ($$$p^{(2)}_4 = 3$$$), and the subarray $$$p_{3\cdots 5}^{(2)}$$$ is cyclically shifted to the left by one position once, incurring $$$1$$$ operation. The resulting array is $$$p^{(3)} = [1,2,3,5,4]$$$.
• pos $$$=4$$$. The minimum element is at position $$$5$$$ ($$$p^{(3)}_5 = 4$$$), and the subarray $$$p_{4\cdots 5}^{(3)}$$$ is cyclically shifted to the left by one position once, incurring $$$1$$$ operation. The resulting array is $$$p^{(4)} = [1,2,3,4,5]$$$.
• Since the array is sorted, the algorithm terminates.

TLE Creators proved that CyclicSort always sorts any permutation in ascending order, but they are having difficulty determining the number of cyclic left-shift operations that CyclicSort will perform. They are going live right after your contest, and desperately need your help!

Given a permutation $$$p$$$ of length $$$n$$$, please help TLE Creators determine the number of cyclic left-shift operations that CyclicSort will perform.