Có một bức ảnh kỹ thuật số với chiều rộng ~W~ và chiều cao ~H~. Ta cần hiển thị bức ảnh trên một màn hình có chiều rộng ~A~ và chiều cao ~B~.

Bức ảnh có các cạnh song song với màn hình. Màn hình có chức năng phóng ảnh theo một hệ số nguyên dương ~k~, ảnh sau khi phóng sẽ có kích thước ~kW \times kH~. Ảnh có thể xoay ~90~ độ trước khi phóng, khi đó chiều rộng và chiều cao của ảnh đổi chỗ cho nhau.

Yêu cầu: Hãy tìm hệ số ~k~ nguyên dương lớn nhất có thể để toàn bộ ảnh sau khi phóng phải nằm trọn trong màn hình.

Input

• Gồm bốn dòng chứa lần lượt bốn số nguyên dương ~W,H,A,B~ ~(1 \le W,H,A,B \le 10^9)~. Dữ liệu bảo đảm ảnh đặt vừa màn hình theo ít nhất một hướng khi ~k=1~.

Output

• Một số nguyên là kết quả của bài toán.

Scoring

Sample Input 1

2
5
4
6

Sample Output 1

1

Sample Input 2

5
3
8
10

Sample Output 2

2

Notes

Trong ví dụ thứ nhất, không xoay và không phóng ảnh.

Trong ví dụ thứ hai, xoay ảnh ~90~ độ và phóng ảnh gấp ~2~ lần.

Cho một dãy số nguyên dương gồm ~N~ số ~a_1,a_2,\dots,a_N~. Dãy số được gọi là hoàn hảo nếu phần tử có giá trị ~a_i~ xuất hiện đúng ~a_i~ lần trong dãy số đó ~(1 \le i \le N)~.

Yêu cầu: Tìm cách xoá tối đa một phần tử của dãy số ban đầu để dãy số trở thành dãy số hoàn hảo.

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(1 \le N \le 10^5)~;

• Dòng thứ hai chứa ~N~ số nguyên dương ~a_1,a_2,\dots,a_N~ ~(1 \le a_i \le 10^5)~.

Output

Một số nguyên là một trong những trường hợp sau:

• Nếu dãy ban đầu đã là dãy hoàn hảo, in ra ~0~;

• Nếu dãy ban đầu không là dãy hoàn hảo và cần xoá đi một phần tử để trở thành dãy hoàn hảo, in ra giá trị phần tử cần xoá;

• Nếu không thể biến đổi thành dãy hoàn hảo, in ra ~-1~.

Scoring

Sample Input 1

4
3 1 3 3

Sample Output 1

0

Sample Input 2

4
3 2 3 3

Sample Output 2

2

Sample Input 3

5
3 1 1 3 3

Sample Output 3

1

Sample Input 4

5
3 4 4 3 3

Sample Output 4

-1

Notes

Trong ví dụ thứ nhất, dãy đã cho là dãy hoàn hảo vì có ~1~ phần tử có giá trị ~1~ và ~3~ phần tử có giá trị ~3~.

Trong ví dụ thứ hai, xoá một phần tử có giá trị ~2~ thì dãy số trở thành ~[3,3,3]~ là dãy hoàn hảo.

Trong ví dụ thứ ba, xóa một phần tử có giá trị ~1~ thì dãy số trở thành ~[3,1,3,3]~ là dãy hoàn hảo.

Trong ví dụ thứ tư, không thể biến đổi thành dãy hoàn hảo.

Cho một chuỗi ~S~ chỉ chứa những ký tự in thường trong bảng chữ cái tiếng Anh.

Một chuỗi được gọi là chuỗi cân bằng nếu thoả mãn các tiêu chí sau:

• Độ dài chuỗi là số chẵn;

• Các ký tự phân biệt xuất hiện ở hai nửa của chuỗi là giống nhau.

Ví dụ:

• "aaazzaaz" là chuỗi cân bằng vì mỗi nửa chuỗi "aaaz" | "zaaz" chứa đúng hai ký tự phân biệt 'a' và 'z';

• "abbba" không là chuỗi cân bằng vì độ dài chuỗi là số lẻ (không chia đôi được);

