Marcio "the indispensable" Himura is back in action. This time, he is investigating the administration of the Ancient Egypt during the reign of pharaoh Thutmose III. The organization Extraordinary Mystery Investigators (IME, in their language) has discovered ancient papyruses related to the Egyptian army. Thutmose was known for making his army march so often at regular intervals, that having local governors was unnecessary.

These papyruses have information regarding the construction of some buildings. In particular, they have the starting and finishing dates of the construction of each building. The ancient tales say that Thutmose chose certain days to march along with his army to supervise the construction of these buildings. In one day, they visited all the buildings that were under construction. A building was considered under construction since its starting date until its finishing date.

Marcio is studying how Thutmose III scheduled the marching days with his army. Regarding this schedule, Marcio has the following information. Since Thutmose was a careful person, he knows that each building was visited at least once. On the other hand, visiting a building many times intimidated the persons in charge of the construction. Therefore, the schedule of the army was planned in such a way to minimize the maximum number of days a single building is visited.

As a first step in his investigation, Marcio wants to find one such schedule. As Marcio is rusty after a two-year break, he needs your help in this task.

The city of Sharm el-Sheikh is full due to the ICPC World Finals, the largest event in the world. One of University of São Paulo competitors, Lucas _Lucas3h_ Harada, is on the city center buying souvenirs. Unfortunately, for him and the for rest of his team, the streats are jammed with traffic, and, guess what, the World Finals will take place today!

But fear no more, because the organizers thought about everything. The ICPC Committee hired Tuk-Tuks to take the competitors from the city center to the hotel.

They hired three companies to do the job. As one should expect of an event of this importance, there is an infinity number of Tuk-Tuks of each company, and one arrives immediately after one leaves. The Tuk-Tuks of each company take $$$t_1$$$, $$$t_2$$$, and $$$t_3$$$ minutes respectively to go from the city center to the hotel. Besides that, each one can carry up to $$$C$$$ passengers. Each Tuk-Tuk laves the city center when at least one of the following conditions is fulfilled

1. $$$C$$$ passengers have boarded;
2. $$$X$$$ minutes have passed after the boarding started.

The second rule exists to avoid some competitors waiting for too long. Notice that this implies that one Tuk-Tuk may even make a trip with no passengers! Also notice that each company has it's own separated service.

The world finals will start in $$$T$$$ minutes, and right now, at time zero, there is one Tuk-Tuk of each company leaving the city center. You may assume that each one of these Tuk-Tuks reaches the hotel in time to the competition.

Lucas needs your help, he wants to know what is the maximum amount of time he can spent at the city center without getting late to the World Finals! For some unknown reason he knows that there $$$N$$$ competitors at the city center and each of them will embark in a Tuk-Tuk of company $$$c_i$$$ at time $$$d_i$$$, and he sent this list to you.

You may assume that, if Lucas arrive at the same time as any other competitor, he will board before them.

The Book of the Dead is a collection of Ancient Egypt's texts that was used to cast spells which purpose was to assist a dead person's journey through the Duat and into the afterlife.

The book contains magic words, each of them with a certain level of magic power. To cast a spell, one must say a sequence of magic words in which every said word (but the first one) is such that the previous one is a proper prefix of the latter. For instance, the sequence of magic words nefer neferti nefertiti is a spell, whereas ra ramses ramesses and amun amun amunra aren't. The magic power of a spell is the sum of magic powers of each of the magic words in it.

Given the list of the Book of the Dead's magic words, answer what is the maximum power of a spell that can be cast using only the magic words in that list.

In the decade of the 2010s, Egypt went through a very high inflation period. This made the price of all local goods to radically increase, so radically that it stopped being feasible for the prices to be written as 64 bit integers, as it was done before. The sellers, not wanting to stop selling their items, had to use their creativity to find a way to write their products prices.

Let $$$a$$$ be an array of $$$n$$$ distinct primes $$$a_1 \dots a_n$$$. We define $$$P$$$ as the product of these primes. Thus:

$$$$$$P = \prod_{i=1}^{n} a_i.$$$$$$

The array $$$b$$$ of prices of the $$$n$$$ items in the store is defined as $$$b_i = P/a_i$$$, in which $$$b_i$$$ is the price of the $$$i$$$-th item in Egyptian Pounds.

Sara is a competitive programmer, and so she gets many prized in American Dollars. With a nice exchange rate, she now holds great wealth. She has some amount $$$d$$$ of Egyptian Pounds, that can be written as the product of $$$m$$$ not necessarily distinct primes $$$c_i$$$. Thus:

$$$$$$\displaystyle d = \prod_{i=1}^{m} c_i.$$$$$$

Since Sara plans to study abroad, she would like to spend all of her pounds. She asked for your self to determine wether it is possible to buy some of the $$$n$$$ itens in such a way as to spend all the money she has: $$$d$$$ pounds. Since the crisis affected the shops, only one of each product is available.

One of pharaoh Hatshepsut's greatest pride was her gardens. Right next to her palace there was a beautiful sequence of fig trees. The trees are numbered from $$$1$$$ to $$$n$$$ and the $$$i$$$-th tree has $$$a_i$$$ figs.

Fig trees are very peculiar, and react in an interesting way when they are shaken. If someone shakes a fig tree with $$$x$$$ figs, after this $$$\phi(x)$$$ figs remain, where $$$\phi(x)$$$ counts the positive integers up to $$$x$$$ that is relatively prime to $$$x$$$. Following is the value of $$$\phi$$$ for integers from 1 to 10 is $$$\{1,1,2,2,4,2,6,4,6,4\}$$$.

The pharaoh is constantly dissatisfied with her fig garden and demands her servants to do some changes to it. In total, she may demand three types of operations

• 1 L R: for $$$i$$$ from $$$L$$$ to $$$R$$$ (inclusive) shake the $$$i$$$-th fig tree (changing $$$a_i$$$ to $$$\phi(a_i)$$$).
• 2 L R x: for $$$i$$$ from $$$L$$$ to $$$R$$$ (inclusive) change the $$$i$$$-th fig tree to one with $$$x$$$ figs (changing $$$a_i$$$ to $$$x$$$).
• 3 L R: print the sum of $$$a_i$$$ for $$$i$$$ from $$$L$$$ to $$$R$$$ (inclusive).

The great gardener of Hatshepsut gets lost with so many orders! She asks for your help, given a list of Hatshepsut's orders print the answer for every order of type 3.

After years searching, Indiana Jiang's journey is reaching it's end. Right now, he is venturing into the most secret tomb in Egypt. However, Jiang didn't expected that his last challenge would be to solve the Sphinx's riddle! In the treasure chamber, at the feet of the sphinx, there is a chest, containing the artifacts Jiang has been searching for. Sphinxes are known to be treacherous, if Jiang doesn't win the challenge he may never leave the tomb.

The riddle goes like this. Initially, $$$N$$$ spheres numbered from one to $$$N$$$ are arranged in order. There are two mummies in the room, one with white stripes and one with black stripes, which will alternately take spheres until only one remains. The one with white stripes goes through the spheres from left to right, taking the balls alternately, that is, removing the second, fourth, sixth, etc.. After that, the mummy with black stripes goes through the sequence from right to left, also removing the spheres alternately, that is, remove the penultimate one and so on. As an example, consider that initially there are $$$7$$$ spheres. $$$$$$1\quad 2\quad 3\quad 4\quad 5\quad 6\quad 7$$$$$$ After the passage of the mummy with white stripes remains $$$$$$1\quad 3\quad 5\quad 7$$$$$$ After the passage of the mummy with black stripes remains $$$$$$3\quad 7$$$$$$ After the passage of the mummy with white stripes remains $$$$$$3$$$$$$ The result of the Sphinx's riddle is the number of the remaining sphere. So for $$$N = 7$$$ the answer is $$$3$$$.

The sphinx tells Jiang a number $$$N$$$ and wants to know the answer to the riddle. Jiang, who is not an amateur, has been communicating with you by radio the whole time. However, he doesn't have much time, help Jiang to solve the sphinx's riddle.

Egyptian names can be confusing sometimes. For instance, in a classroom, we may have students named Mohamed, Muhammad, Mohammed, Mohammad and Mohamad. While any of them is upset when people write his name wrong, no one suffers more than Mmoohhaammeedd.

Cursed by his parents that wanted a special name for him, Mmoohhaammeedd was bullied by his classmates throughout his life. Now, he asks your help to, finally, plan his revenge.

Mmoohhaammeedd got the attendance list of his school. Now, he will make a new one, changing the name of each of his classmates in the following way: Mmoohhaammeedd will duplicate each letter whose neighboring letters are different from it. In this way, "eman" turns into "eemmaann", "hasssan" turns into "hhaasssaann", "alaa" turns into "aallaa" and "mmoohhaammeedd" remains the same.

Given the name of one of Mmoohhaammeedd's classmates, print how he should write it in the attendance list.

