The local Baladeya has just installed a new automated ticket machine to distribute citizens among $$$N$$$ agents sitting at the counters. At the start of the shift, the Chef Service Fathi configures the ticket machine with two parameters, $$$S$$$ and $$$K$$$. The machine then routes the $$$i$$$-th arriving citizen (starting from $$$i = 0$$$) to agent number $$$(S + i \cdot K) \pmod{N}$$$.

Naturally, the agents are super lazy and want to avoid work at all costs. Due to this routing policy, only a subset of agents will ever actually receive citizens. We call these the unlucky agents (or active agents). Let $$$L$$$ denote the number of unlucky agents.

Each agent $$$k$$$ ($$$0 \le k \lt N$$$) has a "complaining factor" $$$M_k$$$, which represents the amount of headache they cause the manager if they are forced to actually do their work (measured in the number of express coffees they demand, sudden "réseau tayah" excuses and phone calls they make during work).

To survive the day, the Chef Service must maximize the Baladeya's operational efficiency while minimizing his total headache. On one hand, every active agent adds their complaining factor to his daily stress. On the other hand, if too few agents are working, operational efficiency plummets, resulting in massive queues and a severe penalty from angry citizens and higher-ups.

Formally, the Chef Service wants to minimize the total cost (which balances his headache and the inefficiency penalty), defined as: $$$$$$ \text{TotalCost} = \left(\sum_{k \in \text{unlucky}} M_k\right) + \left \lfloor \frac{N}{2} \right \rfloor \cdot (N - L + 1) $$$$$$

Your task is to help the Chef Service find the values of $$$S$$$ and $$$K$$$ that minimize the total cost.

You are given a number $$$N$$$ of "legal" labs connected by bidirectional corridors, forming a connected graph. There are $$$M$$$ types of crystals. Every lab makes all types of crystals but specializes in some crystal types, as indicated by a binary string in the input. On day 0, lab $$$i$$$ owns $$$x_{ij}$$$ units of crystal type $$$j$$$.

Every night, all labs update their crystal inventories simultaneously. For a fixed crystal type $$$k$$$, lab $$$i$$$ performs the following process:

A "researcher" from the $$$i$$$ th lab will visit every other lab that can be reached through exactly $$$k$$$ corridors (he can use the same corridor multiple times along his path and it counts). For every possible lab $$$j$$$ that can be reached this way:

- If lab $$$j$$$ specializes in crystal $$$k$$$ and lab $$$i$$$ does not, lab $$$i$$$ gains $$$x_{jk}$$$ (lab $$$j$$$ is not affected).

- If lab $$$i$$$ specializes in crystal $$$k$$$ and lab $$$j$$$ does not, lab $$$i$$$ gains $$$x_{jk}$$$ (lab $$$j$$$ is not affected).

- Otherwise, nothing is gained.

The new amount of crystal $$$k$$$ in lab $$$i$$$ is: the old amount plus all the gained amounts.

All labs compute their new inventories using only the previous day's values.

Your task is to determine, on day $$$D$$$, whether each lab has an odd or even number of each crystal type.

you and your friends came up with a reasonable plan: Rob a Aziza supermarket.

However, the store has installed a new security system to prevent such attempts.

To bypass the security, you must generate a key consisting of $$$n$$$ positive integers ( $$$0 \lt a_i \lt 10^9$$$ ) where the sum of the numbers is equal to their product.

Formally, you need to find a sequence $$$a_1, a_2, \dots, a_n$$$ ( where $$$a_i \gt 0$$$ and $$$a_i \lt 10^9$$$ for all i ) such that: $$$$$$ \sum_{i=1}^{n} a_i = \prod_{i=1}^{n} a_i $$$$$$

Your task is simple: for a given $$$n$$$, output any sequence of $$$n$$$ positive integers satisfying this condition.

It is guaranteed that a solution always exists for all given $$$n$$$.

The city of Sousse is a popular touristic destination, it has n important locations connected by m directed streets.