• "aaab" không là chuỗi cân bằng vì nửa bên trái chỉ chứa ký tự 'a' còn nửa bên phải chứa ký tự 'a' và 'b'.

Yêu cầu: Hãy đếm số lượng chuỗi con liên tiếp của chuỗi ~S~ là chuỗi cân bằng.

Input

Một dòng duy nhất gồm chuỗi ~S~ có độ dài không vượt quá ~10^5~.

Output

Một số nguyên là kết quả của bài toán.

Scoring

Sample Input 1

aazazz

Sample Output 1

4

Sample Input 2

ababbcd

Sample Output 2

2

Notes

Trong ví dụ thứ nhất, có ~4~ chuỗi thoả mãn: "aa", "aazazz", "azaz", "zz".

Trong ví dụ thứ hai, có ~2~ chuỗi thoả mãn: "abab", "bb".

Một hệ thống siêu máy tính đang tiếp nhận danh sách gồm ~N~ gói tác vụ từ các tổ chức cần lập lịch thực thi (có tối đa ba tổ chức). Gói tác vụ thứ ~i~ của tổ chức ~A_i~ yêu cầu ~C_i~ lõi vi xử lý (CPU) và ~R_i~ gigabyte bộ nhớ RAM.

Để bộ điều phối phần cứng có thể tối ưu hoá luồng xử lý, ta cần chọn chuỗi tác vụ sao cho nhu cầu tài nguyên CPU và RAM của tác vụ sau luôn lớn hơn tác vụ trước. Nói cách khác, chọn một chuỗi ~K~ tác vụ ~(i_1,i_2,\dots,i_K)~ thoả mãn quy tắc sau:

~C_{i_1} < C_{i_2} < \dots < C_{i_K}~ và ~R_{i_1} < R_{i_2} < \dots < R_{i_K}~.

Để giữ tính cân bằng giữa các tổ chức, chuỗi tác vụ được chọn đảm bảo không có ba tác vụ liên tiếp thuộc cùng một tổ chức.

Yêu cầu: Hãy xác định độ dài chuỗi tác vụ hợp lệ dài nhất.

Input

• Dòng đầu tiên gồm số nguyên dương ~N~ ~(1 \le N \le 10^5)~;

• ~N~ dòng sau, dòng thứ ~i~ gồm ba số nguyên dương ~C_i,R_i,A_i~ ~(1 \le C_i,R_i \le 10^{18}; 1 \le A_i \le 3)~.

Dữ liệu đảm bảo không có ~2~ bộ ~C_i,R_i,A_i~ giống nhau.

Output

• Một số nguyên là kết quả của bài toán.

Scoring

Sample Input 1

8
3 3 1
4 3 2
9 8 3
1 1 1
9 8 1
5 6 1
7 8 2
7 7 1

Sample Output 1

5

Notes

Có thể thực hiện các tác vụ như sau:

• ~[1,1,1]~

• ~[4,3,2]~

• ~[5,6,1]~

• ~[7,7,1]~

• ~[9,8,3]~

Hệ thống quản lý mạng lưới gồm ~N~ hành tinh được đánh số từ ~1~ đến ~N~ và ~M~ cổng dịch chuyển hai chiều, cổng thứ ~i~ nối hai hành tinh ~u_i~ và ~v_i~, có ngưỡng chịu tải ~c_i~. Một tàu có mức năng lượng ~W~ chỉ đi qua được cổng có ~c_i \ge W~.

Trung tâm điều khiển cần xử lý ~Q~ chuyến bay độc lập. Mỗi chuyến bay yêu cầu đưa một tàu có mức năng lượng ~W~ từ hành tinh ~s~ đến hành tinh ~t~. Trong chuyến bay đó, trung tâm điều khiển có thể nâng cấp ngưỡng chịu tải tối đa của đúng một cổng bất kỳ lên vô hạn. Sự thay đổi không được giữ lại và không ảnh hưởng đến các chuyến bay khác.

Yêu cầu: Với mỗi chuyến bay, hãy xác định tàu có thể đi từ hành tinh ~s~ đến hành tinh ~t~ hay không nếu lựa chọn tối ưu cổng được nâng cấp.

Input

• Dòng đầu tiên chứa ba số nguyên ~N,M,Q~ ~(2 \le N \le 10^5;\ 1 \le M \le 2 \cdot 10^5;\ 1 \le Q \le 10^5)~;