Ahmed lived his entire live in Egypt, and since he was a kid one of his only missions was to keep the secrets of the the tomb of Tutankhamun and going to the ICPC World Finals. Unfortunately, while he was outside the Valley of the Kings for a competition, the great archeologist Mohamed visited the tomb, and, without Ahmed to stop him, found a secret room with never-before-seen paintings about different periods in Egyptian history.

Ahmed realised that he can use this opportunity to share knowledge about the history of Egypt, but he will have to be careful to do so without leaking too many secrets.

To study the $$$n$$$ paintings that were found, Mohamed will send $$$n$$$ historians. He gave Ahmed a list of $$$m$$$ triples $$$(h_i,p_i,c_i)$$$, indicating that the historian $$$h_i$$$ knows the period represented in the painting $$$p_i$$$ with a knowledge level of $$$c_i$$$. This level may be $$$0$$$, indicating a weak knowledge, or $$$1$$$, indicating a strong knowledge. If, for some $$$h_i$$$ and $$$p_i$$$, no triple $$$(h_i,p_i,c_i)$$$ is in the list, $$$h_i$$$ does not know the period $$$p_i$$$. It is guaranteed that for any $$$h_i$$$ and $$$p_i$$$, at most one triple $$$(h_i,p_i,c_i)$$$ is in the list.

Ahmed will choose paintings for the historians to study, and he will do so in such a way that at each historian studies at most one painting and at most one historian studies each painting. A historian can only study a painting if they know the period in it.

Ahmed knows that only a strong knowledge on the period of a painting will bring on new knowledge about Egypt, so he will be happy with his own choice if and only if exactly $$$k$$$ historians have strong knowledge on the period of the painting they are studying.

Mohamed knows that, given the list of triples, regardless of how Ahmed makes his choice, at most $$$E$$$ historians will study some paintings. He calls all choices in which exactly $$$E$$$ historians study some painting of maximum choices.

To keep Ahmed happy, he guarantees that there is at least one maximum choice in which at most $$$k$$$ historians have strong knowledge on the period on the painting they are studying, and there is at least one maximum choice in which at least $$$k$$$ historians have strong knowledge on the period on the painting they are studying.

Since Mohamed does not trust Ahmed's skills very much, he will be happy either with a maximum choice, or an almost-maximum choice, i.e., a choice in which $$$E-1$$$ historians know the period represented in the painting they are studying.

Ahmed now comes to ask for your help to find a maximum, or almost-maximum choice, in which exactly $$$k$$$ historians have a strong knowledge of the period of the painting they are studying. It is guaranteed that such choice exists.

Thiago is a poor farmer of the small village Khaldas, in ancient Egypt. Like it was common at that time, he needs to make an offering to Sun's god Rárada, also known as Ra. He needs to offer part of his harvest to show his gratefulness.

For this, Thiago will use baskets with capacity of $$$A$$$ grams of food. The total quantity of food must respect the following rules, as to not make Rá angry:

1. All of the baskets must be full, so that Ra doesn't think Thiago is offering less food than he could
2. Since Ra loves the number $$$B$$$, the total quantity of food (in grams) in decimal base must begin with the number $$$B$$$. For example, if $$$B=471$$$, the number $$$4715166$$$ accomplishes this rule, since $$$471$$$ is in its most significant digits.

Help Thiago to find some quantity of food (in grams) that he must offer to god Rá. Notice that this quantity must be less than $$$10^{18}$$$ that is the productive capacity of this poor farmer.

One of the main tasks of the pharaohs of the Egyptian Empire was mantaining the Maat, the order and balance, in the civilization. The great pharaoh Ramesses II did that very well. He built paths between Egypt's cities such that it were possible to travel between cities following a sequence of these paths. Therefore, for several years, the order reigned in the empire.

However, Ramesses was aware that this was not to the liking of Apep, the Lord of Chaos, a giant snake which purpose was to break Maat. In order to destroy Egypt's balance, Apep pretends to attack one path such that it would be no longer possible to travel between any pair of cities.

Every path has a strength level that depends, among other things, of the material with which it was built. Hence, the order level of Egypt is equal to the lower strength level among the paths that, if attacked, it would no longer be possible traveling between every pair of cities. If there isn't such path, we say that Egypt is in balance.

Luckily, Ramesses has a plan to prevent that Apep succeeds breaking the empire's Maat. This plan consists in adding new paths in order to raise the order level. The pharaoh wants to know the level of order after adding each of these paths and, hence, he needs your help.

Egypt's railway system is one of the oldest in the world and is one of the most used transport modals in the country. Due to this tradition, some cities organize themselves completely along the train lines. Consider a railway as a straight line that extends from point zero to $$$10^9$$$ meters, and a city is organized along this train line.

