Longest Divisible Subsequence and Its Starting Count

After a series of intense events and interviews, you are now facing an exam that tests your skills in dynamic programming. You are given a sequence (A_1, A_2, \ldots, A_N) of distinct positive integers (each in the range (1 \ldots M)). A subsequence (B_1, B_2, \ldots, B_M) (with (1 \le M \le N)) of (A) is called an increasing divisible subsequence if for every (1 \le i < M) it holds that (B_i) divides (B_{i+1}) (i.e. (B_{i+1} \equiv 0 ;(\bmod; B_i))).

Initially, you are given the sequence (A). Then there are (Q) operations modifying (A}. The operations are as follows:

• 0 x: Insert the number \(x\) at the left end of \(A\).
• 1 x: Insert the number \(x\) at the right end of \(A\).
• 2: Remove the number at the left end of \(A\).
• 3: Remove the number at the right end of \(A\).

After the initialization and after each operation, you are to compute the following for the current sequence (A):

1. \(MaxLen\): The length of the longest increasing divisible subsequence in \(A\).
2. \(Cnt\): The number of distinct starting numbers among all increasing divisible subsequences of length \(MaxLen\).

It is guaranteed that at any moment the sequence (A) is non-empty, its elements are distinct, and every element is a positive integer between (1) and (M). Also, the same number is inserted at most (C) times. Your task is to output (MaxLen) and (Cnt) for the initial sequence and after each operation.

Note on Divisibility: For any two numbers \(a\) and \(b\), the condition \(a\mid b\) means that \(b \bmod a = 0\).

inputFormat

The first line contains two integers (N) and (Q) ( (1 \le N, Q \le \text{upper bound})), the initial length of the sequence and the number of operations. The second line contains (N) space-separated integers representing the initial sequence (A). Each of the following (Q) lines represents an operation in one of the following forms:

• 0 x
• 1 x
• 2
• 3

It is guaranteed that the sequence is never empty after any operation and that all numbers are distinct and lie between (1) and (M).

outputFormat

For the initial sequence and after each operation, output a line with two integers: (MaxLen) and (Cnt), separated by a space.

sample

3 3
1 2 3
1 6
0 2
3

2 1
3 1
3 2
2 2