segment 2

Hân là một học sinh rất thích các cấu trúc dữ liệu. Giải quyết các bài toán truy vấn là thú vui lớn nhất của cậu, chỉ xếp sau anime. Một hôm, sau khi làm đủ 100 bài toán truy vấn trong một ngày, Hân cảm thấy các bài tập chưa đủ khó và quyết định tự nghĩ ra một bài toán khác để thách thức bản thân. Bài toán của Hân như sau:

Ban đầu Hân có một số nguyên \(x\), giá trị ban đầu bằng \(1\). Cậu có \(Q\) truy vấn như sau:

• \(1\ val:\) \(x = x * val\).
• \(2\ pos:\) \(x = x / val\), với \(val\) là giá trị xuất hiện ở truy vấn thứ \(pos\). Đảm bảo rằng truy vấn thứ \(pos\) là truy vấn loại 1 và mỗi thao tác loại 1 bị chia tối đa một lần.

Với mỗi truy vấn, in ra kết quả của số \(x\) khi chia lấy dư cho \(M\).

Vì đã code quá 180 phút nên Hân không còn đủ cảm hứng để giải quyết bài toán này. Bạn hãy giúp Hân nhé.

Input:

• Dòng đầu tiên chứa số nguyên \(t\), là số lượng testcases \((1 \leq t \leq 5)\)
• Với mỗi testcase, dòng đầu tiên chứa 2 số nguyên \(Q, M \ (1 \leq Q \leq 10^5 ,\ 1 \leq M \leq 10^9)\)
• \(Q\) dòng tiếp theo, dòng \(i\) thể hiện truy vấn thứ \(i\).
  Truy vấn loại 1 có dạng \(1\ val\ (1 \leq val \leq M)\).
  Truy vấn loại 2 có dạng \(2\ pos\ (1 \leq pos \leq Q)\)

Output:

Với mỗi truy vấn, in ra giá trị của \(x\) khi chia lấy dư cho \(M\).

Ví dụ:

**Input: **

1
10 1000
1 2
2 1
1 2
1 10
2 3
2 4
1 6
1 7
1 12
2 7

**Output: **

2
1
2
20
10
1
6
42
504
84

Ràng buộc:

• Subtask 1: \(\ 1 \leq Q \leq 500\)
• Subtask 2: \(\ 1 \leq Q \leq 10^5\)

Cho một tập hợp rỗng, bạn sẽ lần lượt thực hiện N thao tác. Có hai loại thao tác được thực hiện:

• Thao tác 1 có dạng (1, \(x\)) : thêm số \(x\) vào tập hợp.
• Thao tác 2 có dạng (2, \(x\)): loại bỏ một số \(x\) ra khỏi tập hợp, dữ liệu luôn đảm bảo tồn tại ít nhất một số \(x\) trước khi thực hiện thao thao tác này.

Sau mỗi lần thực hiện thao tác, hãy đưa ra ước chung lớn nhất của tập hợp này. Với trường hợp tập hợp con rỗng hãy in ra số 1.

Input

• Dòng đầu tiên một số tự nhiên \(N\) (\(1 \leq N \leq 1000\)).
• \(N\) dòng tiếp theo, mỗi dòng là gồm 2 số \(t\) và \(x\) với \(t\) là loại thao tác và \(x\) là số cần được xử lí (\(1 \leq t \leq 2\), \(1 \leq x \leq 10^{9}\)).

Output

• Gồm \(N\) dòng là ước chung lớn nhất của tập hợp sau mỗi lần thực hiện một thao tác.

Example

6  
1 8     
1 12     
1 10     
1 8     
2 8     
2 8 

8     
4     
2     
2     
2     
2

Cho một tập hợp rỗng, bạn sẽ lần lượt thực hiện N thao tác. Có hai loại thao tác được thực hiện:

• Thao tác 1 có dạng \((1, x)\) : thêm số \(x\) vào tập hợp.
• Thao tác 2 có dạng \((2, x)\): loại bỏ một số \(x\) ra khỏi tập hợp, dữ liệu luôn đảm bảo tồn tại ít nhất một số \(x\) trước khi thực hiện thao thao tác này.

Sau mỗi lần thực hiện thao tác, hãy đưa ra ước chung lớn nhất của tập hợp này. Với trường hợp tập hợp con rỗng hãy in ra số \(1\).

Input

• Dòng đầu tiên một số tự nhiên \(N\) (\(1 \leq N \leq 10^{5}\)).
• \(N\) dòng tiếp theo, mỗi dòng là gồm 2 số \(t\) và \(x\) với \(t\) là loại thao tác và \(x\) là số cần được xử lí (\(1 \leq t \leq 2\), \(1 \leq x \leq 10^{9}\)).

