The Institute of Geography and Territorial Organization of the University of Lisbon (IGOT, in Portuguese), is conducting research projects at Pico Island. One of the research projects concerns the level curves of Mount Pico, the highest mountain in Portugal. Using image processing software, the researchers transform such curves into simple polygons (that do not self intersect).

To understand how the terrain changes with respect to height, IGOT is interested in the monotonicity of a level curve with respect to a set of directions (vectors). Given a vector $$$v$$$, we say that a simple polygon is $$$v$$$-monotone if any non-empty intersection of a straight line orthogonal to $$$v$$$ with the polygon is a segment (or a single point). You are one of the IGOT developers and they entrusted you with the following task. Given a simple polygon and a set of vectors, determine for each vector if the polygon is monotone with respect to this vector.

One of the greatest poets in Portuguese language was Luiz Vaz de Camões, born in Lisbon circa 1524. Camões works are fundamental reading for high school students in countries such as Brazil or Portugal. Many consider his 5- and 7-syllable poems and his sonnets (with 14 verses) to be the most important lyrical work in Portuguese of all time.

Camões was a visionary in his own time. His work has been studied from many aspects: historical, cultural, symbolical, and so on. Carlitos "the efficient" Nunes is studying aesthetics in Camões' poetry. He is especially interested in a metric based on the size of the verses of a poem. We define this metric as follows. Suppose we have a poem made of $$$N$$$ verses. We say that the poem is $$$K$$$-elegant if $$$K \gt 1$$$, $$$N$$$ is a multiple of $$$K$$$ and, moreover, there are exactly $$$N/K$$$ verses whose sizes, when divided by $$$K$$$, have remainders equal to $$$i$$$, for $$$i=0,1, \ldots, K-1$$$. Note that a single poem may be $$$K$$$-elegant for several distinct values of $$$K$$$.

Carlitos already processed the data from poems by Camões and now he needs your help to determine the smallest elegance in each of the poems.

The city of Porto will host the ICPC World Finals in 2019. One of the secret touristic spots in the city is the so-called "lake of the thousand bridges". Mr. Manoel Pontes (Pontes stands for "bridges" in Portuguese; this is amazingly his real name$$$\ldots$$$) built this wonder in the lake with a lifetime of hard work. The lake has many small islands. Mr. Manoel built small wooden bridges connecting the islands. In some cases, there are multiple bridges connecting some pairs of islands. Visitors enjoy themselves while promenading through the bridges and small islands. Besides, by walking through the bridges the visitors can go from one island to any other island.

Mr. Manoel wants to enhance this touristic attraction to get even more visitors. One of this ideas is to organize visitors games. He plans to have the following challenge: is it possible to start to walk from outside the lake, pass through all the bridges without repetition, and go back to the starting point (that is, back out of the lake)?

Before creating the attraction, he himself tried it over and over but could not find out if this was possible. To make the challenge even more interesting, Mr. Manoel will allow adding some bridges between some islands. He wants to know if, by adding some of these bridges, the walk he wants the game to have becomes possible. Your task in this problem is to decide if it is possible to choose some (possibly none) of these bridges that, when added, allow people to walk as described.

In Portugal there are very popular political parties, the Social Democrat Party (PSD, in Portuguese) and the Socialist Party (PS, in Portuguese). There will be presidential elections in Portugal in 2019 and the political parties are working on the best way to run advertising campaigns to reach the maximum number of voters.

Due to the high cost of elections advertising, PSD and PS wish to broker a deal and split the costs of advertising. The people in charge of the negotiation have data about political preference of some people in Portugal. They have been processing this information and have thus obtained the geographical position of people that are likely voters for PSD and PS. This position is represented by a point in the plane. To calculate the expenses, they wish to find two disjoint areas that, when summing likely voters for these parties, the result is the largest possible. To facilitate the computations, they decided to consider both areas to be rectangles with sides parallel to the axes. In other words, they wish to find two rectangles, one representing PSD and the other representing PS, such that the sum of the number of likely voters of PSD in the first rectangle and the number of the likely voters of PS in the second rectangle is maximum. You were hired to develop a software that fulfills this task.

