Yeamin loves to play with functions. Recently, he has been experimenting with functions defined on integers.

The function $$$s(x)$$$ denotes the sum of the decimal digits of a positive integer $$$x$$$. For example, $$$s(125) = 1 + 2 + 5 = 8$$$.

Another function $$$h(x)$$$ repeatedly uses $$$s(x)$$$ until the result is a single-digit integer. Formally, $$$$$$ h(x) = \begin{cases} x, & x \lt 10,\\ h(s(x)), & x \ge 10. \end{cases} $$$$$$ For example, $$$h(987) = h(9+8+7) = h(24) = h(2+4) = h(6) = 6$$$.

To make things more interesting, Yeamin defines a new function $$$\displaystyle f(L,R) = \sum_{x=L}^{R} h(x^2)$$$ for integers $$$L$$$ and $$$R$$$ with $$$1 \le L \le R$$$. For example, $$$f(2,4) = h(2^2) + h(3^2) + h(4^2) = h(4) + h(9) + h(16) = 4 + 9 + 7 = 20$$$.

Now, Yeamin wants to compute $$$f(L, R)$$$ for multiple pairs of $$$L$$$ and $$$R$$$. Given the values of $$$L$$$ and $$$R$$$, determine $$$f(L,R)$$$.

In mathematical logic, a quantifier specifies how many elements in a domain satisfy a given property. The two most common quantifiers are the universal quantifier $$$\forall$$$, meaning "for all", and the existential quantifier $$$\exists$$$, meaning "there exists".

A universal quantifier states that a proposition must hold for every value in the domain. For example, the proposition $$$\forall x \,(x^2 \ge 0)$$$ is true over the integers because the square of every integer is non-negative. On the other hand, the proposition $$$\forall x \,(x^2 \gt x)$$$ is false over the integers, because it does not hold for certain values, such as $$$x = 0$$$ and $$$x = 1$$$.

An existential quantifier states that there exists at least one value in the domain for which the proposition holds. For example, the proposition $$$\exists x \,(x^2 - 5x + 6 = 0)$$$ is true over the integers because the equality is satisfied for $$$x = 2$$$ and $$$x = 3$$$. On the other hand, the proposition $$$\exists x \,(x^2 = 5)$$$ is false over the integers because there is no integer whose square equals $$$5$$$.

A statement may also contain multiple quantifiers. For example, the proposition $$$\forall x \, \exists y \,(x + y = 0)$$$ states that for every integer $$$x$$$, there exists an integer $$$y$$$ such that $$$x + y = 0$$$. Quantifiers are interpreted from left to right: each quantifier binds the variable that follows it, and inner quantifiers are evaluated within the scope determined by the preceding ones.

Let the domain of all variables be the set of all integers. The function $$$f(s)$$$ is defined for a binary string $$$s$$$ of length $$$n$$$. The function constructs the following proposition:

$$$$$$ \mathcal{Q}_1 x_1 \;\mathcal{Q}_2 x_2 \;\dots\; \mathcal{Q}_n x_n \;\bigl(x_1 + x_2 + \dots + x_n = 0\bigr), $$$$$$

where each $$$\mathcal{Q}_i$$$ is a quantifier determined by the $$$i$$$-th character of $$$s$$$: $$$$$$ \mathcal{Q}_i = \begin{cases} \exists & \text{if } s_i = 0, \\ \forall & \text{if } s_i = 1. \end{cases} $$$$$$

Given a binary string $$$s$$$, your task is to determine whether $$$f(s)$$$ is true or not.

In the vast Plains of Laurasia, there are $$$N$$$ villages numbered from $$$1$$$ to $$$N$$$, connected by exactly $$$N - 1$$$ bidirectional roads. The road network is designed such that there is exactly one $$$^{\dagger}$$$simple path between any two villages.

