The Department of Computer Engineering at Sharif University of Technology has recently initiated a professional education program known as Micromasters. This program offers a set of courses designed to empower students with specialized knowledge and skills in various domains of computer science and engineering. As an incentive to promote the program, the department has introduced a referral system wherein individuals who refer other students to the Micromasters program receive a 10% discount for each referred student on their own course registrations.

Mina is a talented student who is passionate about spreading the benefits of the Micromasters program. With each referral, Mina's list of discounts grows, and now the following question arises: given the number of students who are referred by Mina, how many courses can she enroll in for free?

Hezardastan, a giant among Iranian IT holding groups, houses several innovative companies such as Cafebazaar, Divar, and Balad. The annual report of the holding consists of $$$n$$$ chapters, each dedicated to a company under Hezardastan's umbrella. The chapters in the report vary in length and occupy a certain number of pages. We want to compile all $$$n$$$ chapters into a PDF document that will be printed double-sided on A4 paper sheets. However, for aesthetic reasons, we want to avoid having pages from two different chapters printed on the same paper sheet. To ensure each chapter begins on a fresh, odd-numbered page, we plan to strategically insert an extra blank page after each chapter that has an odd number of pages. Now, we need to know the minimum number of A4 paper sheets needed to print the entire holding company report?

Initially, we have an array of length $$$1$$$ containing only the number $$$0$$$. All natural numbers are listed in ascending order in the "reservation list" (the first number in the list is $$$1$$$). The array undergoes $$$q$$$ operations. The $$$i^\mathrm{th}$$$ operation, is one of the following:

• Insert(p, x): Insert the first $$$x$$$ numbers from the reservation list after the number $$$p$$$ in the array, in ascending order. These numbers are removed from the reservation list.
• Remove(p, x): Remove the next $$$x$$$ numbers after number $$$p$$$ in the array. These numbers are not returned to the reservation list.

You are given information about $$$q$$$ operations, and you are asked to determine the number written in the middle of the array after each operation. If the length of the array after the $$$i^\mathrm{th}$$$ operation is $$$n$$$, you should find the $$$\lceil\frac{n}{2}\rceil^\mathrm{th}$$$ element of the array. Note that the indexing of the array starts from $$$1$$$.

Abolf lives in Aboland, a country consisting of $$$n$$$ cities and $$$n-1$$$ two-way roads. In Aboland, one can travel from any city to any other city using these roads. Aboland's cities are numbered from $$$1$$$ to $$$n$$$.

Abolbucks is a multinational chain of teahouses which serves the best tea in the world. When Abolf enters a city with an Abolbucks branch, he drinks a cup of tea and instantly reaches $$$k$$$ units of happiness. However, each time Abolf travels through the $$$i^\mathrm{th}$$$ road, he must pay $$$c_i$$$ coins as toll which causes him to lose $$$c_i$$$ units of happiness.

Abolf currently resides in city $$$1$$$ and wants to plan his summer trip. If at any point during his trip Abolf's happiness drops below zero, he would stops his trip immediately. For each city $$$t$$$ (for $$$2 \le t \le n$$$), Abolf wants to know what is the minimum amount of coins he should pay to reach city $$$t$$$ while making sure that his happiness remains non-negative at all time, including at the destination.

He has asked you to find this amount for each city except for his home city. Note that each destination should be considered separately. Also, he may visit a city multiple times during his trip.

A "terrain" is an $$$x$$$-monotone polygon defined by the points $$$p_1, \dots, p_n$$$ where each point $$$p_i$$$ has coordinates $$$(x_i, y_i)$$$, and the following three conditions hold:

• $$$y_1 = y_n = 0$$$
• $$$y_i \gt 0$$$ for $$$1 \lt i \lt n$$$
• $$$x_i \lt x_{i+1}$$$ for $$$1 \leq i \lt n$$$

Given a terrain defined by the points $$$p_1, \dots, p_n$$$, find the largest triangle that fits entirely within the terrain, and one of its three vertices is positioned at one of the terrain points $$$p_2$$$ through $$$p_{n-1}$$$.