There are $$$N$$$ inhabitants in this city who need to go to work. The $$$i$$$-th inhabitant lives at point $$$X_i$$$ (meters from point zero), works at point $$$Y_i$$$, different from where they live, and their shift starts at time $$$T_i$$$ seconds.

At zero time, all citizens leave home to work. Citizens walk at a speed of 1 meter per second. As the bosses in Egypt are very strict, if an employee is late by any epsilon, they will be fined $$$V_i$$$ Egyptian pounds.

At time zero, a train leaves point zero and travels through the city at $$$B$$$ meters per second. This train stops at every integer point. The time it takes to board and disembark passengers is negligible.

A train ticket costs $$$P$$$ Egyptian pounds.

It is well known that if a person walks to work and is not fined, they will not pay for the ticket. It is also known that a person will never be willing to lose more money than they need to, hence if going by train avoids the fine, the person will pay for the ticket only if its cost does not exceed the fine.

ENR (Egyptian National Railways) is looking to maximize the company's profit (the sum of fares paid). Given a list of $$$N$$$ residents with the above information, determine the value of $$$P$$$ that maximizes the company's profit. If multiple answers maximize profit, print the cheapest one.

After a semester of hard work, Cris took some days off and decided to spend them in Cairo, Egypt. The money she took there is all in Brazilian reals and US dollars, hence she usually has to do exchange operations between Egyptian pounds and these currencies.

The exchange operations that Cris does can be described by an integer $$$X$$$. If $$$X \gt 0$$$, she sells $$$X$$$ (dollar or real) coins for Egyptian pounds. If $$$X \lt 0$$$, she buys $$$X$$$ (real or dollar) coins using Egyptian pounds. If $$$X = 0$$$, she does nothing. We call profit the result of the exchange operation in Egyptian pounds. Notice that, when the exchange operation is buying (dollar or real) coins, the profit is a negative value.

Cris got access to the exchange values of the next $$$n$$$ days of a currency exchange house in Alexandria. In the $$$i$$$-th day, the dollar value in Egyptian pounds is $$$d_i$$$ and the Brazilian real value in Egyptian pounds is $$$r_i$$$. In this currency exchange house, the exchange value is the same for selling and buying Egyptian pounds. This is, if in a given day the Brazilian real value is 5 Egyptian pounds, then it's possible to sell 10 reals for 50 Egyptian pounds and it's also possible to buy 10 reals with 50 Egyptian pounds.

Since the currency exchange house is not in the city where Cris is living, she uses her visits to that other city to make the exchange operations that she needs. However, she doesn't want to spend more that one day with the bureaucracy of such transactions. Therefore, if she were to visit Alexandria between days $$$s$$$ and $$$e$$$, she just will do exchange operations in exactly one of those days.

Choosing a day that would maximize the profit of the transactions is a simple task for Cris but, due to her vacations, she asked you to answer $$$q$$$ queries of this kind for her

• $$$s$$$ $$$e$$$ $$$D$$$ $$$R$$$: what is the biggest profit that could be obtain doing exchange operations of $$$D$$$ dollars and $$$R$$$ reals in exactly one day $$$i$$$, $$$s \leq i \leq e$$$.

The Egyptian government is organizing the municipal elections throughout the country. Currently, the two main political forces are the Sadat Democratic party and the Republican People's party. Both are making preparations to assure their victory in the upcoming elections. Both parties consider dangerous exchanging messages through internet. For that reason, they will use the Egyptian mailing system instead. To distinguish their messages, each party will put a mark on the message.

Since information is a key asset in any political campaign, both parties have infiltrated personnel in each mailing office of Egypt. To disrupt the communication of the opposition, when a mail passes through a post office, the personnel will exchange the mark in the message. That is, if a message has the mark of the Democrats, it will be exchanged for the mark of the Republicans, and vice-versa. We observe that, this exchange does not happen in the origin office or in the destination office. When sending a mail from office $$$A$$$ to office $$$B$$$, we do not know which offices the message will pass through. However, we know that a message will not pass through the same post office more than once.

The Democrats have hired Marcel "the optimizer" Saito to study the Egyptian mailing system. The Democrats want to know how many pairs of post offices are insecure and how many pairs of post offices are secure. We consider two distinct offices $$$A$$$ and $$$B$$$ secure (resp. insecure) if, regardless of the route a message takes from $$$A$$$ to $$$B$$$, the message arrives with the initial mark (resp. with the opposite mark).

As Marcel is always busy, he asks your help to answer this question.