A popular tourist activity is to take a "walk" through the city: starting at some location and moving along a sequence of directed streets to reach another location. The length of the walk is the number of streets traversed.

For statistical purposes, the city wants to know the total number of possible walks in the city that use at most L streets. This includes walks between any starting point $$$u$$$ and any ending point $$$v$$$ (including walks of length $$$0$$$, where the tourist stays at the same location).

Since the numbers can be huge, they should be reported modulo $$$M=10^9+7=1000000007$$$.

Given the directed graph of $$$n$$$ locations and $$$m$$$ streets, calculate a single integer: the total number of walks of length between $$$0$$$ and $$$L$$$ (inclusive) over all ordered pairs of locations $$$(u, v)$$$, modulo $$$M$$$.

Rami and Khalil are fierce competitors in two-player games. This time, they agreed to play the following turn-based game, designed by Khalil.

The game starts with a list of $$$n$$$ positive integers $$$A = [A_1, A_2, \dots, A_n]$$$.

On each turn, the current player selects one number $$$A_i$$$ from the list and replaces it with either:

• A proper divisor of $$$A_i$$$ (a positive divisor less than $$$A_i$$$ itself), or
• Any positive integer whose number of distinct prime factors is strictly less than that of $$$A_i$$$.

The player who cannot make a move on their turn loses. Khalil will be the starting player.

While Khalil was carefully considering his first move, Rami realised something interesting: he can sneakily add some positive integers to the list before the game starts to guarantee his win (as the second player).

Since Rami wants to avoid suspicion, he needs to minimize the number of integers he adds. If multiple minimal solutions exist, any valid set will work.

Help Rami determine the smallest set of positive integers (possibly empty) that he can add to the list so that he will win assuming both players play optimally.

This is an interactive problem

In ancient Carthage, scholars created a secret numerical cipher to protect their most valuable trade secrets. This cipher, believed to be a function $$$f$$$, that maps each natural number to a secret value, was known only to the High Council of Merchants. The cipher was lost when Rome destroyed Carthage in 146 BC.

For centuries, archaeologists have searched for the legendary "Stone of Accounts", the key to unlocking this ancient secret.

Recently, in the ruins of ancient Carthage near modern-day Tunis, you've discovered the fabled Stone of Accounts! It's a mysterious device with two input slots and one output display. Ancient Punic inscriptions explain how it works: "Place two numbered stones in the slots. If their numbers sum to a power of two, the stone reveals the sum of their hidden values. Otherwise, it reveals nothing."

Formally, The Stone accepts two positive integers $$$n$$$ and $$$m$$$:

• If $$$n+m$$$ is a power of two, it outputs $$$f(n)+f(m)$$$
• Otherwise, it outputs $$$0$$$

Centuries ago, archaeologists discovered ancient Carthaginian scrolls containing encrypted trade secrets: $$$S=[S_1,\dots,S_n].$$$ For generations, scholars have tried to decipher them, but without the Stone of Accounts, all attempts failed.

Now, with the Stone finally discovered, you have a chance to succeed where others could not.

Your mission: Recover the true message $$$M=[f(S_1),\dots,f(S_n)].$$$ But be careful! The Stone is ancient and fragile. You can use it at most 10,000 times before it breaks forever.

Your program will interact via standard input/output with the black box.

Starting from $$$i=1$$$, two modes of operations are supported:

1. Query the Stone, ? n m: You give two positive integers $$$1 \le n,m \lt 2^{64}$$$ to the Stone. The Stone responds with R s where:
   • $$$s=f(n)+f(m)$$$ if $$$n+m$$$ is power of two
   • $$$s=0$$$ otherwise
2. Declare a Decrypted Value, ! d: This means you've determined that $$$d=f(S_i)$$$. After this command:
   • You receive N.
   • You move to the next encrypted number: $$$i\leftarrow i+1$$$
   • When all numbers are decrypted, your program can exit.