The Department of Computer Engineering has provided several micromasters, each containing a curriculum. If a student successfully completes all the courses of a micromaster, he will receive the certificate of that micromaster. A course may be included in the curriculum of several micromasters. Soroush, who only thinks about getting a certificate and doesn't care about the type of certificate, wants to get $$$3$$$ micromasters certificates by taking the minimum possible number of courses. The micromasters curriculums are posted on the bulletin board. Help Soroush reach his goal according to the micromasters curriculums.

Jackson, after witnessing the advancements in the world of technology, decided to sell his small cozy house and enroll in the programming-and-algorithm micromaster. He came across an interesting algorithm that he needed to analyze and solve the problem related to it, in order to pass the exam at this stage of the course. The pseudocode of this algorithm is as follows:

input: a permutation $$$\pi = \langle \pi_1, \pi_2, \ldots, \pi_n\rangle$$$ of numbers $$$\{ 1, 2, \ldots, n\}$$$

while $$$\pi$$$ is changing during this iteration:

    for $$$i := n$$$ downto $$$2$$$:

        if $$$\pi_i \lt \pi_{\lfloor{i}/{2}\rfloor}$$$:

            swap$$$(\pi_i, \pi_{\lfloor{i}/{2}\rfloor})$$$

He wants to know for how many permutations $$$\pi$$$ of length $$$n$$$ from the possible $$$n!$$$ ones, the final permutation will be sorted after running this algorithm.

Amirreza is playing the Star Wars game. This game is played on an $$$n\times m$$$ board where each cell is either empty ('.'), contains a white piece ('W') or a black piece ('B'). At start of the game, Amirreza should choose exactly one white piece to play with. Afterwards he can move this piece multiple times to knock out as many black pieces as possible. Suppose the white piece is currently in cell $$$(i, j)$$$ of the board; In one move, this piece can go up-left $$$(i-1,j-1)$$$, up $$$(i-1,j)$$$ or up-right $$$(i-1, j+1)$$$, provided that cell exists on the board and it does not contains another white piece. If the cell contains a black piece, it will be knocked out. Help Amireza figure out the maximum number of black pieces he can knock out.

Maryam, a famous mathematician, recently has bought an old vintage car. This car uses a combustion engine to generate the power needed to move the car. Inside the engine, there are $$$n$$$ cylinders of length $$$m$$$ and inside each cylinder, there is a piston constantly moving up and down. All pistons move independently and at the same speed. At any given time, the position of a piston inside a cylinder can be shown with an integer from $$$0$$$ to $$$m$$$, which also describes the area of the cylinder occupied by the piston. A piston instantly changes its direction when it reaches the top (position $$$m$$$) or bottom (position $$$0$$$) of its cylinder.

Maryam managed to determine the position and direction of all the pistons at a specific time. Now she is curious about the maximum total area occupied by all the pistons. Help Maryam find out this value.

It's the end of the year, and Cafebazaar has released a list, containing the number of users of each of its $$$n$$$ applications. Now, each application is eager to showcase its success through an advertisement image, which highlights a continuous subset of the application list containing the application itself. Also, for the image to be credible, it should contain at least $$$k$$$ applications, including itself.

For each application in this list, we need to determine the minimum possible rank this application can achieve within any valid subset, according to the number of users. The rank of an application within a subset is defined by the number of applications in that subset that have more users than it, plus one.

Mike and Sally work in the warehouse of Monster Inc. as storekeepers. Their daily tasks are to process incoming requests and update the inventory of the Warehouse. Requests only include buying, selling, unpacking, and packing containers. The warehouse includes goods and containers and has unlimited space. A container may contain goods or other containers as sub-containers.

The exact format of the requests is given below.

• BUY <CONTAINER_DESCRIPTION>
• SELL <CONTAINER_ID>
• UNPACK <CONTAINER_ID>
• PACK <CONTAINER_DESCRIPTION>

Each container which is not inside any other container is uniquely identified by a positive integer ID. Assigning IDs to containers is done sequentially and started from 1. An ID is valid if and only if its container exists in the warehouse, otherwise it is invalid.

