In the bustling Yuyuan Market, young Li wants to buy jianzhi (traditional paper cuttings) from an artisan. The pieces are aligned in a row, each with a unique symbol, and Li can only purchase them in identical pairs following these rules:

• If Li chooses a jianzhi at position $$$i$$$, he must immediately buy its pair at a position $$$j \gt i$$$.
• After selecting a jianzhi, he cannot go back to buy an earlier one.

The price Li pays is the sum of the distances $$$j - i$$$ between all purchased pairs. Li wants to buy the maximum number of possible pairs in a single pass. Moreover, among all ways to achieve the maximum number of pairs, he wants to pay the minimum possible price. Help Li optimize his purchase.

Ying is a gaming fan and is developing a new RPG. In this game, each player starts with a character that has $$$0$$$ attack points and $$$0$$$ defense points. To customize their character, players can use power-ups.

The game will have $$$N$$$ power-ups, and each one can only be used once. Each power-up is defined by a pair of integers $$$(a, d)$$$, which modifies the attack and defense points. If a player with $$$A$$$ attack and $$$D$$$ defense chooses a power-up $$$(a, d)$$$, their character's new attributes will be $$$A+a$$$ attack and $$$D+d$$$ defense. Note that the values $$$a$$$ and $$$d$$$ can be negative, which means the final attack and defense attributes can also become negative.

The game developers say that a character is "balanced" if its final attack points, $$$A$$$, are in the interval $$$[A_1, A_2]$$$ and its final defense points, $$$D$$$, are in the interval $$$[D_1, D_2]$$$.

Ying wants to know in how many ways a player can obtain a balanced character. A "way" is defined by a distinct set of power-ups. Two sets are distinct if one contains a power-up that the other does not. The order in which the power-ups are applied does not matter.

After a mission between Shanghai and Tianjin, the spy Lian returns to his hidden base in the alleys of Shanghai. There, he receives a new assignment: to become the Guardian of the legendary Jade Library, concealed in the Longmen Valley.

The library holds $$$N$$$ scrolls, numbered from $$$1$$$ to $$$N$$$, each containing a string composed only of lowercase English letters. According to the court magicians, certain palindromic substrings hidden in these texts encode ancient instructions and magical secrets. Preserving the library means correctly identifying where and how many of these palindromes exist.

Lian must therefore answer $$$Q$$$ real-time queries. Each query defines an interval $$$[L, R]$$$ of scrolls and asks for the number of distinct palindromic substrings (of length $$$\geq 1$$$) that occur in at least one of the texts within that interval. Any incorrect response may trigger traps left by the library's ancient protectors.

These queries are made in real time and expect an immediate response.

Note: A palindrome is a sequence of letters that reads the same from left to right and from right to left. Examples: a, aa, aba, abba. Only palindromic substrings (i.e., contiguous segments) are considered.

After his last mission, Lian, the spy, returns to Shanghai. In an ancient stone chest, he finds a sequence of numbers that protect an ancestral secret: the Seals of Shanghai.

To unlock the seals, Lian must follow a precise ritual. Initially, he chooses a fixed integer $$$M$$$ such that $$$1 \lt M \leq 10^9$$$. Then, he must perform a sequence of magical rounds. In each round, he chooses an integer $$$x$$$ with which he unlocks all the seals whose number $$$A_i$$$ satisfies $$$A_i \bmod M = x$$$.

Each round requires concentration and energy. Therefore, Lian wants to minimize the number of rounds to unlock all the seals. Additionally, he wants to know how many distinct values of $$$M$$$ allow him to achieve this minimum number of rounds.

In the city of Shanghai, the young programmer Kai seeks the wisdom of his mentor, Master Wei. One day, Master Wei presented Kai with a challenge on algorithm analysis, a fundamental lesson to achieve mastery.

"Little Kai," said the Master, "a programmer's strength lies not in writing code, but in understanding it deeply. Observe this scroll. It describes the 'Wise Partitioning Method', a way of sorting sequences."

On the scroll was an algorithm, which coincidentally looks very much like an implementation of Quicksort in Python:

cmps = 0
def quicksort(A, l, r):
    if r <= l:
        return
    # The Master chooses the middle element as a guide
    m = (l + r) // 2
    k = pivot(A, l, r, A[m])
    quicksort(A, l, k - 1)
    quicksort(A, k + 1, r)