Output

• Gồm \(N\) dòng là ước chung lớn nhất của tập hợp sau mỗi lần thực hiện một thao tác.

Example

6  
1 8 
1 12 
1 10 
1 8 
2 8 
2 8 

8 
4 
2 
2 
2 
2

Trong một cuộc thi thả diều, ban giám khảo căn cứ vào độ cao của mỗi chiếc diều đạt được khii thả lên trời và xếp hạng cho chiếc diều đó theo một cách đặc biệt: Những chiếc diều không được thả cùng một lúc, mà theo trình tự từng chiệc một. Khi một chiếc diều được thả lên trời, ban giám khảo sẽ căn cứ vào độ cao của chiếc diều và xếp hạng cho chiếc diều đó bằng cách so độ cao của nó với độ cao của những chiếc diều đã thả trước đó. Ví dụ, giả sử độ cao của sáu chiếc diều theo thứ tự được thả như sau:
\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (78,24,68,40,39,89)\)

Chiếc đầu tiên xếp hạng \(1\) vì trước nó chưa có chiếc diều nào được thả. Chiếc thứ hai xếp hạng \(2\) vì \(24 < 78\). Chiếc thứ ba cũng xếp hạng \(2\) vì \(24 < 68 < 78\). Chiếc thứ tư xếp hạng \(3\) vì \(24 < 40 < 68 < 78\), chiếc thứ năm xếp hạng \(4\) vì \(24 < 39 < 40 < 68 < 78\) và chiếc cuối cùng xếp hạng nhất với độ cao \(89\) và \(24 < 39 < 40 < 68 < 78 < 89\). Như vậy trình tự dãy số xếp hạng được công bố sẽ là: \((1,2,2,3,4,1)\). Tóm lại hạng của một chiếc diều bằng số diều đã thả cao hơn nó cộng thêm \(1\).

Yêu cầu:

• Có \(n\) chiếc diều lần lượt được thả lên trời, em hãy cho biết dãy số biểu diễn giá trị xếp hạng của \(n\) chiếc diều.

Input

• Dòng đầu một số nguyên \(n \le 10^5\) cho biết số chiếc diều tham gia dự thi.
• \(n\) dòng tiếp theo, mỗi dòng ghi một số nguyên dương \(\le 10^9\) mô tả độ cao của một chiếc diều, theo thứ tự mà nó được thả lên.

Output

• Gồm \(n\) dòng: dòng thứ \(i\) ghi số nguyên biểu diễn giá trị xếp hạng của chiếc diều thứ \(i\) tại thời điểm nó được thả lên.

Example

6
78
24
68
40
39
89

1
2
2
3
4
1

Cho \(n\) là một số nguyên dương và \(x = (x_1, x_2, ..., x_n)\) là một hoán vị của dãy số \((1, 2, ..., n)\). Với \(\forall i: 1 \le i \le n\), gọi \(t_i\) là số phần tử đứng trước giá trị \(i\) mà lớn hơn \(i\) trong dãy \(x\). Khi đó dãy \(t = (t_1, t_2,..., t_n)\) được gọi là dãy nghịch thế của \(x = (x_1, x_2, ..., x_n)\)

Ví dụ: Với \(n = 6\)

Dãy \(x = (3, 2, 1, 6, 4, 5)\) thì dãy nghịch thế của nó là \(t = (2, 1, 0, 1, 1, 0)\)

Dãy \(x = (1, 2, 3, 4, 5, 6)\) thì dãy nghịch thế của nó là \(t = (0, 0, 0, 0, 0, 0)\)

Dãy \(x = (6, 5, 4, 3, 2, 1)\) thì dãy nghịch thế của nó là \(t = (5, 4, 3, 2, 1, 0)\)

Input

Vào từ file văn bản IVECTOR.INP gồm:

• Dòng 1: Chứa số nguyên dương \(n \le 10^5\)
• Dòng 2: Chứa dãy hoán vị \(x\) gồm \(n\) số \(x_1, x_2, ..., x_n\)
• Dòng 3: Chứa dãy nghịch thế \(t\): gồm \(n\) số \(t_1, t_2,..., t_n\)

Output

Ghi ra file văn bản IVECTOR.OUT gồm:

• Dòng 1: Ghi lần lượt từng phần tử của dãy nghịch thế của \(x\)
• Dòng 2: Ghi lần lượt từng phần tử của dãy hoán vị của \(t\)

Example

6
1 2 3 4 5 6
2 1 0 1 1 0

0 0 0 0 0 0
3 2 1 6 4 5