Recent studies in Education show great pedagogical benefits of working in groups, especially in the freshman and sophomore years in high school. Different groups of various sizes are great and allow students to understand their differences and to train in teamwork. A teacher at a modern school wants to know how many different groups he can form in this class of $$$N$$$ students. The only requirement is that a group must have at least 2 students, and two groups are distinct if at least one student is in one of them and no in the other.

Your task in this problem is, given $$$N$$$, compute the number of distinct groups that is possible to create in the class.

The Ministry of Construction, Transportation and Communications of Portugal is planning to improve transit routes throughout the country. The ministry's main concern is the delay everyone suffers daily in traffic when some road gets blocked. A key part of the ministry's plan is to identify roads that harm people's commute time the most. Hence, they contacted the Institute of Efficient Mobility (IME, in Portuguese).

IME is developing a software that, when given a description of the transit routes in Portugal and their usage information, finds the routes that harm the population the most when blocked. The person in charge of this important project is Marcel "the optimizer" Saito. Marcel is currently busy with administrative tasks and organizing the workforce. He has faith in you and so he is entrusting you with designing the key part of the software. You must solve the following problem: given two locations in a city, say $$$s$$$ and $$$t$$$, one wants to find the worst delay incurred when a person travels from $$$s$$$ to $$$t$$$, when exactly one road in the city gets blocked. As a pragmatic choice, you may assume that people always choose a path that takes the least time to travel from one place to another.

The penitentiary at Viana do Castelo is one of the largest ones in Europe. The building has thousands of jail cells, laid out linearly in several levels, and numbered so that adjacent numbers are given to adjacent cells, be it adjacent cells on the same level, or one on top of the other, or connected by an adjacent stairway. It is not really known why, but the jail cells are numbered starting from a negative number, so that cell number zero is right in the middle of the penitentiary, exactly at the center of the middle level of the building. Probably the first warden, who assigned the cells numbering, did this for entertainment $$$\ldots$$$

Each guard in the penitentiary gets an interval of cells to watch. He must go over these cells and check that the inmates did not escape, are doing okay, and so on. The warden does two operations depending on the intervals of cells assigned to each guard:

1. Given a guard $$$i$$$, change the interval of cells assigned to him to $$$[\ell,r]$$$;
2. Given an interval of guards $$$[a,b]$$$, find how many cells are watched by all the guards in this interval at the moment.

Your task in this problem is to read the number $$$N$$$ of guards in the penitentiary and, for each guard, the interval of cells he is in charge of watching over. Next, you will read the $$$Q$$$ operations carried out by the warden, by executing an operation of the first type or by answering the query for operations of the second type.

Porto is known worldwide for its wine production. These wines are produced in the outskirts of the city and then aged in oak barrels to obtain their unique flavor. The wineries must follow strict production standards to get the seal of approval that helps with sales. To attain these very high standards, the temperatures at the vineyards are measured daily and must satisfy very specific requirements, according to studies by experts.

In order for a grape to reach optimum development, it is important to known how many different temperatures it faced during its growth and in how many days each of these temperatures were repeated. Recent studies show that the quality of the wine is deeply correlated with the following number. Consider the growth period for the grape and count, in those days, how many distinct temperatures we had, and for each temperature, how many times it was repeated in the period. We say that the grapevine has quality $$$x$$$ if we have at least $$$x$$$ distinct temperatures that were repeated in $$$x$$$ days during the growth of its grapes.

Your task is to compute the quality of production of each grapevine in the vineyard. You are given the temperatures measured in $$$N$$$ days in the vineyard. Next, for each one of the $$$Q$$$ grapevines in the vineyard, you are given the start and end days of their growth periods. For each one of these grapevines, you must compute the maximum quality of their production.

Tea is second most consumed beverage in the world after water, especially in the United Kingdom, where about $$$84$$$% of the population has tea every day. This British tradition with tea is a well known fact. What few people know is that English tea has its origins in Portugal. In 1662, when Catarina de Bragança married King Charles II of England, she traveled to London and took with her some tea leaves. The story goes that the boxes where these leaves were carried were labeled as "Transport of Aromatic Herbs", later abbreviated in Portuguese to TEA.