def pivot(A, l, r, x):
    # Each element is compared with the guide x
    for y in A[l : r + 1]:
        cmps += 1
        if y < x:
            A[l] = y
            l += 1
        elif y > x:
            A[r] = y
            r -= 1
    A[l] = x
    return l

The function $$$pivot(A,l,r,x)$$$ rearranges the values in the segment $$$A[l..r]$$$ as follows: values smaller than $$$x$$$ are moved to $$$A[l..k-1]$$$ (in the same relative order), values larger than $$$x$$$ are moved to $$$A[k+1..r]$$$ (in the reverse relative order), and the guide value $$$x$$$ is placed at $$$A[k]$$$.

Master Wei then handed Kai a sequence of numbers representing the energy levels of a sleeping dragon. "A hasty apprentice would try to run this code to get the answer. But a true master can predict the cost without executing a single line."

"Your task, Kai," the Master concluded, "is to tell me the exact cost of the method for this sequence. Calculate the final value of the cost variable $$$cmps$$$ that would be obtained at the end of the $$$quicksort(A, 0, n-1)$$$ call. This is your lesson for today."

China has been unified, ending the Warring States Period and ushering in an era of innovations, such as teleportation. To connect the empire, the emperor has installed teleporters in various cities.

The empire consists of $$$n$$$ cities connected by $$$m$$$ roads, such that it is always possible to travel between any two cities using only these roads. Each road allows for bidirectional traffic and has a fixed travel cost.

Additionally, there are $$$k$$$ different types of teleporters. Two cities can connect instantly via teleportation only if both have a teleporter of the same type. However, the cost of using a teleporter depends on the city of origin, as each mayor sets the fee to be paid for leaving the city using the magical device. That is, even for the same type of teleporter, the usage cost can vary between cities.

The Japanese traveler Mori, upon arriving in China, does not understand its complex structure and is unable to determine the best routes for travel. He wishes to travel from city $$$1$$$ to city $$$n$$$. What is the minimum possible cost to make this journey, considering both the available roads and teleporters?

In the heart of the Forbidden City, the Emperor has ordered the performance of the great "Celestial Dance" to ensure the harmony of the empire. A sequence of dancers, representing the primordial forces, is positioned in a line. Yang dancers (represented by '(') and Yin dancers (represented by ')') form a sequence.

For the grand finale of the dance, each Yang dancer must be paired with a Yin dancer who is positioned further down the line. The beauty of this ancestral dance lies in its complexity: the paths of the pairs can cross, symbolizing the intertwined threads of fate. Therefore, multiple choreographies are possible, with different ways to pair Yin and Yang dancers. It is guaranteed that there always exists a valid choreography.

However, the imperial astrologers have warned that certain pairs are "incompatible". An incompatible pair is a specific Yang dancer and Yin dancer who, if paired together, make it impossible for all the other dancers to find a partner, thus breaking the cosmic harmony of the ritual.

For example, in the formation (()), any pair that is formed (such as the 1st with the 3rd, or the 1st with the 4th) always allows the remaining dancers to form a valid pair. Therefore, for (()), there are no incompatible pairs. However, in the formation ()(), if we try to pair the 1st dancer (Yang) with the 4th dancer (Yin), the remaining dancers are the 2nd (Yin) and the 3rd (Yang). Since the remaining Yin dancer comes before the Yang dancer, they cannot form a pair. Thus, the pair (1, 4) is incompatible.

Your task, as the Imperial Master Choreographer, is to analyze the initial formation of the dancers and determine the total number of incompatible pairs, so they can be avoided in the ceremony.

In the ancient and majestic city of Shanghai, future stage of the ICPC World Finals, a young programmer named Kai dreams of achieving the mastery of his mentor, the legendary Master Wei.

One day, while debugging complex code at the Wild Goose Pagoda, Kai asked, "Master, your experience is as vast as the Yellow River. When will my programming journey be exactly half of yours?"

Master Wei, with an enigmatic smile, replied: "Little grasshopper, experience is measured by years of practice. I started programming in year $$$W$$$, and you started in year $$$K$$$. There will come an exact year when my years of practice will be double yours. Find that year, and you will find the clarity you seek."

