Given a sequence $A_{1}, A_{2}, \dots, A_{N}$, a subsequence $B_1, B_2, \dots, B_M$ is called an increasing multiple subsequence of $A$ if it satisfies the following conditions:

• $1 \le M \le N$
• $\forall 1 \le i < M$, $B_i \mid B_{i+1}$ (where $B_i$ divides $B_{i+1}$)

There is a sequence $A$ of length $N$ initialized as $A_{1}, A_{2}, \dots, A_{N}$, and $Q$ operations are performed on $A$. The four types of operations are as follows:

• 0 x: Insert a number $x$ at the leftmost end of sequence $A$.
• 1 x: Insert a number $x$ at the rightmost end of sequence $A$.
• 2: Remove the number at the leftmost end of sequence $A$.
• 3: Remove the number at the rightmost end of sequence $A$.

After the initialization of sequence $A$ and after each operation, calculate the length of the longest increasing multiple subsequence of $A$, denoted as MaxLen, and the number of distinct starting elements of all increasing multiple subsequences of length MaxLen, denoted as Cnt. Output MaxLen and Cnt.

To significantly reduce the difficulty, it is guaranteed that at any moment the sequence $A$ is non-empty, its elements are distinct, and they are all positive integers between $1$ and $M$. Each number will be inserted at most $C$ times.

Input

The input is read from standard input.

The first line contains three positive integers $N, M, Q$, where $1 \le N \le 10^{5}$, $N \le M \le 10^{6}$, and $0 \le Q \le 10^{5}$.

The second line contains $N$ positive integers $A_1, A_2, \dots, A_N$, where $1 \le A_i \le M$, and all elements in $A$ are distinct.

The next $Q$ lines each contain an operation in the format 0 x, 1 x, 2, or 3, as described above.

Output

The output is written to standard output.

Output $Q+1$ lines. After the initialization and after each operation on sequence $A$, output the length of the longest increasing multiple subsequence MaxLen and the number of distinct starting elements Cnt, separated by a space.

Examples

Input 1

5 10 10
1 2 5 9 10
2
1 7
3
3
0 8
3
2
1 8
3
0 3

Output 1

3 1
2 2
2 2
2 2
1 3
1 4
1 3
1 2
2 1
1 2
1 3

Note 1

The table below shows the sequence $A$ and the corresponding answers. The // symbol separates different starting elements for the longest increasing multiple subsequences.

Constraints

For all data, $1 \le N \le 10^{5}$, $N \le M \le 10^{6}$, $0 \le Q \le 10^{5}$, $1 \le A_i \le M$, and $C = 10$.

The table below shows special constraints for certain test cases. "Only 1" means only operations of type 1 x are present, and so on.