Azurit Contest (Div 2)

Cho một dãy \(a\) gồm \(N\) số nguyên, được đánh số từ 1 đến \(N\), số thứ \(i\) có giá trị là \(a_i\) ban đầu tất cả các số đều có giá trị bằng 0. Ta có \(Q\) thao tác. Có hai loại thao tác

• Loại 1: Gồm hai số \(i\), \(v\): gán \(a_i = v\)
• Loại 2: Gồm hai số \(l\), \(r\): trả về số có giá trị lớn nhất trong đoạn từ \(l\) đến \(r\).

Input

• Dòng đầu tiền gồm 2 hai số nguyên dương \(N\), \(Q\) (\(N, Q \leq 2000\))
• Dòng thứ hai gồm \(N\) số, là giá trị ban đầu của dãy \(a\)
• \(Q\) dòng tiếp theo mỗi dòng là gồm 3 số, số đầu tiên là \(t\) (\(1 \leq t \leq 2\)), là loại thao tác của thao tác hiện tại. Nếu \(t = 1\), hai số tiếp theo sẽ là \(i\) và \(v\) (\(1 \leq i \leq N\), \(1 \leq v \leq 10^{9}\)). Nếu \(t = 2\), hai số tiếp theo sẽ là \(l\) và \(r\) \((1 \leq l \leq r \leq n)\).

Output

• Dòng nhiều dòng là đáp án cho các thao tác loại 2, mỗi số in trên một dòng.

Example

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

5    
6    
4
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

Tại một thời điểm nào đó trong tương lai, lúc này du lịch vũ trụ đang rất phát triển. Có \(N\) hành tinh đang được khai thác để du lịch. Hai hành tinh \(u\) và \(v\) có thể đi lại trực tiếp tới nhau bằng \(N - 1\) đường đi hai chiều đặc biệt, chi phí để sử dụng các đường đi này là 1 lqdcoin (đơn vị tiền tệ tại thời điểm này). Các đường đi được xây dựng sao cho luôn đảm bảo tồn tại cách đi giữa hai hành tinh bất kỳ.

Ngoài cách sử dụng các đường đi đặc biệt để đi lại, người ta đã tạo ra một cách đi khác để có thêm lựa chọn cho khách du lịch, đó là sử dụng những cánh cổng không gian, những cánh cổng này sẽ giúp cho một người đang đứng tại hành tinh \(u\) có thể dịch chuyển ngay lập tức tới một hành tinh bất kỳ. Tuy nhiên vì chi phí để chế tạo những cánh cổng này rất cao nên nhà đầu tư quyết định chỉ cho xây dựng cánh cổng ở một vài hành tinh. Ngoài ra nếu muốn sử dụng cánh cổng để di chuyển, khách du lịch phải trả thêm tiền, chi phí cho việc dịch chuyển giữa các cánh cổng khác nhau có thể khác nhau.

Bạn là một sinh viên ngành du lịch mới ra trường và đang nộp đơn ứng tuyển một vị trí làm hướng dẫn viên du lịch. Để vào được công ty bạn phải trải qua một bài thử thách. Bài thử thách như sau: có \(Q\) thời điểm, tại một thời điểm bất kỳ có thể diễn ra một trong các sự kiện sau:

• Sự kiện 1: một cánh cổng không gian được xây dựng ở thành phố thứ \(v\) và để sử dụng cánh cổng này bạn phải tốn \(c\) lqdcoin
• Sự kiện 2: Hiện tại bạn đang đứng tại hành tinh \(v\) và bạn cần di chuyển về hình tinh \(1\), bạn hãy tìm cách đi để tốn ít lqdcoin nhất.

Input

• Dòng đầu tiên gồm hai số nguyên dương \(N\) và \(Q\) lần lượt là số hành tinh, và \(Q\) thời điểm trong thử thách (\(N, Q \leq 10^{3}\))
• \(N – 1\) dòng tiếp theo, mỗi dòng gồm hai số nguyên dương \(u\) và \(v\) thể hiện các một đường đi đặc biệt giữa hai hành tinh \(u\) và \(v\) (\(1 \leq u, v \leq N\), \(u \neq v\))
• \(Q\) dòng tiếp theo, gồm một vài số nguyên đương, số đầu tiên là t (\(1 \leq t \leq 2\)). Nếu \(t = 1\), hai số tiếp theo sẽ là \(v\) và \(c\) (\(1 \leq v \leq N\), \(1 \leq c \leq 10^{9}\)). Nếu \(t = 2\), số tiếp theo sẽ là \(v\) (\(1 \leq v \leq N\)).

Dữ liệu đảm bảo: luôn tồn tại một đường đi đặc biệt giữa hành tinh thứ \(i\) đến hành tinh thứ \(i + 1\).

Output

• Gồm một vài dòng là các cách đi tốn ít lqdcoin nhất cho từng sự kiện 2, mỗi câu trả lời in trên một dòng.

Example

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

