There is a grid with $$$n$$$ rows and $$$m$$$ columns. Each cell of the grid has an integer in it, where $$$a_{i, j}$$$ indicates the integer in the cell located at the $$$i$$$-th row and the $$$j$$$-th column. Each integer from $$$0$$$ to $$$(n \times m - 1)$$$ (both inclusive) appears exactly once in the grid.
Let $$$(i, j)$$$ be the cell located at the $$$i$$$-th row and the $$$j$$$-th column. You now start from $$$(1, 1)$$$ and need to reach $$$(n, m)$$$. When you are in cell $$$(i, j)$$$, you can either move to its right cell $$$(i, j + 1)$$$ if $$$j \lt m$$$ or move to its bottom cell $$$(i + 1, j)$$$ if $$$i \lt n$$$.
Let $$$\mathbb{S}$$$ be the set consisting of integers in each cell on your path, including $$$a_{1, 1}$$$ and $$$a_{n, m}$$$. Let $$$\text{mex}(\mathbb{S})$$$ be the smallest non-negative integer which does not belong to $$$\mathbb{S}$$$. Find a path to maximize $$$\text{mex}(\mathbb{S})$$$ and calculate this maximum possible value.
There are multiple test cases. The first line of the input contains an integer $$$T$$$ indicating the number of test cases. For each test case:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 10^6$$$, $$$1 \le n \times m \le 10^6$$$) indicating the number of rows and columns of the grid.
For the following $$$n$$$ lines, the $$$i$$$-th line contains $$$m$$$ integers $$$a_{i, 1}, a_{i, 2}, \cdots, a_{i, m}$$$ ($$$0 \le a_{i, j} \lt n \times m$$$) where $$$a_{i, j}$$$ indicates the integer in cell $$$(i, j)$$$. Each integer from $$$0$$$ to $$$(n \times m - 1)$$$ (both inclusive) appears exactly once in the grid.
It's guaranteed that the sum of $$$n \times m$$$ of all test cases will not exceed $$$10^6$$$.
For each test case output one line containing one integer indicating the maximum possible value of $$$\text{mex}(\mathbb{S})$$$.
22 31 2 43 0 51 51 3 0 4 2
3 5
For the first sample test case there are $$$3$$$ possible paths.
- The first path is $$$(1, 1) \to (1, 2) \to (1, 3) \to (2, 3)$$$. $$$\mathbb{S} = \{1, 2, 4, 5\}$$$ so $$$\text{mex}(\mathbb{S}) = 0$$$.
- The second path is $$$(1, 1) \to (1, 2) \to (2, 2) \to (2, 3)$$$. $$$\mathbb{S} = \{1, 2, 0, 5\}$$$ so $$$\text{mex}(\mathbb{S}) = 3$$$.
- The third path is $$$(1, 1) \to (2, 1) \to (2, 2) \to (2, 3)$$$. $$$\mathbb{S} = \{1, 3, 0, 5\}$$$ so $$$\text{mex}(\mathbb{S}) = 2$$$.
So the answer is $$$3$$$.
For the second sample test case there is only $$$1$$$ possible path, which is $$$(1, 1) \to (1, 2) \to (1, 3) \to (1, 4) \to (1, 5)$$$. $$$\mathbb{S} = \{1, 3, 0, 4, 2\}$$$ so $$$\text{mex}(\mathbb{S}) = 5$$$.
Given $$$n$$$ strings $$$w_1, w_2, \cdots, w_n$$$, please select $$$k$$$ strings among them, so that the lexicographic order of string $$$v$$$ is minimized, and output the optimal string $$$v$$$. String $$$v$$$ satisfies the following constraint: $$$v$$$ is the longest common prefix of two selected strings with different indices. Also, $$$v$$$ is the lexicographically largest string among all strings satisfying the constraint.
More formally, let $$$\mathbb{S}$$$ be a set of size $$$k$$$, where all the elements in the set are integers between $$$1$$$ and $$$n$$$ (both inclusive) and there are no duplicated elements. Let $$$\text{lcp}(w_i, w_j)$$$ be the longest common prefix of string $$$w_i$$$ and $$$w_j$$$, please find a set $$$\mathbb{S}$$$ to minimize the lexicographic order of the following string $$$v$$$ and output the optimal string $$$v$$$.
$$$$$$ v = \max\limits_{i \in \mathbb{S}, j \in \mathbb{S}, i \ne j} \text{lcp}(w_i, w_j) $$$$$$
In the above expression, $$$\max$$$ is calculated by comparing the lexicographic order of strings.
Recall that:
- String $$$p$$$ is a prefix of string $$$s$$$, if we can append some number of characters (including zero characters) at the end of $$$p$$$ so that it changes to $$$s$$$. Specifically, empty string is a prefix of any string.
- The longest common prefix of string $$$s$$$ and string $$$t$$$ is the longest string $$$p$$$ such that $$$p$$$ is a prefix of both $$$s$$$ and $$$t$$$. For example, the longest common prefix of "abcde" and "abcef" is "abc", while the longest common prefix of "abcde" and "bcdef" is an empty string.
- String $$$s$$$ is lexicographically smaller than string $$$t$$$ ($$$s \ne t$$$), if
- $$$s$$$ is a prefix of $$$t$$$, or
- $$$s_{|p| + 1} \lt t_{|p| + 1}$$$, where $$$p$$$ is the longest common prefix of $$$s$$$ and $$$t$$$, $$$|p|$$$ is the length of $$$p$$$, $$$s_i$$$ is the $$$i$$$-th character of string $$$s$$$, and $$$t_i$$$ is the $$$i$$$-th character of string $$$t$$$.
There are multiple test cases. The first line of the input contains an integer $$$T$$$ indicating the number of test cases. For each test case:
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2\leq n\leq 10^6$$$, $$$2\leq k\leq n$$$) indicating the total number of strings and the number of strings to be selected.
For the following $$$n$$$ lines, the $$$i$$$-th line contains a string $$$w_i$$$ ($$$1\leq |w_i|\leq 10^6$$$) consisting of lower-cased English letters.
It's guaranteed that the total length of all strings of all test cases will not exceed $$$10^6$$$.
For each test case output one line containing one string indicating the answer. Specifically, if the answer is an empty string, print EMPTY.
25 3gdcpcgdcpcpcpsuasuasuassususua3 3abc
gdcpc EMPTY
Given a convex polygon $$$P$$$ with $$$n$$$ vertices, you need to choose two vertices of $$$P$$$, so that the line connecting the two vertices will split $$$P$$$ into two smaller polygons $$$Q$$$ and $$$R$$$, both with positive area.
Let $$$d(Q)$$$ be the diameter of polygon $$$Q$$$ and $$$d(R)$$$ be the diameter of polygon $$$R$$$, calculate the minimum value of $$$(d(Q))^2 + (d(R))^2$$$.
Recall that the diameter of a polygon is the maximum distance between two points inside or on the border of the polygon.
There are multiple test cases. The first line of the input contains an integer $$$T$$$ indicating the number of test cases. For each test case:
The first line contains an integer $$$n$$$ ($$$4 \le n \le 5 \times 10^3$$$) indicating the number of vertices of the convex polygon $$$P$$$.
For the following $$$n$$$ lines, the $$$i$$$-th line contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$0 \le x_i, y_i \le 10^9$$$) indicating the $$$i$$$-th vertex of the convex polygon $$$P$$$. Vertices are given in counter-clockwise order. It's guaranteed that the area of the convex polygon is positive, and there are no two vertices with the same coordinate. It's possible that three vertices lie on the same line.
It's guaranteed that the sum of $$$n$$$ of all test cases will not exceed $$$5 \times 10^3$$$.
For each test case output one line containing one integer indicating the answer.
241 02 01 10 0610 49 75 74 56 49 3
4 44
The first sample test case is shown as follows. The diameter of smaller polygons are marked by red dashed segments. In fact, $$$(1, 0)$$$ and $$$(1, 1)$$$ are the only pair of vertices we can choose in this test case. You can't choose $$$(0, 0)$$$ and $$$(2, 0)$$$, or $$$(0, 0)$$$ and $$$(1, 1)$$$, because they can't split $$$P$$$ into two smaller polygons both with positive area.
The second sample test case is shown as follows. The diameter of smaller polygons are marked by red dashed segments.
What age is it that you are still solving traditional linear algebra problem?
You are given a prime number $$$q$$$.
Suppose $$$A$$$ and $$$B$$$ are two $$$n \times n$$$ square matrices such that $$$AB \equiv A \pmod q$$$, and each element of $$$A$$$ and $$$B$$$ is an integer from $$$0$$$ to $$$q-1$$$.
- Here, $$$S \equiv T \pmod q$$$ implies that for each $$$1 \leq i,j \leq n$$$, we have $$$S_{i,j} \equiv T_{i,j} \pmod q$$$.
Given a fixed matrix $$$B$$$ ($$$\det B \ne 0$$$), it's too easy for you to just find an arbitrary suitable matrix $$$A$$$.
Let $$$f(B)$$$ represent the number of matrices that satisfy the equation above. Your task is to calculate:
$$$$$$\sum_{B \in M_n(\mathbb F_q)} [\det B \ne 0] 3^{f(B)}$$$$$$
The answer can be quite large, you only need to output it modulo another given prime number, $$$mod$$$.
The first line of the input contains three integers $$$n$$$, $$$q$$$ and $$$mod$$$. ($$$1 \leq n \leq 10^7$$$, $$$2 \leq q \lt mod$$$, $$$10^8 \leq mod \leq 10^9+7$$$).
It is guaranteed that $$$q$$$ and $$$mod$$$ are two prime numbers.
Output a single line contains a single integer, indicating the answer modulo the given number $$$mod$$$.
2 2 1000000007
43046970
100 127 998244353
881381862
For $$$B=\left(\begin{array}{ll}0 & 1 \\ 1 & 0\end{array}\right)$$$, matrices $$$A$$$ that satisfy the condition are: $$$\left(\begin{array}{ll}0 & 0 \\ 0 & 0\end{array}\right)$$$, $$$\left(\begin{array}{ll}0 & 0 \\ 1 & 1\end{array}\right)$$$, $$$\left(\begin{array}{ll}1 & 1 \\ 0 & 0\end{array}\right)$$$, $$$\left(\begin{array}{ll}1 & 1 \\ 1 & 1\end{array}\right)$$$, totaling 4.
For $$$B=\left(\begin{array}{ll}0 & 1 \\ 1 & 1\end{array}\right)$$$, the matrices $$$A$$$ that satisfy the condition are: $$$\left(\begin{array}{ll}0 & 0 \\ 0 & 0\end{array}\right)$$$, totaling 1.
For $$$B=\left(\begin{array}{ll}1 & 0 \\ 0 & 1\end{array}\right)$$$, all matrices $$$A$$$ satisfy the condition, totaling 16.
For $$$B=\left(\begin{array}{ll}1 & 0 \\ 1 & 1\end{array}\right)$$$, matrices $$$A$$$ that satisfy the condition are: $$$\left(\begin{array}{ll}0 & 0 \\ 0 & 0\end{array}\right)$$$, $$$\left(\begin{array}{ll}0 & 0 \\ 1 & 0\end{array}\right)$$$, $$$\left(\begin{array}{ll}1 & 0 \\ 0 & 0\end{array}\right)$$$, $$$\left(\begin{array}{ll}1 & 0 \\ 1 & 0\end{array}\right)$$$, totaling 4.
For $$$B=\left(\begin{array}{ll}1 & 1 \\ 0 & 1\end{array}\right)$$$, matrices $$$A$$$ that satisfy the condition are: $$$\left(\begin{array}{ll}0 & 0 \\ 0 & 0\end{array}\right)$$$, $$$\left(\begin{array}{ll}0 & 0 \\ 0 & 1\end{array}\right)$$$, $$$\left(\begin{array}{ll}0 & 1 \\ 0 & 0\end{array}\right)$$$, $$$\left(\begin{array}{ll}0 & 1 \\ 0 & 1\end{array}\right)$$$, totaling 4.
For $$$B=\left(\begin{array}{ll}1 & 1 \\ 1 & 0\end{array}\right)$$$, the matrices $$$A$$$ that satisfy the condition are: $$$\left(\begin{array}{ll}0 & 0 \\ 0 & 0\end{array}\right)$$$, totaling 1.
Therefore, the answer is $$$3^4+3^1+3^{16}+3^4+3^4+3^1 \equiv 43046970 \pmod {(10^9+7)}$$$.
For positive integers $$$X$$$ and $$$b \geq 2$$$, define $$$f(X,b)$$$ as a sequence which describes the base-$$$b$$$ representation of $$$X$$$, where the $$$i$$$-th element in the sequence is the $$$i$$$-th least significant digit in the base-$$$b$$$ representation of $$$X$$$. For example, $$$f(6, 2) = \{0, 1, 1\}$$$, while $$$f(233, 17) = \{12, 13\}$$$.
Given four positive integers $$$x$$$, $$$y$$$, $$$A$$$ and $$$B$$$, please find two positive integers $$$a$$$ and $$$b$$$ satisfying:
- $$$2 \leq a \leq A$$$
- $$$2 \leq b \leq B$$$
- $$$f(x, a) = f(y, b)$$$
There are multiple test cases. The first line of the input contains an integer $$$T$$$ ($$$1 \leq T \leq 10^3$$$) indicating the number of test cases. For each test case:
The first line contains four integers $$$x$$$, $$$y$$$, $$$A$$$ and $$$B$$$ ($$$1 \leq x,y \leq 10^9$$$, $$$2 \leq A,B \leq 10^9$$$).
It's guaranteed that there are at most $$$50$$$ test cases satisfying $$$\max(x, y) \gt 10^6$$$.
For each test case, if valid positive integers $$$a$$$ and $$$b$$$ do not exist, output NO in one line.
Otherwise, first output YES in one line. Then in the next line, output two integers $$$a$$$ and $$$b$$$ separated by a space. If there are multiple valid answers, you can output any of them.
61 1 1000 10001 2 1000 10003 11 1000 1000157 291 5 6157 291 3 610126 114514 789 12345
YES 2 2 NO YES 2 10 YES 4 5 NO YES 779 9478
Given an undirected complete graph with $$$n$$$ vertices and $$$m$$$ triples $$$P_1, P_2, \cdots, P_m$$$ where $$$P_i = (u_i, v_i, w_i)$$$, it's guaranteed that $$$1 \leq u_i \lt v_i \leq n$$$, and for any two triples $$$P_i$$$ and $$$P_j$$$ with different indices we have $$$(u_i, v_i) \ne (u_j, v_j)$$$.
For any two vertices $$$x$$$ and $$$y$$$ in the graph ($$$1 \leq x \lt y \leq n$$$), define the weight of the edge connecting them as follows:
- If there exists a triple $$$P_i$$$ satisfying $$$u_i = x$$$ and $$$v_i = y$$$, the weight of edge will be $$$w_i$$$.
- Otherwise, the weight of edge will be $$$|x - y|$$$.
Calculate the total weight of edges in the minimum spanning tree of the graph.
There are multiple test cases. The first line of the input contains an integer $$$T$$$ ($$$1 \le T \le 10^5$$$) indicating the number of test cases. For each test case:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 10^9$$$, $$$0 \leq m \leq 10^5$$$) indicating the number of vertices in the graph and the number of triples.
For the following $$$m$$$ lines, the $$$i$$$-th line contains three integers $$$u_i$$$, $$$v_i$$$ and $$$w_i$$$ ($$$1 \leq u_i \lt v_i \leq n$$$, $$$0 \leq w_i \leq 10^9$$$) indicating the $$$i$$$-th triple. It's guaranteed that for all $$$1 \leq i \lt j \leq m$$$ we have $$$(u_i, v_i) \ne (u_j, v_j)$$$.
It's guaranteed that the sum of $$$m$$$ of all test cases will not exceed $$$5 \times 10^5$$$.
For each test case output one line containing one integer indicating the total weight of edges in the minimum spanning tree of the graph.
35 31 2 52 3 41 5 05 05 41 2 10000000001 3 10000000001 4 10000000001 5 1000000000
4 4 1000000003
The first sample test case is illustrated as follows. The minimum spanning tree is marked by red segments.
The second sample test case is illustrated as follows. The minimum spanning tree is marked by red segments.
The third sample test case is illustrated as follows. The minimum spanning tree is marked by red segments.
Given a non-negative integer sequence $$$A = a_1, a_2, \dots, a_n$$$ of length $$$n$$$, define
$$$$$$ F(A)=\max\limits_{1\leq k \lt n} ((a_1 \,\&\, a_2 \,\&\, \cdots \,\&\, a_k)+(a_{k+1} \,\&\, a_{k+2} \,\&\, \cdots \,\&\, a_n)) $$$$$$
where $$$\&$$$ is the bitwise-and operator.
You can perform the swapping operation at most once: choose two indices $$$i$$$ and $$$j$$$ such that $$$1\leq i \lt j\leq n$$$ and then swap the values of $$$a_i$$$ and $$$a_j$$$.
Calculate the maximum possible value of $$$F(A)$$$ after performing at most one swapping operation.
There are multiple test cases. The first line of the input contains an integer $$$T$$$ indicating the number of test cases. For each test case:
The first line contains an integer $$$n$$$ ($$$2\leq n\leq 10^5$$$) indicating the length of sequence $$$A$$$.
The second line contains $$$n$$$ integers $$$a_1, a_2, \cdots, a_n$$$ ($$$0\leq a_i\leq 10^9$$$) indicating the given sequence $$$A$$$.
It's guaranteed that the sum of $$$n$$$ of all test cases will not exceed $$$10^5$$$.
For each test case output one line containing one integer indicating the maximum possible value of $$$F(A)$$$ after performing at most one swapping operation.
366 5 4 3 5 661 2 1 1 2 251 1 2 2 2
7 3 3
For the first sample test case, we can swap $$$a_4$$$ and $$$a_6$$$ so the sequence becomes $$$\{6, 5, 4, 6, 5, 3\}$$$. We can then choose $$$k = 5$$$ so that $$$F(A) = (6 \,\&\, 5 \,\&\, 4 \,\&\, 6 \,\&\, 5) + (3) = 7$$$.
For the second sample test case, we can swap $$$a_2$$$ and $$$a_4$$$ so the sequence becomes $$$\{1, 1, 1, 2, 2, 2\}$$$. We can then choose $$$k = 3$$$ so that $$$F(A) = (1 \,\&\, 1 \,\&\, 1) + (2 \,\&\, 2 \,\&\, 2) = 3$$$.
For the third sample test case we do not perform the swapping operation. We can then choose $$$k = 2$$$ so that $$$F(A) = (1 \,\&\, 1) + (2 \,\&\, 2 \,\&\, 2) = 3$$$.
Let $$$m(x)$$$ be the mode of the digits in decimal representation of positive integer $$$x$$$. The mode is the largest value that occurs most frequently in the sequence. For example, $$$m(15532)=5$$$, $$$m(25252)=2$$$, $$$m(103000)=0$$$, $$$m(364364)=6$$$, $$$m(114514)=1$$$, $$$m(889464)=8$$$.
Given a positive integer $$$n$$$, DreamGrid would like to know the value of $$$(\sum\limits_{x=1}^{n} m(x)) \bmod (10^9+7)$$$.
There are multiple test cases. The first line of the input contains an integer $$$T$$$, indicating the number of test cases. For each test case:
The first line contains a positive integer $$$n$$$ ($$$1 \le n \lt 10^{50}$$$) without leading zeros.
It's guaranteed that the sum of $$$|n|$$$ of all test cases will not exceed $$$50$$$, where $$$|n|$$$ indicates the number of digits of $$$n$$$ in decimal representation.
For each test case output one line containing one integer, indicating the value of $$$(\sum\limits_{x=1}^{n} m(x)) \bmod (10^9+7)$$$.
5 9 99 999 99999 999999
45 615 6570 597600 5689830
BaoBao, one of the most famous monster hunters, wakes up in the middle of Heltion City dominated by monsters. Having troubles remembering what has happened, BaoBao decides to escape from this horrible city as soon as possible. Despite arming no weapon, he luckily puts his hand on a map in his right pocket, which contains valuable information that can possibly help him find a way out.
According to the map, Heltion City is composed of $$$n$$$ spots connected by $$$m$$$ undirected paths. Starting from spot $$$1$$$, BaoBao must head towards any of the $$$k$$$ exits of the city to escape, where the $$$i$$$-th of them is located at spot $$$e_i$$$.
However, it's not an easy task for BaoBao to escape since monsters are everywhere in the city! For all $$$1 \le i \le n$$$, $$$d_i$$$ monsters are wandering near the $$$i$$$-th spot, so right after BaoBao arrives at that spot, at most $$$d_i$$$ paths connecting the spot will be blocked by monsters and are unable for BaoBao to pass. When BaoBao leaves the $$$i$$$-th spot, the monsters will go back to their nests and the blocked paths are clear. Of course, if BaoBao comes back to the spot, at most $$$d_i$$$ paths will be again blocked by the monsters. The paths blocked each time may differ.
As BaoBao doesn't know which paths will be blocked, please help him calculate the shortest time he can escape from the city in the worst case.
There are multiple test cases. The first line of the input contains an integer $$$T$$$ (about $$$100$$$), indicating the number of test cases. For each test case:
The first line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le m \le 10^6$$$, $$$1 \le k \le n$$$), indicating the number of spots, the number of undirected paths and the number of exits of the city.
The second line contains $$$k$$$ distinct integers $$$e_1, e_2, \dots, e_k$$$ ($$$1 \le e_i \le n$$$), indicating $$$k$$$ exits of Heltion City.
The third line contains $$$n$$$ integers $$$d_1, d_2, \dots, d_n$$$ ($$$0 \le d_i \le m$$$), where $$$d_i$$$ indicates the number of monsters at the $$$i$$$-th spot.
For the following $$$m$$$ lines, the $$$i$$$-th line contains three integers $$$x_i$$$, $$$y_i$$$ and $$$w_i$$$ ($$$1 \le x_i,y_i \le n$$$, $$$x_i \neq y_i$$$, $$$1 \le w_i \le 10^4$$$), indicating an undirected edge of length $$$w_i$$$ connecting spot $$$x_i$$$ and $$$y_i$$$.
It's guaranteed that the total sum of $$$n$$$ will not exceed $$$10^6$$$ and the total sum of $$$m$$$ will not exceed $$$3 \times 10^6$$$.
For each case output one line containing one integer. If BaoBao can get to some exit in the worst case, output the shortest possible time cost; Otherwise if BaoBao cannot get to any exit in the worst case, output "-1" (without quotes) instead.
2 3 4 1 3 1 1 1 1 2 1 1 2 2 2 3 1 2 3 2 3 2 2 2 3 2 0 0 1 2 1 1 3 1
4 -1
There is a circle in the plane. Both the coordinates of the center and the radius are unknown.
Chiaki found three distinct points A, B and C in the plane. And she also knows the shortest distance from each point to the circumference.
Chiaki would like to find the smallest circle according to above information.
Note that in general, a circle with infinite radius is a line. But in this problem, line is not considered as a circle.
There are multiple test cases. The first line of input contains an integer T (1 ≤ T ≤ 2 × 105), indicating the number of test cases. For each test case:
The first line contains three integers xa, ya and da ( - 100 ≤ xa ≤ 100, ya = 0, 1 ≤ da ≤ 100) denoting the coordinates of A and the shortest distance to the circumference.
The second line contains three integers xb, yb and db ( - 100 ≤ xb ≤ 100, yb = 0, 1 ≤ db ≤ 100) denoting the coordinates of B and the shortest distance to the circumference.
The third line contains three integers xc, yc and dc ( - 100 ≤ xc, yc, dc ≤ 100, dc ≠ 0) denoting the coordinates of C and the shortest distance to the circumference.
If the distance is equal to 0, the point is on the circumference. If distance is greater than 0, the point is inside the circle. If distance is less than 0, the point is outside the circle and the shortest distance is the absolute value.
It is guaranteed that the minimum possible radius of the circle is at most 104.
For each test case, if there are infinite possible circles, output - 1 in a single line. If there is no such circle, output 0 in a single line. Otherwise, output an integer m and a real number r in a single line separated by one space denoting the number of possible circles and the radius of the smallest circle. You answer will be accepted if the relative error of your answer is no more than 10 - 6.
2
0 0 1
3 0 2
10 2 2
0 0 1
3 0 2
10 2 -2
2 10.327329213469
2 5.341730785440
The image below shows the sample.
With the construction and development of Guangdong, more and more people choose to come to Guangdong to start a new life. In a recently built community, there will be $$$n$$$ people moving into $$$m$$$ houses which are arranged in a row. The houses are numbered from $$$1$$$ to $$$m$$$ (both inclusive). House $$$u$$$ and $$$v$$$ are neighboring houses, if and only if $$$|u-v|=1$$$. We need to assign each person to a house so that no two people will move into the same house. If two people move into a pair of neighboring houses, they will become neighbors of each other.
Some people like to have neighbors while some don't. For the $$$i$$$-th person, if he has at least one neighbor, his happiness will be $$$a_i$$$; Otherwise if he does not have any neighbor, his happiness will be $$$b_i$$$.
As the planner of this community, you need to maximize the total happiness.
There are multiple test cases. The first line of the input contains an integer $$$T$$$ indicating the number of test cases. For each test case:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 5 \times 10^5$$$, $$$1 \le m \le 10^9$$$, $$$n \le m$$$) indicating the number of people and the number of houses.
For the following $$$n$$$ lines, the $$$i$$$-th line contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i, b_i \le 10^9$$$) indicating the happiness of the $$$i$$$-th person with and without neighbors.
It's guaranteed that the sum of $$$n$$$ of all test cases will not exceed $$$10^6$$$.
For each test case output one line containing one integer indicating the maximum total happiness.
34 51 100100 1100 1100 12 21 101 102 3100 501 1000
400 2 1050
For the first sample test case, the optimal strategy is to let person $$$1$$$ move into house $$$1$$$ and let person $$$2$$$ to $$$4$$$ move into house $$$3$$$ to $$$5$$$. Thus, person $$$1$$$ have no neighbors while person $$$2$$$ to $$$4$$$ have neighbors. The answer is $$$100 + 100 + 100 + 100 = 400$$$. Of course, we can also let person $$$2$$$ to $$$4$$$ move into house $$$1$$$ to $$$3$$$ and let person $$$1$$$ move into house $$$5$$$. This will also give us $$$400$$$ total happiness.
For the second sample test case, as there are only $$$2$$$ houses, person $$$1$$$ and $$$2$$$ have to be neighbors. The answer is $$$1 + 1 = 2$$$.
For the third sample test case, the optimal strategy is to let person $$$1$$$ move into house $$$1$$$ and let person $$$2$$$ move into house $$$3$$$. Thus, both of them have no neighbors. The answer is $$$50 + 1000 = 1050$$$.
There is a sequence of length $$$n$$$. At the beginning, all elements in the sequence equal to $$$0$$$. There are also $$$m$$$ operations, where the $$$i$$$-th operation will change the value of the $$$l_i$$$-th element in the sequence to $$$x_i$$$, and also change the value of the $$$r_i$$$-th element in the sequence to $$$y_i$$$. Each operation must be performed exactly once.
Find the optimal order to perform the operations, so that after all operations, the sum of all elements in the sequence is maximized.
There are multiple test cases. The first line of the input contains an integer $$$T$$$ indicating the number of test cases. For each test case:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n, m \leq 5 \times 10^5$$$) indicating the length of the sequence and the number of operations.
For the following $$$m$$$ lines, the $$$i$$$-th line contains four integers $$$l_i$$$, $$$x_i$$$, $$$r_i$$$ and $$$y_i$$$ ($$$1 \leq l_i \lt r_i \leq n$$$, $$$1 \leq x_i,y_i \leq 2$$$) indicating the $$$i$$$-th operation.
It's guaranteed that neither the sum of $$$n$$$ nor the sum of $$$m$$$ of all test cases will exceed $$$5 \times 10^5$$$.
For each test case, first output one line containing one integer, indicating the maximum sum of all elements in the sequence after all operations. Then output another line containing $$$m$$$ integers $$$a_1, a_2, \cdots, a_m$$$ separated by a space, indicating the optimal order to perform the operations, where $$$a_i$$$ is the index of the $$$i$$$-th operation to be performed. Each integer from $$$1$$$ to $$$m$$$ (both inclusive) must appear exactly once. If there are multiple valid answers, you can output any of them.
24 41 1 2 23 2 4 11 2 3 22 1 4 14 23 2 4 11 2 3 1
7 4 1 3 2 5 2 1
For the first sample test case, after performing operations $$$4, 1, 3, 2$$$ in order, the sequence becomes $$$\{2, 2, 2, 1\}$$$. The sum of all elements is $$$7$$$.
For the second sample test case, after performing operations $$$2, 1$$$ in order, the sequence becomes $$$\{2, 0, 2, 1\}$$$. The sum of all elements is $$$5$$$.