Help Kai solve his master's riddle.

In the turbulent times of the Warring States, the renowned warrior Na Tan and his companions traveled to participate in a martial arts tournament. They are all staying in the same room, and before the competition, Na Tan decides to go to the baths to clear his mind. However, upon finishing, he realizes that he made a mistake: he forgot to grab the towel!

Fortunately, the room is empty at the moment, but his companions may return at any moment. Na Tan, determined not to be seen in an embarrassing situation, needs to leave the bath, grab the towel, and return as quickly as possible, without being caught.

The room can be represented by a simple polygon (that is, a polygon whose sides do not cross), and Na Tan's path must occur entirely within this polygon. The door of the bath is located at one of the vertices of the polygon, while the towel is at some point inside the polygon, but not necessarily at a vertex. Na Tan moves at a constant speed of 1 unit per second.

Given this, what is the minimum time required for Na Tan to fetch the towel and return to the bath?

In the Warring States period of ancient China, espionage was the key to survival. An agent named Lian has received a critical mission: to deliver a message from his base in Shanghai (represented on the map by vertex $$$S$$$) to an allied general in the walled city of Tianjin (vertex $$$T$$$).

Lian's spymaster warned him: "Our enemies are cunning. They know all the roads and expect an urgent messenger to use the fastest possible path. If you arrive from Shanghai to Tianjin in record time, your identity will be revealed."

The order was clear: calculate the shortest path length, $$$D$$$, but do not use it. Instead, to pass as a common merchant who might have taken a detour, you must follow a path of length exactly $$$D+1$$$.

To have flexibility and escape routes, Lian needs to know how many travel options meet this condition. Your task is to help him count the number of distinct paths from Shanghai to Tianjin with a length of precisely one more than the minimum.

Agent Wang is a very reserved person and prefers not to share his birthday. However, the MaratonUSP trio managed to find out when his birthday is!

To celebrate, the trio decided to bake a cake from scratch. The responsibility for the recipe fell to Antonio, the trio's cook — but there's a problem: Antonio does not like cakes.

After some investigation, Antonio discovered which cake ingredients he doesn't like and decided simply not to use them in the preparation, even if it compromises the result. The cake recipe is divided into several steps, and each step uses a list of ingredients. The cake will become bad if, in any step, more than one third of the ingredients of of the step are missing.

What is the first step in which the cake becomes bad, if any?

Given a board of size $$$N \times N$$$, where each cell can be alive, dead, or uninhabitable, simulate the evolution of the board for $$$K$$$ iterations based on the following rules:

$$$\bullet$$$ A live cell ($$$\texttt{'1'}$$$) dies if it has an odd number of live neighbors.

$$$\bullet$$$ A dead cell ($$$\texttt{'0'}$$$) becomes alive if it has an odd number of live neighbors.

$$$\bullet$$$ An uninhabitable cell ($$$\texttt{'#'}$$$) never changes state and is never considered alive.

Each cell has up to 8 neighbors (horizontal, vertical, and diagonal).

Your goal is to determine the final state of the board after $$$K$$$ iterations.

Due to the high rent prices in Shanghai, Kai, of the Yafa clan, has become homeless. Fortunately, he has already found a new place! However, he will need to wait for exactly $$$D$$$ days until he can move in.

In the meantime, he has evaluated his options and found $$$N$$$ places, represented by indices from $$$1$$$ to $$$N$$$, where he can spend the night. Each place, however, has a tolerance limit: after a certain number of consecutive days, Kai will be kicked out.

For each of the $$$N$$$ places, an integer $$$d_i$$$ has been determined, representing the maximum number of consecutive days he can sleep at the $$$i$$$-th location before being expelled. It is possible that $$$d_i = 0$$$; in this case, it means Kai cannot spend even a single night at that location.

Your goal is to create an accommodation plan for Kai to get through the $$$D$$$ days by alternating between these places, without exceeding the consecutive day limit of any of them. Kai can return to a place later, as long as each new consecutive stay respects the limit.

Write a program that determines if it is possible to create such a plan. If so, produce a sequence of places (indices from $$$1$$$ to $$$N$$$), indicating where Kai should sleep on each of the $$$D$$$ days. Otherwise, print $$$-1$$$.