$$$\qquad$$$The galactic exam requires a multiplication table. But if in 2022, every pupil had to know the regular multiplication table, then in the future, everyone must know not only the products of multiplication of two any natural numbers, but also the number of different numerals that are the product of multiplication of two any natural numbers in the table.
The first row contains one integer value $$$t$$$ $$$(1 \leq t \leq 1000)$$$; The following row contains two integer values $$$n$$$ and $$$k$$$ $$$(1 \leq n \leq 10^5 ; 1 \leq k \leq 10^9 )$$$ separated by space.
On each iteration, print one value: the number of times $$$k$$$ appears in the multiplication table of size $$$n$$$ x $$$n$$$.
2 5 10 6 12
2 4
Given two arrays $$$a$$$ and $$$b$$$ with the length of $$$n$$$ filled with numbers.
Let us consider that the result of formula $$$\sum_{i = 1}^n GCD(a_i, b_i)$$$ is their coolness
You can shuffle numbers in a given array $$$b$$$ as you like. You should find maximum coolness.
In the first row there is one positive integer value$$$n$$$ ($$$1 \leq n \leq 700$$$) — length of both arrays.
The second row consists of numbers $$$a_1, a_2, ... , a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — elements of the first array.
The third row consists of numbers $$$b_1, b_2, ... , b_n$$$ ($$$1 \leq b_i \leq 10^9$$$) — elements of the second array.
You should print the maximum coolness.
3 1 2 3 5 3 6
6
4 6 4 6 5 1 5 3 2
11
There is a function
$$$$$$ f(x)=\begin{cases} x - b + 1, & x \gt a \\ f(f(x + b)), & x \leq a \\ \end{cases} $$$$$$
and $$$t$$$ requests are given. Each request contains coefficients $$$a$$$, $$$b$$$ and variable $$$x$$$. You should calculate $$$f(x)$$$
First row contains single integer $$$t$$$ — the number of tests ($$$1 \leq t \leq 10^5$$$). Following $$$t$$$ rows. $$$i$$$-th row contains 3 integers $$$a, b$$$ and $$$x$$$ ($$$1 \leq a, b, x \leq 10^{18}$$$) — function's coefficients and variable appropriately.
You should output $$$t$$$ rows, each $$$i$$$-th row should contain single value — answer on $$$i$$$-th request.
2 4 9 9 27 26 31
1 6
3 11 24 20 12 22 10 56 5 11
-3 -8 53
Petya came across an unusual calculator. It does not have the usual "+", "-", "*" and "/" buttons. Maybe this is for the best, because the buttons for dialing numbers ("0", "1", ..., "9") and getting the result ("=") are located in their places. But what is most unusual about this calculator is the presence of "^{}" and "^{}^{}" buttons.
After many experiments with this calculator, Petya found out what these buttons mean.
The "^{}" button means the exponentiation operation $$$a^b$$$. For example, if you enter the expression "2^{}3" in the calculator, then as a result, it will display the number $$$2^3 = 8$$$.
The button "^{}^{}" means tetration $$$\displaystyle {^{b}a}=\underbrace {a^{a^{\cdot ^{\cdot ^{\cdot ^{a}}}}}} _{b}$$$. For example, if you enter the expression "2^{}^{}3", then as a result the calculator will display the number $$$^{3}2 = 2^{2^2} = 16$$$.
Petya planned to calculate several expressions on this calculator. Unfortunately, his experiments were enough to deal with the device of the calculator, but they were also enough to bring the calculator into an inoperable state.
Help Petya calculate the values of the remaining expressions. To do this, it is necessary to implement a program that processes the expression taking into account the precedence of operations. Tetration has a higher precedence (compared to exponentiation), so such operations must be performed first. It should also be borne in mind that the calculation of degrees and tetrations must be started from the farthest levels to the initial one. For example, the entry "a^{}^{}b^{}^{}c" should evaluate to $$$^{(^{c}b)}a$$$ and the expression "a^{}b^{}c" — as $$$a^{(b^c)}$$$.
The single line contains an expression without spaces, consisting of positive integers, operators "^{}" (exponentiation) and operators "^{}^{}" (tetration).
The number of characters in a line does not exceed $$$100\,000$$$.
It is guaranteed that all numbers do not contain leading zeros, the expression begins and ends with a number, the expression cannot contain two consecutive operators (there are no more than two characters "^{}" in a line).
Note that there is no limit to the number of digits in a number.
In a single line print the result of evaluating the expression. Since the result may be too large, output it modulo $$$10^9 + 7$$$.
2^^4
65536
42^^1^^2^1^^3
42
20^^2^^2
634985421
1000000013000000042^1000000013000000042
0
In the second example, the expression looks like this:
$$$$$$ (^{(^{2}1)}42)^{(^{3}1)} $$$$$$
$$$\qquad$$$Cosmo Go is Chief Coordinator Beeblebrox's favorite game, and, by the way, he does not like to lose. According to Cosmo Go rules, the game field is a rectangular goban, separated by vertical and horizontal lines. Standard cosmic goban consists of $$$N$$$ x $$$N$$$ cells in the Cartesian coordinate system $$$(x, y)$$$, where $$$(1 \leq x, y \leq N)$$$.
$$$\qquad$$$Each cell can contain one of three following objects: locked cells, empty cells, or Go-isi. They're painted in red, green, and white colors appropriately. For each $$$i$$$, $$$(1 \leq i \leq N)$$$, in the $$$i$$$-th column, cells from the bottommost row to the $$$A_i$$$-th row from the bottom — are red cells showing locked cells.
$$$\qquad$$$$$$M$$$ white cells are showing Go-isi. Each Go-isi has its own positive integer deleting cost. $$$j$$$-th white cell $$$(1 \leq j \leq M)$$$ is the cell $$$(X_j, Y_j)$$$. All the other cells are green, showing empty cells.
The rectangular region is fortified if it satisfies the following conditions:
$$$\qquad$$$1. There are no red cells inside the region.
$$$\qquad$$$2. There are two or more white pixels inside the region.
$$$\qquad$$$To win, Beeblebrox has to delete all fortified regions (each deletion is considered a turn). Beeblebrox always wants to set records. To achieve the best results, he has to reach the minimum cost of all turns. Beeblebrox has trouble figuring out protected areas, And he asked you to write a program that will help him identify and destroy protected areas.
$$$\qquad$$$You enthusiastically volunteered to help Beeblebrox solve such an interesting problem.
There is an integer $$$N$$$ in the first row $$$(1 \leq N \leq 200\,000)$$$, which shows field's height and width.
Second row contains $$$N$$$ integer values $$$A_i$$$ $$$(1 \leq A_i \leq N)$$$.
Third row contains integer value $$$M$$$ $$$(1 \leq M \leq 200\,000)$$$ — number of white cells on the field.
Following $$$M$$$ rows contain three integer values $$$X_i, Y_i, C_i$$$, where $$$1 \leq X_i, Y_i \leq N$$$ and $$$1 \leq C_i \leq 10^9$$$.
Output one positive integer value which shows minimal cost of committed turns needed to win.
7 5 6 2 3 6 7 6 5 7 7 5 3 3 7 3 7 10 1 7 6 4 7 8
16
$$$\qquad$$$There are $$$N$$$ planets in Adams' Universe, numbered from $$$1$$$ to $$$N$$$. Planets are connected with $$$N - 1$$$ space lifts. $$$i$$$-th space lift $$$(1 \leq i \leq N - 1)$$$ connects planet $$$A_i$$$ to planet $$$B_i$$$. Each space lift can move in any direction. You can travel from one planet to any other planet using space lifts.
$$$\qquad$$$Presently, Adams' Universe is divided into $$$K$$$ galaxies, numbered from $$$1$$$ to $$$K$$$. Planet $$$j (1 \leq j \leq N)$$$ belongs to the galaxy $$$C_j$$$. Every galaxy contains at least one planet.
$$$\qquad$$$One galaxy will be chosen as the main transportation hub (MTH) by Chief Coordinator Beeblebrox. For national security reasons, MTH must satisfy the following conditions.
$$$\qquad$$$You should be able to travel from any planet of MTH to any other planet of MTH, visiting only planets which belong to MTH.
$$$\qquad$$$Nevertheless, Chief Coordinator Beeblebrox noticed that it might be the case that no galaxy of Adams' Universe satisfies the condition, and he is not able to choose the MTH. $$$\qquad$$$In order to solve this problem, Chief Coordinator Beeblebrox can merge galaxies. Precisely, he can do the following operation.
$$$\qquad$$$Choose $$$x$$$ and $$$y$$$ satisfying $$$(1 \leq x, y \leq K)$$$ and $$$x \neq y$$$ and change the galaxies of planets belonging to the galaxy $$$y$$$ so that every planet belonging to the galaxy $$$y$$$ becomes a planet belonging to the galaxy $$$x$$$.
$$$\qquad$$$Merging galaxies is very labor-intensive, so Chief Coordinator Beeblebrox would like to minimize the number of times to merge galaxies in order to choose MTH.
$$$\qquad$$$Since Beeblebrox coordinates the whole Adams' Universe, which is not simple, he will not be able to do it himself, so he decided to ask you for help. Calculate the minimum number of times to merge galaxies to choose MTH.
There are two numbers $$$N$$$ and $$$K$$$ in the first row, $$$(1 \leq N \leq 200000)$$$, $$$(1 \leq K \leq N)$$$ — Number of planets and galaxies appropriately.
Each of the following $$$N$$$ rows contain numbers $$$A_i$$$ and $$$B_i$$$, $$$(1 \leq A_i, B_i \leq N)$$$, $$$(1 \leq i \leq N-1)$$$.
Following $$$K$$$ rows contain numbers $$$C_j$$$, $$$(1 \leq C_j \leq K)$$$, $$$(1 \leq j \leq N)$$$.
All the values in the input are integers.
Output the minimum number of merging galaxies needed to choose a MTH.
1 1 1
0
8 4 4 1 1 3 3 6 6 7 7 2 2 5 5 8 2 4 3 1 1 2 3 4
1
Vadim's brother attends the karate section and practices breaking planks in halves. Vadim decided not to lose an opportunity and make money on it. He wants to fill the broken edges with epoxy and cut down all remaining splinters.
Merchant said to Vadim that he would buy each plank for $$$m * S$$$, $$$S$$$– plank area. It is originally a rectangle, three sides are flat, and the fourth is broken. Vadim placed the plank in the coordinate plane, broken side upwards so that its lower side coincides with the abscissa axis. Vadim can describe slivers on the drawing as a polyline that consists of $$$n$$$ vertices (img.1).
After that, in a hardware store, Vadim discovered that one epoxy drop costs $$$k$$$ coins. In the store, the merchant told him that one drop of epoxy would occupy precisely one unit of area in his drawing. Also, to help Vadim, the merchant promised to sell even a noninteger amount of drops of epoxy. After Vadim pours the epoxy and its polymerize (img. 2), he will cut down all remaining splitters and sell the plank (on img. 3, you can see the line by which the plank will be cut down). Help Vadim: write a program, which according to the description and prices of $$$m$$$ and $$$k$$$, will calculate the maximum amount of money that Vadim can get from this plank.
It is guaranteed that answer will be fit double. The answer should be displayed with an accuracy of $$$10^{-6}$$$
The first row contains single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) - the number of vertices in the polynomial. The following row contains 2 values $$$m$$$ and $$$k$$$ ($$$0 \lt m, k \leq 10^9$$$) ($$$m$$$ and $$$k$$$ may be float) - price per unit of area and price per drop of epoxy appropriately. $$$i$$$-th of following $$$n$$$ rows contain two integers $$$x$$$ and $$$y$$$ ($$$0 \leq x, y \leq 10^{9}$$$, $$$x_i \gt x_{i-1}$$$) - coordinates of $$$i$$$-th polygonal line vertex.
Print single value — answer. The answer should be displayed with an accuracy of $$$10^{-6}$$$
8 1.5 10.2 1 4 3 5 4 2 5 6 6 5 8 6 9 2 11 6
38.272059
Egor is qualifying to Student union FCSN. There are $$$n - 1$$$ people in Student union. Egor numbered them from $$$2$$$ to $$$n$$$. Student union chairman Has number $$$n$$$. To get into Student union, Egor must score as much points as possible. $$$i$$$-th Student union member gives $$$a_i$$$ points for completed task. And also some of the Student union members can send Egor to colleagues, so that he can continue to do a job with one of them. So, if Student union member with number $$$k$$$ can direct Egor to colleagues, he calls him two numbers: $$$l_k$$$ and $$$r_k$$$. This means that Yegor can choose any Student union member with number $$$q \in [l_k, r_k]$$$ and go to him. Egor cannot go anywhere without given destination.
Egor marked himself with number $$$1$$$.
Help Egor calculate his chances. Calculate te maximum number of points that Egor can score. If Yegor can't get to the Student union chairman, print "No" (without quotation marks).
The first row contains two integer numbers $$$n$$$ and $$$m$$$ ($$$1 \leq m \lt n \leq 10^5$$$) - the number of Student union members (with due regard for Egor) and number of Student union members, who can send Egor further.
The second row contains integer numbers $$$a_1, a_2, ... , a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) - points, which can score Egor. Note that Yegor already has $$$a[1]$$$ points on the start.
Following $$$m$$$ rows contain 3 integer numbers $$$k$$$, $$$l$$$, $$$r$$$ ($$$1 \leq k \lt l \leq r \leq n$$$) - Student union members description.
Print the maximum number of points that can score Egor, or "No" (without quotation marks), If Yegor can't get to the Student union chairman.
6 4 5 1 3 3 2 3 1 2 6 3 4 5 2 5 5 5 6 6
13
5 2 6 3 5 1 1 1 3 4 2 4 5
No
Length of array which can consist only from numbers $$$1, 2, 3, 4, 5, 6$$$ is $$$n$$$.
You are given $$$q$$$ requests of the kind of $$$t$$$, $$$l$$$, $$$r$$$ ($$$l \leq r$$$), where $$$t$$$ is the type of request (1 or 2), $$$l$$$ and $$$r$$$ — are left and right borders of the subline:
If $$$t = 1$$$. sort the subline $$$[l, r]$$$ in non-decreasing order. This type of request does not require a response.
If $$$t = 2$$$. Print the length of the maximum increasing subsequence on the segment $$$[l, r]$$$
The first row consists of 2 integer numbers $$$n$$$ and $$$q$$$ ($$$1 \leq n, q \leq 10^5$$$) - length of array and number of requests appropriately. The second row consists of $$$n$$$ integer numbers $$$a_i$$$ ($$$1 \leq a_i \leq 6$$$) - elements of array. In each of the following $$$q$$$ rows contain 3 integer numbers divided by space $$$t$$$, $$$l$$$, $$$r$$$ ($$$1 \leq t \leq 2, 1 \leq l \leq r \leq n$$$) - description of given requests.
In response to each request of the second type print a single integer in a separate row - response to given request.
6 5 3 5 3 5 1 6 1 4 4 2 1 2 2 2 3 2 4 6 1 1 2
2 1 2
6 4 5 2 4 5 1 2 2 3 5 1 2 3 1 3 6 2 3 6
2 4
Vova got the homework from his teacher. After that he got mail which contains number $$$n$$$ and row in length of $$$9 * n$$$ characters, consisting of capital latin letters. Since the teacher loves his native programming championship, he wants to find the minimum number of letters to replace in the sent string so that the substring "BSUIROPEN" (without captions) have met in the string as many times as possible. Help Vova to solve the problem.
The first row consists of one natural number $$$n$$$ ($$$1 \leq 9 * n \leq 200\,000$$$). The following row contain string with length $$$9 * n$$$, consisting only from capital latin letters.
In one string print integer number - answer to the problem.
2 MKUKBSUIROPENKANDS
17
3 BSUIRLMEBBJUMSOPMEMNDIROPMC
13