• ~M~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên ~u_i,v_i,c_i~ ~(1 \le u_i,v_i \le N;\ 1 \le c_i \le 10^9)~;

• ~Q~ dòng cuối cùng, mỗi dòng chứa ba số nguyên ~s,t,W~ ~(1 \le s,t \le N;\ s \ne t;\ 1 \le W \le 10^9)~.

Dữ liệu đảm bảo đồ thị không có khuyên và không có đa cạnh.

Output

• Với mỗi chuyến bay, in YES nếu tàu có thể đến đích; ngược lại in NO.

Scoring

Sample Input 1

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

Sample Output 1

YES
YES
NO
NO

Notes

• Có thể đi từ hành tinh ~1~ đến hành tinh ~4~ với mức năng lượng ~2~ mà không cần nâng ngưỡng chịu tải của cổng nào.

• Có thể đi từ hành tinh ~4~ đến hành tinh ~3~ với mức năng lượng ~4~ và cần nâng cấp cổng ~1-2~.

• Không thể đi từ hành tinh ~5~ đến hành tinh ~3~ với mức năng lượng ~7~ vì có hai cổng có ngưỡng nhỏ hơn ~7~.

• Không thể thực hiện chuyến bay thứ tư, vì hành tinh ~1~ và hành tinh ~6~ không liên thông.

Cho bốn số nguyên ~N,K,X,Y~ và dãy số từ ~1~ tới ~N~. Mỗi lượt thực hiện hai thao tác theo thứ tự sau:

• Bước 1: Lấy các phần tử nằm ở vị trí là số chính phương trong dãy và chuyển tới bên trái dãy;

• Bước 2: Lấy các phần tử nằm ở vị trí là số chính phương trong dãy và chuyển tới bên phải dãy.

Ví dụ: Với ~N=6~ và dãy số ban đầu là ~[1,2,3,4,5,6]~, lượt ~1~ sẽ thực hiện các bước sau:

• Bước 1: Dồn số ở vị trí ~1~ và vị trí ~4~ sang bên trái, dãy số ~[1,2,3,4,5,6]~ trở thành ~[1,4,2,3,5,6]~;

• Bước 2: Dồn số ở vị trí ~1~ và vị trí ~4~ sang bên phải, dãy số ~[1,4,2,3,5,6]~ trở thành ~[4,2,5,6,1,3]~.

Yêu cầu: Với dãy số ban đầu, sau khi thực hiện liên tục ~K~ lượt, xác định vị trí của giá trị ~X~ và giá trị của phần tử ở vị trí ~Y~.

Input

• Một dòng duy nhất gồm bốn số nguyên dương ~N,K,X,Y~ ~(1 \le X,Y \le N \le 10^{12}; K \le 10^6)~.

Output

• Một dòng duy nhất chứa hai số nguyên dương là kết quả bài toán.

Scoring

Sample Input 1

6 1 3 6

Sample Output 1

6 3

Sample Input 2

6 2 1 1

Sample Output 2

3 6

Notes

Trong ví dụ thứ nhất, dãy sau thực hiện ~1~ lượt là ~[4,2,5,6,1,3]~. Vị trí của giá trị ~3~ là ~6~. Giá trị của phần tử ở vị trí ~6~ là ~3~.

Trong ví dụ thứ hai, dãy sau thực hiện ~2~ lượt là ~[6,2,1,3,4,5]~. Vị trí của giá trị ~1~ là ~3~. Giá trị của phần tử ở vị trí ~1~ là ~6~.

Một khu đất được chia thành ~N~ mảnh liền kề đánh số từ ~1~ đến ~N~. Mảnh thứ ~i~ có độ cao là số nguyên không âm ~H_i~.

Có ~M~ nhà đầu tư tham gia dự án. Nhà đầu tư thứ ~i~ muốn thuê toàn bộ các mảnh đất thuộc đoạn ~[L_i,R_i]~ và chỉ chấp nhận khi ~H_j=0~ ~(L_i \le j \le R_i)~. Các yêu cầu là độc lập, có thể nhiều nhà đầu tư muốn thuê cùng một đoạn.