Merchants regularly travel between these villages to sell their goods. However, bandits have begun to learn the merchants' schedules in advance. Since there is currently only a single path connecting any two villages, an ambush is easy to arrange. If a bandit knows which villages the merchants plan to travel between, they can lie in wait along one of the roads in that path and rob them.

To reduce the chances of merchants being attacked by the bandits, the mayor has decided to build additional roads so that for every pair of villages, there exist at least two $$$^*$$$distinct simple paths between them.

Since constructing roads is expensive, the mayor wants to add as few new roads as possible.

Your task is to determine the minimum number of new roads that must be built so that for every pair of villages, there exists at least two distinct simple paths between them.

$$$^{\dagger}$$$A path between village $$$u$$$ and village $$$v$$$ is defined as a sequence of villages $$$x_1, x_2, \dots, x_k$$$ such that $$$x_1 = u$$$, $$$x_k = v$$$, and for each $$$1 \le i \lt k$$$, there exists a bidirectional road connecting village $$$x_i$$$ and village $$$x_{i+1}$$$. A path is called simple if it does not visit the same village twice.

$$$^{*}$$$Two paths are considered distinct if they differ by at least one road.

You live in a city that is modeled as a rectangular grid. Each cell in the city is a unit square, and the grid follows a standard Cartesian coordinate system where the $$$x$$$-axis increases from left to right and the $$$y$$$-axis increases from bottom to top.

A cyclone named Gigantomachia has formed at the bottom-left corner of the city, located at the point $$$(0, 0)$$$. According to meteorological forecasts, the cyclone will travel in a straight line towards the top-right corner of the city, located at the point $$$(x, y)$$$. The cyclone is immensely powerful, and every cell that it enters along its path will be damaged.

Your task is to determine the number of cells in the city that will be damaged by the cyclone.

In the vast Plains of Laurasia, there lives a foolish horse named Doddo, who is about to take part in an obstacle race.

The race track consists of $$$N$$$ lanes, numbered from $$$1$$$ to $$$N$$$, arranged side by side.

Each lane contains $$$M+2$$$ positions, labeled from $$$0$$$ to $$$M+1$$$. Positions $$$1$$$ through $$$M$$$ form the actual track. Position $$$0$$$ is the starting point, and position $$$M+1$$$ is the finishing point of each lane; these two positions are not considered part of the track.

There are $$$K$$$ obstacles. Each obstacle is described by a triple $$$(i, l, r)$$$, meaning that in lane $$$i$$$, every position $$$x$$$ such that $$$l \le x \le r$$$ is blocked by this obstacle.

It is guaranteed that the starting and finishing points in every lane are never blocked, and that no two obstacles in the same lane overlap.

Doddo starts at the starting point (position $$$0$$$) in a chosen lane. Each second of the race, the following steps occur in order:

1. If Doddo is already at the finishing point (position $$$M+1$$$) in any lane, the race ends immediately.

2. Suppose Doddo is currently at position $$$x$$$ in lane $$$i$$$. He checks whether position $$$x+1$$$ in lane $$$i$$$ is blocked.

3. If position $$$x+1$$$ is not blocked, Doddo stays in the same lane.

4. Otherwise, Doddo attempts to switch to an adjacent lane ($$$i-1$$$ or $$$i+1$$$), if such a lane exists and position $$$x$$$ in that lane is not blocked. Note that only position $$$x$$$ is checked for availability; even if position $$$x+1$$$ in the new lane is blocked, Doddo can still switch to that lane.

   In this situation, Doddo behaves in the following way:

   • If no adjacent lane is available, Doddo stays in the same lane.
   • If exactly one adjacent lane is available, Doddo switches to that lane.
   • If both adjacent lanes are available, Doddo becomes confused and chooses one of them uniformly at random.
   Doddo can switch lanes even at the starting point(position $$$0$$$). Doddo can change lanes at most once per second.

5. After that, if any obstacle does not block position $$$x+1$$$ in Doddo's current lane, Doddo moves to position $$$x+1$$$ in that lane; otherwise, Doddo crashes into the obstacle, and the race ends immediately.

