Before mining radium on Mars is possible, a special satellite was launched to measure the radioactivity level on the surface of the planet.
The plateau (flat piece of land) Meridian can be represented as a rectangle with $$$n \times m$$$ unit squares. We denote the $$$j$$$-th square in the $$$i$$$-th row as $$$(i, j)$$$. Both rows and columns are numbered starting from $$$1$$$.
As a result of scanning the plateau, we know the level of radioactivity for each unit square. For the unit square $$$(i, j)$$$ it is a positive integer $$$a_{ij}$$$. The accuracy of the measurements is so high that all numbers $$$a_{ij}$$$ are different. A unit square is considered suitable for the extraction of radium if its value $$$a_{ij}$$$ is the maximum in the $$$i$$$-th row and the maximum in the $$$j$$$-th column.
The satellite then recorded $$$q$$$ updates in the radioactivity. The $$$k$$$-th update changed the value $$$a_{r_k c_k}$$$ to a stricly greater value. (The radioactivity on Mars tends to increase.) The new value stays in this unit square forever unless a new update changes the same unit square. After each update, all values $$$a_{ij}$$$ are guaranteed to still remain different.
Your task is to write a program that, given the initial values $$$a_{ij}$$$ and the list of updates, after each update determines the number of unit squares that are suitable for the extraction of radium.
The first line of the input contains three positive integers $$$n$$$, $$$m$$$ and $$$q$$$ ($$$1 \le n \cdot m \le 200\,000$$$, $$$1 \le q \le 200\,000$$$). Please note that the first constraint is for the product $$$n \cdot m$$$, not for the number of rows and columns separately.
Each of the following $$$n$$$ lines contains $$$m$$$ positive integers. The $$$j$$$-th integer in the $$$i$$$-th of those lines specifies the initial value $$$a_{ij}$$$ ($$$1 \le a_{ij} \le 10^7$$$, all $$$a_{ij}$$$ are different).
The following $$$q$$$ lines describe the updates. The $$$k$$$-th of them contains three integers $$$r_k$$$, $$$c_k$$$ and $$$x_k$$$, that denote the change in the level of radioactivity in the unit square $$$(r_k, c_k)$$$ to a new value $$$x_k$$$ ($$$1 \le r_k \le n$$$, $$$1 \le c_k \le m$$$, $$$1 \le x_k \le 10^7$$$). It is guaranteed that $$$x_k$$$ is strictly greater than the previous level of radioactivity in this square, and that all the radioactivity levels are different after each update.
The output should consist of $$$q$$$ lines. In the $$$k$$$-th line, print a single integer — the number of unit squares suitable for the extraction of radium after the $$$k$$$-th update.
$$$$$$ \begin{array}{|c|c|c|c|} \hline \text{Subtask} & \text{Points} & \text{Constraints} & \text{Dependencies} \\ \hline 1 & 25 & 1 \le n \cdot m \le 100, 1 \le q \le 100 & 0 \\ \hline 2 & 25 & 1 \le n \cdot m \le 5000, 1 \le q \le 5000 & 0, 1 \\ \hline 3 & 25 & 1 \le n, m \le 400, 1 \le q \le 200\,000 & 0, 1 \\ \hline 4 & 25 & 1 \le n \cdot m \le 200\,000, 1 \le q \le 200\,000 & 0, 1, 2, 3 \\ \hline \end{array}$$$$$$
You will get points for a group if you pass all tests in this group and all groups listed in the dependencies. The group $$$0$$$ denotes the sample test(s) from the statement.
2 3 3 1 4 3 6 5 2 2 2 9 1 3 5 2 2 10
1 2 2
Some telecommunications company plans to simultaneously introduce two innovative smartphones to the market. These smartphones will be called ,,Innophone" and ,,Innophone Plus". The devices are ready for production, but there is one more thing the company management needs to decide about – the optimal price for each type of smartphone.
The company hired analysts to analyze the market. They conducted a study in which they built the following model. There are $$$n$$$ potential buyers of innovative smartphones. The $$$i$$$-th buyer uses the following algorithm, characterized by two numbers $$$a_i$$$ and $$$b_i$$$ ($$$a_i \geq b_i$$$):
- If the price of ,,Innophone Plus" is at most $$$a_i$$$, he buys ,,Innophone Plus".
- Otherwise, if the price of ,,Innophone" is at most $$$b_i$$$, he buys ,,Innophone".
- Otherwise, he doesn't buy anything.
The company wants to set the prices of ,,Innophone" and ,,Innophone Plus" in such a way that both prices are integers, the price of ,,Innophone" is not greater than the price of ,,Innophone Plus", and the total value of sold phones is the highest.
Write a program that finds the maximum possible total value of the sold smartphones, i.e. the total amount of money the buyers will pay.
The first line of the input contains an integer $$$n$$$ ($$$1 \leq n \leq 150\,000$$$) — the number of potential buyers.
The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$0 \leq b_i \leq a_i \leq 10^9$$$) — the parameters used in the algorithm of the $$$i$$$-th potential buyer.
Print a single line — the maximum possible total value of sold smartphones.
$$$$$$ \begin{array}{|c|c|c|c|} \hline \text{Subtask} & \text{Points} & \text{Constraints} & \text{Dependencies} \\ \hline 1 & 9 & n \le 100; b_i \le a_i \le 100 & 0 \\ \hline 2 & 10 & n \le 300 & 0, 1 \\ \hline 3 & 16 & n \le 3000 & 0, 1, 2 \\ \hline 4 & 11 & n \le 10^5; b_i = 0 & \\ \hline 5 & 16 & n \le 10^5; a_i = b_i & \\ \hline 6 & 7 & n \le 50\,000 & 0 - 3 \\ \hline 7 & 7 & n \le 75\,000 & 0 - 3, 6 \\ \hline 8 & 8 & n \le 100\,000 & 0 - 7 \\ \hline 9 & 8 & n \le 125\,000 & 0 - 8 \\ \hline 10 & 8 & n \le 150\,000 & 0 - 9 \\ \hline \end{array}$$$$$$
You will get points for a group if you pass all tests in this group and all groups listed in the dependencies. The group $$$0$$$ denotes the sample test(s) from the statement.
5 80 20 60 50 40 40 15 10 70 30
220
1 50 0
50
In the first sample test, the optimal prices of ,,Innophone" and ,,Innophone Plus" are $$$40$$$ and $$$70$$$ respectively. The first and fifth buyer will buy ,,Innophone Plus", while the second and third buyer will buy ,,Innophone". The fourth buyer will not buy anything. The total value of sold smartphones is then $$$70+40+40+0+70=220$$$.
In the second sample test, you need to set the price of ,,Innophone Plus" to $$$50$$$. The price of ,,Innophone" doesn't matter.
Scientists in an IT company developed a quantum supercomputer. The prototype contains $$$n \times m$$$ quantum processors, arranged in a grid with $$$n$$$ rows and $$$m$$$ columns, both numbered starting from $$$1$$$. We denote the processor in the $$$j$$$-th cell of the $$$i$$$-th row as $$$(i, j)$$$.
After scientists have launched the quantum supercomputer, a failure in the power supply damaged a portion of the processors. Researchers are left with only $$$k$$$ working processors.
A piece of important information is initially in the memory of the processor $$$(1, 1)$$$ and it needs to be transferred to the processor $$$(n, m)$$$, where the output device is located. Transferring information from one processor to another requires quantum teleportation. The peculiarity of quantum teleportation lies in the fact that with increasing distance there is instability, requiring additional energy. Therefore, the transfer of information from the processor $$$(x_i, y_i)$$$ to the processor $$$(x_j, y_j)$$$ requires $$$2^{\max(|x_i - x_j|, |y_i - y_j|)}$$$ units of energy. Scientists want to transfer the information from the processor $$$(1, 1)$$$ to the processor $$$(n, m)$$$, spending the minimum possible amount of energy. They can use only working processors.
Your task is to write a program that, given the positions of working processors, determines how to transfer the data from $$$(1, 1)$$$ to $$$(n, m)$$$, spending the minimum possible amount of energy.
The first line of the input contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ — the number of rows and columns in the grid and the number of processors that survived the power outage ($$$2 \le n, m, k \le 10\,000$$$).
The $$$i$$$-th of the following $$$k$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ — the row and column number of the $$$i$$$-th working processor ($$$1 \le x_i \le n$$$, $$$1 \le y_i \le m$$$).
It is guaranteed that $$$(x_1, y_1) = (1, 1)$$$, $$$(x_k, y_k) = (n, m)$$$. The given $$$k$$$ processors are in different cells of the grid.
The first line of the output should contain an integer $$$L$$$ — the number of processors that will be used in the transmission of the information.
The second line should contain $$$L$$$ integers — the indices of processors in the order in which they will obtain the information. The first index must be $$$1$$$ and the last one must be $$$k$$$.
If there are several ways to achieve the minimum possible total amount of energy spent, you can output any of them.
$$$$$$ \begin{array}{|c|c|c|c|} \hline \text{Subtask} & \text{Points} & \text{Constraints} & \text{Dependencies} \\ \hline 1 & 21 & 2 \le n, m, k \le 20 & 0 \\ \hline 2 & 13 & 2 \le n, m, k \le 500 & 0, 1 \\ \hline 3 & 33 & 2 \le n, m, k \le 10\,000; x_i \neq x_j; y_i \neq y_j & \\ \hline 4 & 33 & 2 \le n, m, k \le 10\,000 & 0 - 4 \\ \hline \end{array}$$$$$$
You will get points for a group if you pass all tests in this group and all groups listed in the dependencies. The group $$$0$$$ denotes the sample test(s) from the statement.
4 5 3 1 1 2 3 4 5
3 1 2 3
5 6 9 1 1 4 3 4 6 2 5 3 1 3 3 3 6 5 4 5 6
5 1 6 2 8 9
Modeling biological processes is one of the most important tasks in modern computer science. Recently, biologists have found $$$n$$$ viruses, each of which was assigned a unique code number from $$$1$$$ to $$$n$$$. A virus has the ability to integrate into the cells of other organisms. Initially, at the disposal of scientists, there are $$$n$$$ cells numbered from $$$1$$$ to $$$n$$$. The cell $$$i$$$ is infected with the virus $$$i$$$. Each cell can be infected with only one virus.
For each cell, the scientists know the level of susceptibility of this cell to each of the viruses, i.e. how easy it is for each virus to infect this cell. This is described by a permutation of code numbers of viruses.
Virus-infected cells can attack each other. If the cell $$$i$$$ is now infected with the virus $$$a$$$, it can be attacked by the virus $$$b$$$ from another cell, assuming that $$$b$$$ is before $$$a$$$ in the susceptibility permutation of the cell $$$i$$$. It doesn't matter from which cell the virus $$$b$$$ comes. As a result of such an attack, the cell $$$i$$$ becomes infected with the virus $$$b$$$.
For example, if the cell $$$i$$$ has permutation $$$(2, 3, 4, 1)$$$ and is now infected with the virus $$$1$$$, and some other cell $$$j$$$ is infected with the virus $$$3$$$, this virus can attack the cell $$$i$$$ – because $$$3$$$ is before $$$1$$$ in the permutation of the attacked cell $$$i$$$. After that, both cells $$$i$$$ and $$$j$$$ are infected with the virus $$$3$$$.
As an experiment, the scientists placed all the $$$n$$$ cells in a closed environment, causing cells to attack each other at random. The experiment ends when no virus can attack another cell anymore.
The scientists call the virus $$$i$$$ stable if it must survive the process, and they call the virus $$$i$$$ viable if it's possible it will survive the process.
More formally, the virus $$$i$$$ is stable if it remains in at least one cell at the end of the process after every possible sequence of attacks. The virus $$$i$$$ is viable if it remains in at least one cell at the end of the process after some possible sequence of attacks.
The scientists will want to know either which viruses are stable or which viruses are viable. Write a program that takes the description of the susceptibility of cells and the type of the question, and determines all the viruses with the given property (stable or viable).
The first line of the input contains an integer $$$n$$$ — the number of viruses ($$$1 \le n \le 500$$$). This is also the number of cells.
The following $$$n$$$ lines describe the susceptibility of cells. The $$$i$$$-th line contains a permutation of numbers from $$$1$$$ to $$$n$$$ — the susceptibility permutation of the $$$i$$$-th cell.
The last line contains the number $$$p$$$ that specifies the property that is interesting for the scientists. The value $$$p = 1$$$ means you need to identify all stable viruses, while $$$p = 2$$$ means you need to identify all viable viruses.
The first line of the output should contain an integer $$$k$$$ — the number of viruses with the given property ($$$0 \le k \le n$$$).
The second line should contain $$$k$$$ integers — the code numbers of viruses that have this property. The numbers should be displayed in ascending order.
$$$$$$ \begin{array}{|c|c|c|c|} \hline \text{Subtask} & \text{Points} & \text{Constraints} & \text{Dependencies} \\ \hline 1 & 11 & 1 \le n \le 5; p = 1 & \\ \hline 2 & 21 & 1 \le n \le 500; p = 1 & 1 \\ \hline 3 & 22 & 1 \le n \le 5 & 0, 1 \\ \hline 4 & 31 & 1 \le n \le 50 & 0 - 3 \\ \hline 5 & 15 & 1 \le n \le 500 & 0 - 4 \\ \hline \end{array}$$$$$$
You will get points for a group if you pass all tests in this group and all groups listed in the dependencies. The group $$$0$$$ denotes the sample test(s) from the statement.
2 1 2 2 1 1
2 1 2
2 1 2 2 1 2
2 1 2
2 2 1 1 2 1
0
2 2 1 1 2 2
2 1 2
2 1 2 1 2 1
1 1
2 1 2 1 2 2
1 1
4 3 2 4 1 1 4 2 3 3 1 2 4 1 4 2 3 1
1 3
4 3 2 4 1 1 4 2 3 3 1 2 4 1 4 2 3 2
3 1 3 4
In two first sample tests, there are two viruses and the susceptibility permutations are $$$(1, 2)$$$ and $$$(2, 1)$$$ for the cell $$$1$$$ and the cell $$$2$$$ respectively. The virus $$$1$$$ is initially in the cell $$$1$$$ and it can't attack the cell $$$2$$$ (infected by the virus $$$2$$$) because the susceptibility permutation of the cell $$$2$$$ has the virus $$$2$$$ first. Similarly, the virus $$$2$$$ can't attack the cell $$$1$$$. The experiment is terminated immediately because no attack is possible. Hence, both viruses are stable and viable.
In the third and fourth sample, each of the two cells can be overtaken by the other virus. The experiment will end after one attack, and either the virus $$$1$$$ will be in both cells or the virus $$$2$$$ will be in both cells. No virus is stable, but both are viable.