Đội thi công nhận được ~Q~ chỉ thị liên tiếp. Mỗi chỉ thị chọn một vị trí ~x~ đang có ~H_x>0~ và thực hiện giảm ~H_x~ đi ~1~.

Yêu cầu: Sau mỗi chỉ thị, hãy cho biết số lượng nhà đầu tư đang được thỏa mãn.

Trong một số trường hợp để bảo mật thông tin, vị trí ~x_i~ có thể được mã hóa. Dữ liệu cung cấp giá trị ~y_i~ và tham số ~\theta~:

• Nếu ~\theta=0~, ~x_i=y_i~ (không mã hóa);

• Nếu ~\theta=1~, ~x_i=(y_i+lastans)\bmod N+1~, trong đó ~lastans~ là đáp án ngay trước chỉ thị thứ ~i~. Trước chỉ thị đầu tiên, ~lastans~ là số lượng nhà đầu tư thỏa mãn ở trạng thái ban đầu.

Input

• Dòng đầu tiên chứa bốn số nguyên ~N,M,Q,\theta~ ~(1 \le N,M,Q \le 5 \cdot 10^5;\ \theta \in \{0,1\})~;

• Dòng thứ hai chứa ~N~ số nguyên ~H_1,H_2,\dots,H_N~ ~(0 \le H_i \le 5 \cdot 10^5)~;

• ~M~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~L_i,R_i~ ~(1 \le L_i \le R_i \le N)~;

• Dòng cuối cùng chứa ~Q~ số nguyên ~y_1,y_2,\dots,y_Q~ ~(0 \le y_i < 10^9)~.

Dữ liệu bảo đảm sau khi giải mã luôn có ~1 \le x_i \le N~ và ~H_{x_i}>0~ ngay trước khi thực hiện chỉ thị.

Output

• In ~Q~ dòng; dòng thứ ~i~ là số lượng nhà đầu tư thỏa mãn sau chỉ thị thứ ~i~.

Scoring

Sample Input 1

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

Sample Output 1

0
0
2
2
3
4

Sample Input 2

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

Sample Output 2

0
0
1
2
5
5

Notes

Trong ví dụ thứ nhất, sau chỉ thị thứ ba, hai mảnh ~3~ và ~4~ đều có độ cao ~0~, nên hai nhà đầu tư có yêu cầu ~[3,4]~ và ~[4,4]~ được thỏa mãn.

Sau chỉ thị cuối cùng, các mảnh từ ~2~ đến ~6~ đều bằng ~0~ và cả bốn nhà đầu tư đều được thỏa mãn.

Trong ví dụ thứ hai, khi ~\theta=1~, trước chỉ thị đầu tiên, không có nhà đầu tư nào thỏa mãn nên ~lastans=0~, vị trí thực tế ~x_1=(5+0)\bmod 5+1=1~, ~H_1~ giảm từ ~4~ xuống ~3~.

Trước chỉ thị thứ tư, ~lastans=1~ nên vị trí thực tế là ~x_4=(1+1)\bmod 5+1=3~, ~H_3~ giảm từ ~2~ xuống ~1~.

Một hệ thống gồm ~N~ cảm biến được xếp thành hàng, đánh số từ ~1~ đến ~N~. Cảm biến thứ ~i~ có tần số hiệu chỉnh là số nguyên dương ~A_i~. Mức đồng bộ của một nhóm cảm biến được tính bằng ước chung lớn nhất của các tần số trong nhóm.

Yêu cầu: Xử lý ~Q~ thao tác thuộc một trong hai loại:

• Loại 1 — 1 ~L~ ~R~ ~X~: tăng tần số của mọi cảm biến ~A_i~ (~L \le i \le R~) thêm ~X~;

• Loại 2 — 2 ~L~ ~R~: Xét các cảm biến ở các vị trí ~L, L+1, \dots, R~; được phép loại không quá một cảm biến. Hãy tính mức đồng bộ lớn nhất có thể của các cảm biến còn lại.

Truy vấn có ~L=R~ luôn có đáp án ~A_L~ (không loại bỏ cảm biến nào).

Input

• Dòng đầu tiên chứa hai số nguyên dương ~N, Q~ (~1 \le N, Q \le 2 \cdot 10^5~);

• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2, \dots, A_N~ (~1 \le A_i \le 10^9~);