3
3    
2    
4

Cho một dãy \(a\) gồm \(N\) số nguyên, được đánh số từ 1 đến \(N\), số thứ \(i\) có giá trị là \(a_i\) ban đầu tất cả các số đều có giá trị bằng 0. Ta có \(Q\) thao tác. Có hai loại thao tác

• Loại 1: Gồm hai số \(i\), \(v\): gán \(a_i = v\)
• Loại 2: Gồm hai số \(l\), \(r\): trả về số có giá trị lớn nhất trong đoạn từ \(l\) đến \(r\).

Input

• Dòng đầu tiền gồm 2 hai số nguyên dương \(N\), \(Q\) (\(N, Q \leq 10^{5}\))
• Dòng thứ hai gồm \(N\) số, là giá trị ban đầu của dãy \(a\)
• \(Q\) dòng tiếp theo mỗi dòng là gồm 3 số, số đầu tiên là \(t\) (\(1 \leq t \leq 2\)), là loại thao tác của thao tác hiện tại. Nếu \(t = 1\), hai số tiếp theo sẽ là \(i\) và \(v\) (\(1 \leq i \leq N\), \(1 \leq v \leq 10^{9}\)). Nếu \(t = 2\), hai số tiếp theo sẽ là \(l\) và \(r\) \((1 \leq l \leq r \leq n\)).

Output

• Dòng nhiều dòng là đáp án cho các thao tác loại 2, mỗi số in trên một dòng.

Example

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

5    
6    
4    
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 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

Tại một thời điểm nào đó trong tương lai, lúc này du lịch vũ trụ đang rất phát triển. Có \(N\) hành tinh đang được khai thác để du lịch. Hai hành tinh \(u\) và \(v\) có thể đi lại trực tiếp tới nhau bằng \(N - 1\) đường đi hai chiều đặc biệt, chi phí để sử dụng các đường đi này là 1 lqdcoin (đơn vị tiền tệ tại thời điểm này). Các đường đi được xây dựng sao cho luôn đảm bảo tồn tại cách đi giữa hai hành tinh bất kỳ.

Ngoài cách sử dụng các đường đi đặc biệt để đi lại, người ta đã tạo ra một cách đi khác để có thêm lựa chọn cho khách du lịch, đó là sử dụng những cánh cổng không gian, những cánh cổng này sẽ giúp cho một người đang đứng tại hành tinh \(u\) có thể dịch chuyển ngay lập tức tới một hành tinh bất kỳ. Tuy nhiên vì chi phí để chế tạo những cánh cổng này rất cao nên nhà đầu tư quyết định chỉ cho xây dựng cánh cổng ở một vài hành tinh. Ngoài ra nếu muốn sử dụng cánh cổng để di chuyển, khách du lịch phải trả thêm tiền, chi phí cho việc dịch chuyển giữa các cánh cổng khác nhau có thể khác nhau.

Bạn là một sinh viên ngành du lịch mới ra trường và đang nộp đơn ứng tuyển một vị trí làm hướng dẫn viên du lịch. Để vào được công ty bạn phải trải qua một bài thử thách. Bài thử thách như sau: có \(Q\) thời điểm, tại một thời điểm bất kỳ có thể diễn ra một trong các sự kiện sau:

• Sự kiện 1: một cánh cổng không gian được xây dựng ở thành phố thứ \(v\) và để sử dụng cánh cổng này bạn phải tốn \(c\) lqdcoin
• Sự kiện 2: Hiện tại bạn đang đứng tại hành tinh \(v\) và bạn cần di chuyển về hình tinh \(1\), bạn hãy tìm cách đi để tốn ít lqdcoin nhất.

Input

• Dòng đầu tiên gồm hai số nguyên dương \(N\) và \(Q\) lần lượt là số hành tinh, và \(Q\) thời điểm trong thử thách (\(N, Q \leq 10^{5}\))
• \(N – 1\) dòng tiếp theo, mỗi dòng gồm hai số nguyên dương \(u\) và \(v\) thể hiện các một đường đi đặc biệt giữa hai hành tinh \(u\) và \(v\) (\(1 \leq u, v \leq N\), \(u \neq v\))
• \(Q\) dòng tiếp theo, gồm một vài số nguyên đương, số đầu tiên là t (\(1 \leq t \leq 2\)). Nếu \(t = 1\), hai số tiếp theo sẽ là \(v\) và \(c\) (\(1 \leq v \leq N\), \(1 \leq c \leq 10^{9}\)). Nếu \(t = 2\), số tiếp theo sẽ là \(v\) (\(1 \leq v \leq N\)).

Dữ liệu đảm bảo: luôn tồn tại một đường đi đặc biệt từ hành tinh thứ \(i\) đến hành tinh thứ \(i + 1\).

Output

• Gồm một vài dòng là các cách đi tốn ít lqdcoin nhất cho từng sự kiện 2, mỗi câu trả lời in trên một dòng.

Example

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

3
3    
2    
4