It is the day of the Grand Derby at the Stade Hammadi Agrebi in Radès. The stadium is packed to capacity, and the atmosphere is electric.

As the lead audio engineer for the broadcast, you are monitoring a row of $$$n$$$ passionate fans in the "Virage" stand. Each fan at position $$$i$$$ has a specific vocal intensity level, represented by an integer $$$a_i$$$.

When a continuous segment of fans chants together, their voices create a "Resonance Wave". The Total Resonance of the segment from index $$$l$$$ to index $$$r$$$ is defined as the product of their individual intensities: $$$$$$ \text{Resonance}(l, r) = a_l \times a_{l+1} \times \dots \times a_r $$$$$$

The stadium's modern "Smart Audio System" filters noise based on power tiers. For a chant to be successfully broadcast clearly on the high-definition channel of Tier $$$k$$$, its Total Resonance must be divisible by $$$10^k$$$.

You must process $$$q$$$ queries from the control room. For each query $$$(l, r, k)$$$, determine if the chant from the fans between $$$l$$$ and $$$r$$$ (inclusive) qualifies for the Tier $$$k$$$ broadcast (i.e., is divisible by $$$10^k$$$).

Touhemi is interested in betting, specifically in Scratch Expressions.

Touhemi buys a card that reveals, when scratched, a hidden string of length $$$n$$$, generated uniformly at random from the alphabet $$$$$$ \Sigma =\{(,),+,-,*,0,1,2,3,4,5,6,7,8,9\}. $$$$$$

The string is interpreted as an arithmetic expression under the standard rules described below.

He only has to scratch the card and hope that this is a winning card. Each generated string belongs to exactly one of the following categories:

• Winner: the string is a valid expression and evaluates to $$$0$$$ (after applying modulo $$$m$$$).
• Loser: the string is an invalid expression, or if it evaluates to $$$k\neq 0$$$ (after applying modulo $$$m$$$)

A string is a valid arithmetic expression if and only if:

• It consists of digits 0-9, binary operators +, -, *, and parentheses().
• Parentheses are balanced and properly nested.
• All operators are binary.
• Each digit represents a single non-negative integer.
• The entire string forms exactly one expression.

Valid Arithmetic Expressions are defined using the following recursive rules:

• An expression is either:
  1. A sum, difference or product of two sub-expressions
  2. A sub-expression, grouped by paranthesis
  3. A number. Note that leading zeros are allowed
• A Number is a sequence of digits
• A Digit is a character in $$$\{0,1,2,3,4,5,6,7,8,9\}$$$

Any string that does not satisfy these rules is considered invalid.

The valid arithmetic expression is evaluated using standard arithmetic semantics (Detailed in Notes).

Any strings of length $$$n$$$ is generated uniformly at random from the alphabet $$$\Sigma =\{(,),+,-,*,0,1,2,3,4,5,6,7,8,9\}.$$$

Your task is to compute, for each given length $$$n$$$, the probability that Touhemi obtains a Winner card.

You are given an array $$$A$$$ of size $$$N$$$. You need to process $$$Q$$$ queries of two types:

• Query: Given an integer $$$x$$$, return the number of elements in the array that are equal to $$$x$$$.

• Update query: Given an integer $$$x$$$, for every index $$$i$$$ such that $$$A_i \gt x$$$, update the value as: $$$A_i = A_i - x$$$

Miss Amina is organizing an excursion for primary school students to The Lake of Ichkeul, well-known locally as Bouhayret Echkel. She's managing the payment queue where students come to settle their trip fees.

The payment system works as follows:

• Each student in the queue has a payment balance (in dinars).
• Positive values represent payments made by the student.
• Negative values represent refunds, scholarships, or discounts applied to the student.

• Front: Priority students (e.g., class representatives, students with urgent matters).
• Back: Regular arrivals.

Students may also leave the queue in groups from either end (called away for verification, already processed, etc.).

Miss Amina frequently needs to calculate the net payment for specific sections of the queue. This is crucial for:

• Verifying which bus groups have fully paid their share.
• Checking if a specific segment has a deficit that needs attention.

Your task is to help Miss Amina by simulating the queue operations and answering her payment queries.

Deep inside the ancient Medina of Tunis, among the narrow alleys and whitewashed walls, a respected calligrapher and scholar left behind a mysterious parchment before disappearing during troubled times.

The parchment was discovered in a small shop near the souks. It contains an encrypted message written in lowercase English characters. The message was protected using a Caesar cipher, yet the shift number used to encrypt it is unknown.

Luckily, an old hakim (wise man) from the Medina provides a clue: he is certain that the original message contained at least one word from a given list of important Tunisian words — words such as "carthage", "zitouna", "jasmine", "kasba", or "medina".

A Caesar cipher shifts each letter in the alphabet forward by a fixed number of positions $$$k$$$ ($$$0 \le k \le 25$$$). The shift wraps around at the end of the alphabet. For example, with a shift of $$$1$$$, 'a' becomes 'b', 'b' becomes 'c', and 'z' becomes 'a'.

Your task is to determine the shift number $$$k$$$ that was used to encrypt the message.

In the first example, shifting the original words "treasure" and "madina" forward by $$$k=5$$$ results in the encrypted words "ywjfxzwj" and "rfinsf".

You are in charge of an autonomous delivery drone navigating a futuristic smart city.

The city is represented as a directed weighted graph. Each hub is a node, and each aerial flight path is a one-way connection with a given energy cost.

Some hubs contain delivery packages.

The drone starts at hub $$$U$$$, and its mission is to:

1. Take off from hub $$$U$$$.
2. Collect exactly five packages.
3. Return to hub $$$U$$$.
4. Minimize the total energy cost.

The drone may revisit hubs and reuse flight paths multiple times.

If the drone visits a hub that contains a package, it is not required to collect it.

There are at most $$$35$$$ hubs in the city that contain packages.

Your task is to determine the minimum total energy cost required to complete the route:

If no such route exists, output $$$-1$$$.

You have a number $$$x$$$, initially equal to $$$S$$$.

There are $$$N$$$ types of operations available. Each operation $$$i$$$ is described by:

- a range $$$[l_i, r_i]$$$

- an integer $$$d_i$$$

An operation $$$i$$$ can be applied only if the current value of $$$x$$$ satisfies $$$l_i \le x \le r_i$$$.

When applied, the operation reduces $$$x$$$ by exactly $$$d_i$$$: $$$x := x - d_i$$$.

You may apply any operation any number of times, as long as its condition is satisfied at the moment of application. Each application counts as one step.

Your goal is to reduce $$$x$$$ to exactly $$$0$$$ using the minimum number of steps.

If there are multiple sequences of operations that achieve this using the minimum number of steps, output the lexicographically smallest sequence of applied $$$d_i$$$ values.

If there is no solution your answer should be $$$-1$$$.

Ons Jabeur, the "Minister of Happiness" is training in Tunis for her next Grand Slam tournament. She believes that consistency is the key to winning the trophy.

Her coach has lined up N tennis balls, indexed from $$$1$$$ to $$$N$$$. The initial bounce rating of the $$$i-th$$$ ball is $$$A_i$$$ Ons wants to modify the ratings so that all balls eventually have the same value to ensure her practice is perfectly consistent. To modify the bounce ratings, she can perform a special technique. In one operation, she does the following:

1. She calculates the smallest non-negative integer that does not currently appear in the array of bounce ratings.
2. She chooses one ball at index $$$i$$$ ($$$1 \le i \le N$$$) and changes its bounce rating to that calculated value.

Help Ons determine if it is possible to make all bounce ratings equal. If it is possible, find the minimum number of operations $$$k$$$ and the sequence of indices $$$i_1, i_2, \dots, i_k$$$ to perform the operations.

If it is impossible to make all elements equal, output $$$-1$$$.