The historian Gaia "the Curious" Fontenelle is studying some old documents that describe how tea was transported from Portugal to England. Initially, $$$N$$$ boats were anchored in Portugal. Each boat was assigned a distinct integer between $$$1$$$ and $$$N$$$. The documents say that the tea was to be transported in a total of $$$K$$$ trips. These trips would use ports in Portugal, China and England. After many ruminations, Gaia reached these conclusions:

1. In each one of the $$$K$$$ trips only one boat would move between two ports. Moreover, this boat was the smallest numbered when considering the boats stationed in both ports.
2. The trips would take place one after the other, and there never were two boats traveling at the same time.
3. Boat $$$N$$$ would end its itinerary when it arrived in England. For $$$i \lt N$$$, boat $$$i$$$ would only end its itinerary when it arrived in England and the itinerary of boat $$$i+1$$$ had also ended.

Gaia quickly noticed that, with these rules, each port looks like a stack, where a trip corresponds to moving the smallest boat (in the top) of the origin stack to the destination stack (while satisfying constraint $$$1$$$). Gaia was used to dealing with imprecise or downright false sources of information, so she started playing in her notebooks and she realized that, depending on the values of $$$N$$$ and $$$K$$$, sometimes it was impossible to move all $$$N$$$ boats (even while using the port in China). For this reason, for each report about tea transport, she wants to find out whether it was possible or not.

Gaia got hungry and left for coffee, chocolate and taking pictures of the sunset. You are an intern in her team and wish to impress her (maybe you will get the job this way). Thus, you decided to solve the problem before she returns.

Altercations between Brazil and Portugal go a long way back. The most recent such skirmish happened in 2016 when these two countries had a "meme war". The journalist Fiorentina "sagacious" Azzellini is studying this event in her work of describing ways in which social networks have changed how people interact.

Brazil flooded the internet with a huge amount of memes, and won the contest in three days. Fiorentina, while investigating how such a huge amount of images could be created, found that some of them could be constructed very simply. The meme was made of an image that had the national flags of Brazil and Portugal, and one word. The word $$$S(x)$$$ was created from a letter $$$x$$$ and has the following composition:

where $$$p(x)$$$ is the letter that precedes $$$x$$$ in the alphabet and $$$A \cdot B$$$ denotes the concatenation of words $$$A$$$ and $$$B$$$. Fiorentina started playing with distinct letters and wrote in her notebook

Sagacious as she is, Fiorentina quickly noticed that the word $$$S($$$'z'$$$)$$$ is huge. Not willing to write it down in her notebook, but still curious about some of the letters in this word, she asked for you to help. She would like to know what the letter in the $$$n$$$th position of the word $$$S($$$'z'$$$)$$$ is.

Portuguese children's pastimes are very sophisticated. Some of them have very complex rules and their description can get even a grown up dumbfounded, but somehow the kids play with them and have lots of fun. One of them goes by the name of "spin-and-turn". In this game, one of the players writes down an ordering of the participants, and this ordering remains secret. Some other player then tries to guess this ordering with spin-and-turn moves. The idea is to apply several times the same permutation of the participants, starting from the ordering of the children by their ages. If at some point the secret permutation is found, the player wins. Otherwise, the kid who came up with the secret ordering wins.

Let's see an example. Imagine that the secret ordering is $$$(4, 2, 1, 3)$$$, that is, the oldest child comes first, next the second youngest, followed by the youngest child and then the third one. One of the players could play with the permutation $$$(3, 1, 4, 2)$$$. If we apply this permutation from the age ordering $$$(1, 2, 3, 4)$$$ we get $$$(3, 1, 4, 2)$$$. If we do this again on this ordering, we get $$$(4, 3, 2, 1)$$$. And then $$$(2, 4, 1, 3)$$$ and then we get back to the starting ordering $$$(1, 2, 3, 4)$$$. So this player has lost, and the player that chose the secret ordering won. In the game, the kids keep moving, spinning and turning, hence the name$$$\ldots$$$

This very sophisticated game intrigued a famous Portuguese mathematician who decided to study it. Your task in this problem is to help this mathematician. Given a secret ordering $$$p$$$ of the players, we want to find how many permutations $$$q$$$ may result in $$$p$$$ when applied a finite number $$$k \geq 0$$$ of times, as in the example above.