If Doddo reaches the finishing point in any lane before the race ends, he wins the race. Otherwise, if he crashes at any point, he loses.

For each $$$i$$$ $$$(1 \le i \le N)$$$, determine the probability that Doddo wins the race if he starts at the starting point in lane $$$i$$$.

It is almost the end of the 3-1 semester for batch 22, and before the Eid holidays, $$$N$$$ students must be assigned to research groups for their upcoming thesis. There are $$$K$$$ distinct research groups available, and the university has decided on a unique procedure to assign students to these groups based on their academic standing.

Each student has a Face–Value in the department and a CGPA (ranging from 0.00 to 4.00). The assignment process works as follows:

1. All students are first sorted by their CGPA in descending order. (If multiple students have the exact same CGPA, they are sorted by their Face Value in descending order).
2. The students are then processed in batches of size $$$K$$$, strictly following this sorted order:
   • The first $$$K$$$ students are randomly and uniformly assigned to $$$K$$$ distinct groups.
   • The next $$$K$$$ students are then randomly and uniformly assigned to $$$K$$$ distinct groups, and this process repeats.
   • The final batch may contain fewer than $$$K$$$ students. If so, they are still randomly and uniformly assigned to distinct groups (meaning no two students from this final batch will end up in the same group).
3. A research group's score is the average of the CGPAs of all the students assigned to it.

Labib is one of these students. His information is always provided as the first entry in the university's records. He is curious about his academic future and wants to know: what is the expected score of the research group he will eventually be placed in?

Note: The expected value (or expectation) of a random variable is the probability-weighted average of all its possible values. Formally, if a random variable $$$X$$$ can take values $$$x_1, x_2, \dots, x_m$$$ with probabilities $$$p_1, p_2, \dots, p_m$$$ respectively, then its expected value $$$E[X]$$$ is defined as: $$$$$$E[X] = \sum_{i=1}^{m} x_i \cdot p_i$$$$$$

In the vast Plains of Laurasia, a clever but greedy donkey named Doru loves collecting treasures. The village market contains $$$N$$$ unique items, each with a weight and a profit value (how valuable it is to Doru).

Doru carries a bag with limited capacity. For a bag of capacity $$$c$$$, he can pick items whose total weight does not exceed $$$c$$$. Each item can be picked at most once.

Being ambitious, Doru wants to know: for every bag capacity from $$$1$$$ to $$$K$$$, what is the maximum total profit he can collect?

In Dhaka, the mosquito population has risen to unprecedented levels this year. The threat of an epidemic outbreak of Dengue or Chikungunya feels more serious than ever. As dusk settles over the city, a relentless buzzing fills the air. Sleep is no longer peaceful; every night feels like a siege.

Trying to protect himself, Ishraque finds an old mosquito net. Though worn, it represents a vital barrier – a wall between him and the swarm of killers. However, even as he tucks it in, he wonders in fear: how many enemies are already inside the wall?

The upper structure of the net is defined by $$$n$$$ points $$$(ax_1, ay_1), (ax_2, ay_2), \dots, (ax_n, ay_n)$$$. The net is anchored to the bed at $$$(ax_1, 0)$$$ and $$$(ax_n, 0)$$$. The boundary forms a polygon consisting of straight line segments consisting of points $$$(ax_i, ay_i), (ax_{i+1}, ay_{i+1})$$$ for all $$$i$$$ such that $$$1 \le i \lt n$$$, vertical segments connecting the first and last points to their respective anchors on the bed and a horizontal segment along the bed from $$$(ax_1, 0)$$$ to $$$(ax_n, 0)$$$.

There are currently $$$m$$$ mosquitoes in his room located at points $$$(bx_1, by_1), (bx_2, by_2), \dots, (bx_m, by_m)$$$. Your task is to determine how many mosquitoes are inside the net or on its boundary.