There are $$$n$$$ countries numbered from $$$1$$$ to $$$n$$$ in Erathia. Each country can be regarded as a chain with $$$m+1$$$ nodes numbered from $$$1$$$ to $$$m+1$$$. Initially, node $$$(a, b)$$$ is connected with node $$$(a, b + 1)$$$ by a street where node $$$(a, b)$$$ denotes the $$$b$$$-th node of the $$$a$$$-th country. There are no bridges between any two countries at first.
You need to process $$$q$$$ queries of the following two types.
- $$$1\ a\ b$$$ ($$$1\leq a \lt n, 1\leq b\leq m$$$). Build a bridge between node $$$(a, b)$$$ and node $$$(a + 1, b)$$$. It is guranteed that at any time, each node is connected with at most one bridge.
- $$$2\ a$$$ ($$$1\leq a\leq n$$$). A hero will walk through Erathia. This hero starts from $$$(a, 1)$$$. If the hero is at $$$(x, y)$$$ and there is a unvisited bridge connected to him, he passes it, or he goes to $$$(x, y + 1)$$$. Once he arrived the $$$(m+1)$$$-th node of any conutry, he stops. Please note that "unvisited bridge" is independently judged for each query.
Your task is to print which country the hero is in at last for the second kind of query. It can be proved that the hero's route is always unique under these constraints.
The first line contains three integers $$$n$$$, $$$m$$$ and $$$q$$$ ($$$1 \leq n, m, q \leq 10 ^ 5$$$).
Each of the following $$$q$$$ lines represents a query with format described above.
For each query of type $$$2$$$, output a line with an integer representing the answer.
3 4 13 2 2 1 1 3 2 1 2 2 2 3 1 2 4 2 1 2 2 2 3 1 2 1 2 1 2 2 2 3
2 2 1 3 3 1 2 3 2 1
You are given an $$$n \times m$$$ grid. Some of the cells are obstacles, the others are empty. Choose a non-negative integer $$$k$$$ and color all empty cells with $$$k+1$$$ colors $$$0, 1, 2, \ldots k$$$. You can not color two cells in the same row or same column with the same non-zero color.
You are given two non-negative integers $$$c$$$ and $$$d$$$. For a coloring plan, define $$$z$$$ as the number of the cells with color $$$0$$$. Define the cost of the plan is $$$ck+dz$$$.
Find the minimum cost.
The first line contains four integers $$$n$$$, $$$m$$$ ($$$1\leq n, m\leq 250$$$), $$$c$$$ and $$$d$$$ ($$$0\leq c, d\leq 10 ^ 9$$$).
The $$$i$$$-th line of the next $$$n$$$ lines contains a string of $$$m$$$ characters. The $$$j$$$-th character is '*' if the cell in the $$$i$$$-th row and the $$$j$$$-th column is an obstacle. The $$$j$$$-th character is '.' if the cell in the $$$i$$$-th row and the $$$j$$$-th column is empty.
Output a line with a single number, representing the answer.
3 4 2 1 .*** *..* **..
4
3 4 1 2 .*** *..* **..
2
Ranran needs to prepare a contest! A contest is made of $$$c$$$ problems, and Ranran can do one of the following two things:
- Clone himself in $$$a$$$ minutes. That is, after $$$a$$$ minutes, there will be one more Ranran.
- Prepare a problem in $$$b$$$ minutes. That is, after $$$b$$$ minutes, there will be one more problem.
Note that a cloned Ranran can also do the two things above. A Ranran cannot do the two things at the same time.
Ranran wants to prepare the contest as fast as possible. But he is very lazy, so he asks you to find the minimum number of minutes to prepare the contest.
You need to answer $$$T$$$ queries independently.
The first line contains an integer $$$T$$$ ($$$1\leq T\leq 10 ^ 5$$$).
Each of the next $$$T$$$ lines contains three integers $$$a$$$, $$$b$$$ and $$$c$$$ ($$$1\leq a, b, c\leq 10 ^ 9)$$$, representing a query.
For each test case, output a line with a single integer representing the answer.
51 1 12 3 39 9 93 26 471064 822 1048576
1 7 45 44 21860
There are $$$n$$$ contestants and they take part in $$$m$$$ contests. You are given the ranklist of each contest. The ranklist of the $$$k$$$-th contest is a sequence $$$a_k$$$, indicating that the $$$a_{k, i}$$$-th contestant's rank is $$$i$$$.
SolarPea and PolarSea are two of the $$$n$$$ contestants. SolarPea wants to prove that he is stronger than PolarSea.
Define $$$x$$$ is $$$l$$$-stronger than $$$y$$$, if and only if there exists a sequence $$$b$$$ of length $$$l + 1$$$, such that $$$b_1 = x$$$, $$$b_{l + 1} = y$$$, and for all $$$1\leq i\leq k$$$, $$$b_i$$$ has a smaller rank than $$$b_{i + 1}$$$ in at least one contest.
There are $$$q$$$ queries. In the $$$i$$$-th query, SolarPea is contestant $$$x$$$ and PolarSea is contestant $$$y$$$. Please find the minimum positive number $$$l$$$ such that SolarPea is $$$l$$$-stronger than PolarSea.
The first line contains two integers $$$n$$$ ($$$2\leq n\leq 10 ^ 5$$$) and $$$m$$$ ($$$1\leq m\leq 5$$$).
The $$$i$$$-th of the next $$$m$$$ lines contains $$$n$$$ intergers $$$a_{i, 1}, a_{i, 2}, \ldots, a_{i, n}$$$. It is guaranteed that $$$a_i$$$ is a permutaion of $$$1,2,\ldots,n$$$.
The next line contains an integer $$$q$$$ ($$$1\leq q\leq 10 ^ 5$$$).
Each of the next $$$q$$$ lines contains two integers $$$x$$$ and $$$y$$$ ($$$1 \le x,y \le n, x \neq y$$$), representing a query.
For each query, output a number $$$l$$$ representing the answer. If there is no legal $$$l$$$, output $$$-1$$$.
6 2 1 3 2 5 4 6 2 1 4 3 6 5 4 1 4 5 3 6 1 5 2
1 2 5 3
We define a function $$$f(x)$$$ over all non-negative integer $$$x$$$ as follows: $$$$$$ f(x) = \begin{cases} 1 & (x = 0) \\ f(\frac{x}{3}) + 1 & (x \gt 0\land x\bmod3 = 0) \\ f(x - 1) + 1 & (x \gt 0\land x\bmod 3\neq 0) \end{cases} $$$$$$ Calculate $$$\max_{x = l} ^ r f(x)$$$.
You need to answer $$$T$$$ queries independently.
The first line contains a single integer $$$T$$$ ($$$1\leq T\leq 10 ^ 4$$$).
Each of the next $$$T$$$ lines contains two integers $$$l$$$ and $$$r$$$ ($$$1\leq l\leq r\leq 10 ^ {18}$$$), representing a query.
Output $$$T$$$ lines. The $$$i$$$-th line contains a single integer, representing the answer to the $$$i$$$-th query.
101 21 31 41 52 32 42 53 43 54 5
3 3 4 5 3 4 5 4 5 5
You are doing volunteer work for a programming competition in an ancient hotel. Unfortunately, the hotel provides no phone signal or tap water since it can be dated back to the Qin Dynasty, and you have to assign the contestants to the hotel rooms manually instead of using the internet apps. Fortunately, the hotel has sufficient rooms, and you have taken a computer that lets you do some computation locally.
There are $$$n$$$ teams, each with exactly $$$3$$$ contestants. There are $$$2$$$ types of rooms in the hotel, the single room and double room, which can receive at most $$$1$$$ and $$$2$$$ contestants, respectively. To avoid embarrassing contestants, if two contestants are assigned to a double room, they must come from the same team and have the same gender.
The cost of each room of the same type is the same, but different types may have different costs. Your program needs to calculate the minimum price the host has to pay. The teams are waiting in the registration hall now, and the competition finance officer relies on you to save costs and make a fortune by the residual value. Be quick, or the finance officer will sue you for violating his reputation!
The first line of input contains three integers $$$n$$$, $$$c_1$$$ and $$$c_2$$$ ($$$1 \leq n, c_1, c_2 \leq 1\,000$$$), denoting the number of teams, the cost of a single room and a double room respectively.
In the following $$$n$$$ lines, each line contains a string $$$S$$$ with exactly $$$3$$$ uppercase English letters. The letters in a string denote the genders of the contestants in one team and will be represented by A to Z, respecting the diversity of human beings.
The output should contain a single integer, denoting the minimum cost of hotel allocation for contestants.
3 1 3 MMM MMM FFF
9
3 3 1 ABC DEF GHI
9
10 438 438 WWW SOU PUN ETC OME CFI NAL GOO DHO TEL
12264
You are given $$$n$$$ strings and required to find the length of the longest perfect word.
A string $$$t$$$ is called a perfect word, if and only if every non-empty substring of $$$t$$$ appears in the given strings.
A string $$$s$$$ is called a substring of $$$t$$$ if and only if it can be obtained by removing several (possibly zero) characters from the beginning or end of $$$t$$$.
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 10 ^ 5$$$).
Each of the next $$$n$$$ lines contains a string consisting of lowercase English letters.
It is guaranteed that the total length of the given strings is no more than $$$10 ^ 5$$$.
Output an integer, representing the length of the longest perfect word.
4 a t b ab
2
$$$$$$ 2 ^ {2 ^ {2 ^ {2 ^ {2 ^ {2 ^ {2 ^ {2 ^ {2 ^ {2}}}}}}}}} $$$$$$
SolarPea likes blowing up PolarSea's blog by sending power tower of $$$2$$$. As the tower is too high, the stack of the web page overflows. So the blog no longer works.
Now SolarPea has $$$n$$$ powers of two $$$a_1, a_2, \ldots, a_n$$$, $$$x$$$ bitwise AND operators, $$$y$$$ bitwise OR operators and $$$z$$$ bitwise XOR operators. It is guaranteed that $$$n = x + y + z$$$.
Solarpea wants to construct an arithmetic expression with these numbers and operators. Formally, define $$$x_0 = 0$$$ and $$$x_i = x_{i - 1}\ \mathrm{op}_i\ b_i$$$, where $$$b$$$ is a permutation of $$$a$$$, which means we can rearrange $$$a$$$ to get $$$b$$$, and $$$\mathrm{op}_i$$$ is one of the three types of bitwise operators above. Then $$$x_n$$$ is the result of the expresstion.
The larger the expression, the more likely it is to make PolarSea's blog unable to work. SolarPea wants you to help him to find the largest $$$x_n$$$ and construct such an expression. If there are multiple solutions, output any of them.
You need to process $$$T$$$ test cases independently.
The first line contains a single integer $$$T$$$ ($$$1\leq T \leq 10 ^ 5$$$), denoting the number of test cases.
For each test case, the first line contains four integers $$$n$$$, $$$x$$$, $$$y$$$ and $$$z$$$ ($$$0\leq x, y, z\leq n \leq 65\,536, n = x + y + z$$$). The next line contains $$$n$$$ integers $$$c_1, c_2, \ldots, c_n$$$ ($$$0\leq c_i \lt n$$$), where $$$a_i = 2 ^ {c_i}$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases is no more than $$$1\,048\,576$$$.
For each test case, output three lines.
The first line contains a $$$01$$$-string of length $$$n$$$, representing the binary form of the largest $$$x_n$$$.
The next line contains a single $$$1$$$-indexed string $$$\mathrm{op}$$$ of length $$$n$$$, where $$$\mathrm{op}_i$$$ represents the $$$i$$$-th operator. Here, we denote AND as $$$\text{\&}$$$ (ASCII 38), OR as $$$\text{|}$$$ (ASCII 124), and XOR as $$$\text{\^{}}$$$ (ASCII 94). You should guarantee that there is exactly $$$x$$$ AND operators, $$$y$$$ OR operators and $$$z$$$ XOR operators.
The third line contains $$$n$$$ integers $$$d_1, d_2, \ldots, d_n$$$, the $$$i$$$-th of which representing the logarithm of $$$b_i$$$ with base $$$2$$$. That is, $$$d$$$ is a permutaion of $$$c$$$.
If there are multiple solutions, output any of them.
44 3 0 11 0 1 04 1 0 31 0 1 08 0 2 61 5 5 7 1 5 5 78 0 0 81 5 5 7 1 5 5 7
0010 &&^& 0 0 1 1 0011 ^^&^ 0 1 0 1 10100000 ^^|^^^^| 1 5 5 7 1 5 5 7 00000000 ^^^^^^^^ 1 5 5 7 1 5 5 7
$$$$$$ \frac { \prod^ { { { \prod^ { { \sideset { _{2}^{2} } { _{2}^{2} } { \operatorname{{2}^{2}_{2}} } }_ { \prod^{2}_{2} } } _{ \binom { {2}^{2} } { {2}_{2} } } } _{ \begin{bmatrix} { \int ^{ {2}^{2} } _{ \begin{bmatrix} {2}&{2}\\ {2}&{2} \end{bmatrix} } } &{ \prod^{{2}_{2}}_{{2}^{2}} } \\ { { {2}_{2} } ^{ \sum^{2}_{2} } } &{ \frac { \sum^{2}_{2} } { \sum^{2}_{2} } } \end{bmatrix} } } _{ \frac { { \frac { {2}^{2} } { {2}^{2} } } ^{ \int ^{ {2}_{2} } _{ \sum^{2}_{2} } } } { { \begin{bmatrix} {{2}^{2}}&{{2}_{2}}\\ {\binom{2}{2}}&{\int^{2}_{2}} \end{bmatrix} } ^{ \binom{\sum^{2}_{2}}{{2}_{2}} } } } } _{ { { { {{2}_{2}}_{\frac{2}{2}} } ^{ {\binom{2}{2}} ^{ \sideset {_{2}^{2}} {_{2}^{2}} {\operatorname{{2}^{2}_{2}}} } } } ^{ \sideset { _{ { \sideset {_{2}^{2}} {_{2}^{2}} {\operatorname{{2}^{2}_{2}}} } ^{ \frac{2}{2} } } ^{ \sideset { _{{2}^{2}}^{\binom{2}{2}} } { _{ \sum^{2}_{2} } ^{ \begin{bmatrix} {2}&{2}\\ {2}&{2} \end{bmatrix} } } { \operatorname{{\frac{2}{2}}^{{2}^{2}}_{{2}^{2}}} } } } { _{ \binom{{2}_{2}}{\sum^{2}_{2}} } ^{ \sum^{\frac{2}{2}}_{{2}_{2}} } } { \operatorname{ \int ^{ \begin{bmatrix} {2}&{2}\\ {2}&{2}\end{bmatrix} } _{{2}_{2}} } } ^{ \begin{bmatrix} {{2}^{2}}&{\sum^{2}_{2}}\\ {{2}_{2}}&{{2}_{2}} \end{bmatrix} } _{ \int ^{ {2}^{2} } _{ \begin{bmatrix} {2}&{2}\\ {2}&{2} \end{bmatrix} } } } } } } {2} $$$$$$
Given a square grid, its lattice points labeled from $$$(0, 0)$$$ to $$$(n, n)$$$, and a number $$$t$$$.
You need to answer $$$q$$$ queries in this format: given $$$A = (x_0, y_0)$$$ and $$$B = (x_1, y_1)$$$, how many ways are there to move from $$$A$$$ to $$$B$$$ in exactly $$$t$$$ steps so that in each step you move from a lattice point to one of its neighbors (up, down, left, right). Calculate the answer modulo $$$998\,244\,353$$$.
The first line contains three integers $$$n$$$ ($$$1 \leq n \leq 10^5$$$), $$$t$$$ ($$$1 \leq t \leq 10^9$$$) and $$$q$$$ ($$$1 \leq q \leq 3 \times 10^5$$$).
Each of the following $$$q$$$ lines contains four integers $$$x_0$$$, $$$y_0$$$, $$$x_1$$$ and $$$y_1$$$ ($$$0 \leq x_0, y_0, x_1, y_1 \leq n$$$), representing a query.
For each query, output a line containing one integer, representing the answer to the query modulo $$$998\,244\,353$$$.
2 5 3 0 0 1 2 1 1 2 1 0 0 2 2
30 64 0
5 20 5 0 0 5 5 1 1 4 4 2 2 3 3 2 3 2 3 1 2 5 2
615136704 443203969 899931333 464755094 679729107
Given a sequence $$$a_1, a_2, \ldots, a_n$$$.
You are going to select zero or more elements of $$$a$$$ so that: if you select $$$a_i$$$, then in any interval of length $$$i$$$ (formally, in $$$a[j, j + i - 1]$$$ for any $$$1 \le j \le n - i + 1$$$) you can select at most $$$2$$$ elements.
Calculate the maximal sum of the elements you select.
The first line contains an integer $$$n$$$ ($$$2 \leq n \leq 10^5$$$).
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$).
Output a single integer denoting the answer.
4 1 4 3 2
7
3 -10 -10 -10
0
You are given $$$n$$$ vertical lines with x-coordinates $$$x_1, x_2, \ldots, x_n$$$ and weights $$$a_1, a_2, \ldots, a_n$$$ and $$$m$$$ horizontal lines with y-coordinates $$$y_1, y_2, \ldots, y_m$$$ and weights $$$b_1, b_2, \ldots, b_m$$$.
Call a rectangle good if and only if all of its four edges lie on the given lines. On this basis, define the cost of a good rectangle as the sum of the costs of its four segments. The cost of a segment is the product of its length and the weight of the line it belongs.
Find the maximum area of good rectangles with cost no more than $$$c$$$. Note that the length and the width of the rectangle can be zero, so the answer always exists.
You need to answer $$$T$$$ queries with different $$$c$$$.
The first line contains three integers $$$n$$$, $$$m$$$ ($$$2\leq n, m\leq 5\,000$$$) and $$$T$$$ ($$$1\leq T\leq 100$$$).
The second line contains $$$n$$$ integers $$$x_1, x_2, \ldots, x_n$$$ ($$$1\leq x_1 \lt x_2 \lt \ldots \lt x_n \leq 10 ^ 5$$$).
The third line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1\leq a_i\leq 10 ^ 7$$$).
The fourth line contains $$$m$$$ integers $$$y_1, y_2, \ldots, y_m$$$ ($$$1\leq y_1 \lt y_2 \lt \ldots \lt y_m \leq 10 ^ 5$$$).
The fifth line contains $$$m$$$ integers $$$b_1, b_2, \ldots, b_m$$$ ($$$1\leq b_i\leq 10 ^ 7$$$).
Each of the next $$$T$$$ lines contains a single integer $$$c$$$ ($$$1\leq c\leq 4\times 10 ^ {12}$$$), representing a query.
For each query, output one line representing the answer.
3 4 20 1 3 4 3 1 2 1 3 4 7 4 2 1 2 1 5 6 7 9 10 11 12 15 16 17 22 23 28 30 35 43 47 49 57
0 0 1 1 1 2 2 3 3 4 4 6 6 9 9 12 12 12 18 18
You are given a tree $$$T$$$ with $$$n$$$ nodes. The tree is rooted at $$$1$$$. Define $$$\mathrm{subtree}(u)$$$ as the set of nodes in the subtree of $$$u$$$.
Call a subset of nodes $$$S$$$ good if and only if $$$S$$$ satisfies at least one of the following contidions:
- For all $$$u, v\in S$$$ where $$$u\neq v$$$, either $$$u\in \mathrm{subtree}(v)$$$ or $$$v\in \mathrm{subtree}(u)$$$.
- For all $$$u, v\in S$$$ where $$$u\neq v$$$, both $$$u\notin \mathrm{subtree}(v)$$$ and $$$v\notin \mathrm{subtree}(u)$$$.
You need to partition all nodes of $$$T$$$ into several good subsets. Calculate the minimum number of subsets.
The first line contains a single integer $$$Q$$$ ($$$1\leq Q\leq 10 ^ 5$$$), denoting the number of test cases.
For each test case, the first line contains an integer $$$n$$$ ($$$1\leq n\leq 10 ^ 6$$$). The next line contains $$$n - 1$$$ integers $$$p_2, p_3, \ldots, p_n$$$ ($$$1\leq p_i \lt i$$$), indicating that there is an edge between $$$p_i$$$ and $$$i$$$ for each $$$i=2,3,\ldots,n$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases is no more than $$$10 ^ 6$$$.
For each test case, output a single integer representing the answer.
271 1 2 2 2 351 2 3 4
3 1