Azurit Contest (Div 1)

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

Cho n hình chữ nhật kích thước khác nhau được đại diện bằng góc trái dưới và góc phải trên. Các bạn hãy kiểm tra có ít nhất một cặp hình chữ nhật cắt nhau không. Một cặp hình chữ nhật cắt nhau khi tồn tại ít nhất một điểm của hình chữ nhật này nằm hoàn toàn trong hình chữ nhật còn lại (không tính các điểm nằm trên cạnh) và chúng không lồng nhau.

Input

• Dòng đầu tiên chứ số nguyên \(n\) (\(1 \leq n \leq 10^{5}\)).
• N dòng tiếp theo, mỗi dòng chứ 4 số nguyên \(x1\), \(y1\), \(x2\), \(y2\) lần lượt tọa độ của góc trái dưới và góc phải trên của hình chữ nhật (\(-10^{9} \leq x1, y1, x2, y2 \leq 10^{9}\), \(x1 < x2, y1 < y2\)).

Output

• Gồm một dòng duy nhất: chứa số 1 (có ít nhất 1 cặp hình chữ nhật giao nhau) hoặc 0 (không chứa bất kì một cặp hình chữ nhật nào giao nhau).

Example

2    
0 0 2 2    
2 2 3 4

0

2    
1 1 3 3    
2 2 10 4

1

Sắp tới các bạn học sinh trường SuperKids (dành cho các bạn từ \(192\) đến \(216\) tháng tuổi) sẽ tổ chức kiểm tra học kỳ môn thể dục, nội dung kiểm tra năm nay là vượt rào, trường có N chiếc rào, chiếc rào thứ \(i\) sẽ có độ cao là \(h_i\) và độ chênh lệch độ cao là \(a_i\), độ chênh lệch độ cao sẽ tính bằng công thức \(a_i\) = \(h_i – h_{i - 1}\) , \(h_0 = 0\) . Để vượt chiếc rào thứ \(i\), học sinh phải có khả năng bật nhảy \(j\) sao cho \(j \ge h_i\). Thầy giáo yêu cầu để qua được môn học sinh ít nhất phải đi được hơn một nửa quãng đường, hay nói cách khác số lượng rào học sinh có thể vượt quá là lớn hơn \(n / 2\). Vì đây là một bài kiểm tra khá là khó nên các bạn học sinh đã lên một kế hoạch đột nhập vào hệ thống của trường để điều chỉnh lại độ chênh độ cao của các chiếc rào để tất cả cùng qua môn thể dục khó khăn này hoặc có thể làm nó khó hơn để tăng thêm tính thử thách nếu thấy bài thi quá dễ.

Sau một thời gian nỗ lực, các bạn học sinh đã đột nhập thành công vào hệ thống trường. Lúc này các bạn sẽ thực hiện \(Q\) thao tác, bao gồm hai loại:

• Loại 1: Gồm ba số \(l,r,v\): thay đổi độ chênh lệch của toàn bộ \(a_i = v\) (\(l \leq i \leq r\))
• Loại 2: Gồm một số \(j\): trả lời câu hỏi: "Với khả năng bật nhảy là \(j\) thì các học sinh thể vượt qua được tất cả chiếc rào hay không?"

Input:

• Dòng đầu tiền gồm 2 hai số nguyên dương \(N\), \(K\) (\(N \leq 10^{9}\), \(k \leq min(N, 100)\))
• Dòng thứ hai gồm \(K\) số, là \(K\) giá trị ban đầu của dãy \(a\), phần còn lại được mặc định ban đầu là \(0\)
• Dòng thứ ba là số \(Q\), (\(Q \leq 10^{5}\))

• \(Q\) dòng tiếp theo mỗi dòng là gồm một vài 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\), ba số tiếp theo sẽ là \(l\), \(r\) và \(v\) (\(1 \leq l \leq r \leq N\), \(-10^{9} \leq v \leq 10^{9}\)). Nếu \(t = 2\), một số tiếp theo sẽ là \(j\) \((1 \leq j \leq 10^{9}\))

• Dữ liêụ luôn đảm bảo chiều cao của các chiếc rào luôn không âm ở bất kì thời điểm nào.

Output:

• Gồm 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, nếu có thì in ra “YES” và “NO” nếu ngược lại.

Example

5 5 
1 0 0 0 0    
4
2 6    
1 1 5 4    
2 6    
2 15

YES    
NO   
YES

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 răng ở một hành tinh bất kỳ luôn tồn lại nhiều nhất một cổng dịch chuyển.

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