• Mỗi dòng trong ~Q~ dòng tiếp theo có một trong hai dạng:

  • 1 ~L~ ~R~ ~X~, với ~1 \le L \le R \le N~ và ~1 \le X \le 10^9~;

  • 2 ~L~ ~R~, với ~1 \le L \le R \le N~.

Output

Với mỗi thao tác loại ~2~, in ra trên một dòng đáp án tương ứng.

Scoring

Sample Input 1

3 3
6 10 15
2 1 3
1 2 3 2
2 1 3

Sample Output 1

5
6

Notes

• Thao tác ~1~: loại bỏ cảm biến đầu tiên có giá trị ~6~, kết quả là ước chung lớn nhất của ~10~ và ~15~ là ~5~.

• Thao tác ~2~: sau phép cộng, dãy là ~[6, 12, 17]~.

• Thao tác ~3~: loại bỏ cảm biến cuối cùng có giá trị ~17~, kết quả là ước chung lớn nhất của ~6~ và ~12~ là ~6~.

Hệ thống xe buýt ở Hà Nội rất lớn. An muốn xây dựng một ứng dụng kiểm tra xem hai trạm có thể đi lại với nhau mà không cần đổi tuyến hay không.

Hệ thống mô hình hoá thành một mạng lưới gồm có ~N~ trạm và đúng ~N-1~ đoạn đường hai chiều sao cho từ mọi trạm đều có thể đi tới mọi trạm khác, do đó mạng lưới tạo thành một cây.

Có ~K~ tuyến xe, tuyến xe thứ ~i~ chạy qua toàn bộ đường đi đơn từ trạm ~s_i~ đến trạm ~t_i~ và ngược lại. Hành khách có thể lên hoặc xuống xe tại bất kỳ trạm nào nằm trên đường đi này.

Yêu cầu: Có ~Q~ truy vấn, mỗi truy vấn cho hai số nguyên ~a~ và ~b~, hãy xác định xem có tồn tại ít nhất một tuyến xe đi qua cả ~a~ và ~b~ không (có thể đi từ ~a~ tới ~b~ mà không cần đổi tuyến).

Input

• Dòng đầu tiên chứa ba số nguyên ~N,K,Q~ ~(2 \le N \le 3 \cdot 10^5; 1 \le K,Q \le 3 \cdot 10^5)~;

• ~N-1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u,v~ ~(1 \le u,v \le N; u \ne v)~ mô tả một đoạn đường nối hai trạm. Các đoạn đường tạo thành một cây;

• ~K~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~s,t~ ~(1 \le s,t \le N; s \ne t)~, mô tả một tuyến xe chạy giữa ~s~ và ~t~;

• ~Q~ dòng cuối cùng, mỗi dòng chứa hai số nguyên ~a,b~ ~(1 \le a,b \le N; a \ne b)~, mô tả một truy vấn.

Output

Với mỗi truy vấn, in ra YES nếu hai trạm thuộc cùng một tuyến; ngược lại, in ra NO. Các kết quả phải được in theo đúng thứ tự truy vấn.

Scoring

Sample Input 1

8 3 7
1 2
1 3
2 4
2 5
3 6
6 7
6 8
4 5
4 7
3 8
2 5
5 7
1 6
7 8
3 8
2 3
4 8

Sample Output 1

YES
NO
YES
NO
YES
YES
NO

Notes

1. Tuyến từ ~4~ đến ~5~ đi qua các trạm ~4,2,5~ ~\rightarrow~ YES.

2. Không có tuyến nào đi qua đồng thời ~5~ và ~7~ ~\rightarrow~ NO.

3. Tuyến từ ~4~ đến ~7~ đi qua ~4,2,1,3,6,7~ ~\rightarrow~ YES.

4. Không có tuyến nào đi qua đồng thời cả ~7~ và ~8~ ~\rightarrow~ NO.

5. Tuyến từ ~3~ đến ~8~ đi qua ~3,6,8~ ~\rightarrow~ YES.

6. Tuyến từ ~4~ đến ~7~ đi qua ~4,2,1,3,6,7~ ~\rightarrow~ YES.

7. Không có tuyến nào đi qua đồng thời cả ~4~ và ~8~ ~\rightarrow~ NO.