A container description is enclosed in parentheses and lists the contents, which can be either goods or sub-containers. A good is identified exclusively by its name, which consists of non-case-sensitive English letters. Multiple units of a good may be available. To denote quantities, place a positive integer 'N' before or after the good name (separated by one whitespace), where N < 100 is the number of the good. For example, ((tomato, potato), 4 celery, (wood, (silk 3, banana 2))) describes a container with four units of celery and two sub-containers.

The description of each request is as follows:

• BUY: A new container is transferred into the warehouse and an ID is assigned to it.
• SELL: An existing container with the given ID is ship out and its ID becomes invalid.
• UNPACK: All goods and sub-containers are extracted from the container and added to the warehouse. Moreover, the sub-containers become new containers and get their own ID. The assignment of IDs to the new containers is based on the order of their appearance in the container description (from left to right). For instance, considering the following two lines as the first requests, results in adding one unit of celery and adding three containers with IDs 2, 3, and 4 to the warehouse and ID 1 becomes invalid.

  	BUY (celery, (Banana), (Celery), (celery))
  	UNPACK 1	
  

• PACK: Goods specified in a PACK request are grouped into a new container, which is then assigned the next available ID.

Mike and Sulley process the requests in the order they are received. Any request with an invalid container ID must be discarded. Moreover, for PACK request they need to check if there exists enough units of each good in the warehouse.

Roz, the agent of Monster Inc. has told Mike once "I'm watching you, Wazowski. Always watching. Always.", She rolled her desk into their office and asked for requests and reports. She is looking for every detail. She is reviewing each request and might ask a few questions. Her questions might be each of the following types:

• ? COUNT <good>: How many units of the given good exist outside of containers?
• ? CONTAINS <good>: How many containers with ID have the given good, i.e. the good is in the container or there is a recursive sub-container which contains that good.
• ? MIN <good>: At least how many containers should be unpacked to reach one unit of the good. If it is impossible, the answer should be -1.

Mike and Sully are expected to answer these queries using just one integer.

Before helping Mike and Sully, read samples carefully.

'

Sarina and her brother, Soroush, are playing the rolling-dice game. The game is played on an $$$n \times m$$$ board. Initially, Soroush places a standard dice in one of the cells. It is place in a way that the number $$$6$$$ is on the upper face, the number $$$4$$$ is on the north face, and the number $$$2$$$ is on the west face. In a standard dice, $$$6$$$ is on the opposite side of $$$1$$$, $$$2$$$ is on the opposite side of $$$5$$$, and $$$3$$$ is on the opposite side of $$$4$$$. Additionally, he selects some of the cells and writes arbitrary integers numbers from $$$1$$$ to $$$6$$$ in them.

After that, Sarina have to move the dice on the board by rolling it multiple times. The act of rolling is defined as follows: Suppose two adjacent cells $$$A$$$ and $$$B$$$ share an edge $$$e$$$ and the dice is on the cell $$$A$$$; The dice can be rolled around its edge incident to $$$e$$$ and moved from $$$A$$$ to $$$B$$$. For example, consider the starting position of the dice. If the dice is rolled around the east, west, north, and south edges, the number appearing on the top face after rolling will be $$$2$$$, $$$5$$$, $$$3$$$, and $$$4$$$, respectively.

Whenever Sarina moves the dice to a a cell with a number in it in such a way that the number on the upper face of the dice matches the number in that cell, she gets a point. Note that Sarina can get a point from each cell at most one. The game is not that simple! There are obstacles in some of the cells and it is not possible to move the dice to the cells with an obstacle in it. Your task is to find out the maximum points that Sarina can get.

The Museum of Contemporary Art is holding a painting gallery focused on modern art, especially Monochromatic style paintings, which use only a single color. The gallery displays $$$n$$$ paintings arranged in a line.

The ICPC wants to bring students on an excursion to the gallery to spark their interest in art. However, the students are programmers, and everyone knows programmers only care about the colors of these modern paintings. They are also somewhat impatient. To keep their attention and to ensure they see every color without overwhelming them, the organizer decided to show them exactly two intervals of painting. This approach balances their short attention span and ensures all colors are represented. The task is to find two intervals of paintings such that each color appears at least once in at least one of the intervals, and the total number of paintings the students need to see is minimized.