Giáng sinh năm nay, khu phố VOI được trang trí bởi một dàn ~N~ bóng đèn, các bóng đèn được đánh số từ ~1~ đến ~N~. Ban đầu, mỗi bóng đèn ở một trong ~3~ trạng thái tắt, vàng hoặc đỏ và được điều khiển bởi một công tắc vòng tròn hoạt động như sau:

• Khi xoay theo chiều kim đồng hồ một nấc, trạng thái bóng đèn đó thay đổi theo quy tắc:
  • Nếu đang ở trạng thái tắt thì chuyển sang trạng thái vàng.
  • Nếu đang ở trạng thái vàng thì chuyển sang trạng thái đỏ.
  • Nếu đang ở trạng thái đỏ thì chuyển sang trạng thái tắt.
• Khi xoay ngược chiều kim đồng hồ một nấc, trạng thái bóng đèn đó thay đổi theo quy tắc:
  • Nếu đang ở trạng thái tắt thì chuyển sang trạng thái đỏ.
  • Nếu đang ở trạng thái đỏ thì chuyển sang trạng thái vàng.
  • Nếu đang ở trạng thái vàng thì chuyển sang trạng thái tắt.

Ban quản trị VOI nhận được ~Q~ yêu cầu khảo sát, mỗi yêu cầu gồm hai giá trị ~L~ và ~R~ với ~1 ≤ L ≤ R ≤ N~. Cụ thể, mỗi yêu cầu khảo sát cần tìm một dãy các thao tác để đưa tất cả các bóng đèn từ ~L~ đến ~R~ về trạng thái tắt, mỗi thao tác có thể thực hiện như sau:

Chọn ~X + Y~ bóng đèn phân biệt trong đoạn từ ~L~ đến ~R~, trong đó: ~X~ bóng đèn để xoay công tắc theo chiều kim đồng hồ một nấc, ~Y~ bóng đèn còn lại để xoay công tắc ngược chiều kim đồng hồ một nấc.

Lưu ý: Các yêu cầu khảo sát là độc lập, nghĩa là mỗi yêu cầu đều được xử lý trên trạng thái ban đầu của dãy đèn. Giá trị ~X~ và ~Y~ cố định cho tất cả ~Q~ yêu cầu. Các công tắc vòng tròn được thiết kế để có thể xoay không giới hạn theo cả hai chiều.

Yêu cầu: Với mỗi yêu cầu khảo sát, hãy tìm số thao tác ít nhất để đưa toàn bộ các bóng đèn trong đoạn từ L đến R của dãy đèn về trạng thái tắt.

Input

Vào từ file văn bản LIGHT.INP:

• Dòng đầu chứa ~4~ số nguyên không âm ~N, Q, X, Y~ (~0 < X + Y ≤ 5~, ~X + Y ≤ N ≤ 666~, ~1 ≤ Q ≤ 10^5~).
• Dòng thứ hai chứa ~N~ số nguyên, số thứ ~i~ có giá trị ~0, 1~ hoặc ~2~ tương ứng với trạng thái ban đầu của bóng đèn thứ ~i~ là tắt, vàng hoặc đỏ (~1 ≤ i ≤ N~).
• Mỗi dòng trong số ~Q~ dòng tiếp theo chứa hai số nguyên dương ~L~ và ~R~ mô tả một yêu cầu. Dữ liệu bảo đảm ~R - L + 1 ≥ X + Y~ trong tất cả các yêu cầu khảo sát.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

Ghi ra file văn bản LIGHT.OUT:

• Gồm ~Q~ dòng, mỗi dòng một số nguyên là số lượng thao tác ít nhất tìm được cho yêu cầu khảo sát tương ứng hoặc ~-1~ nếu không tồn tại phương án.

Sample Input

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

Sample Output

3
2
-1

Yêu cầu khảo sát đầu tiên cần ít nhất ~3~ thao tác. Hình sau minh hoạ một dãy thao tác tối ưu:

Subtasks

Ông già Noel đã chuẩn bị ~N~ loại quà, loại quà thứ ~i~ (~1 ≤ i ≤ N~) có ~S_i~ món và khối lượng mỗi món là ~W_i~ gram. Ông dự định đóng gói các túi quà để phát cho trẻ em ở VOI sao cho mỗi túi có đúng ~K~ món và không có hai món nào cùng một loại quà. Tuy nhiên xe tuần lộc của ông chỉ có thể mang được không quá ~M~ gram quà.

Để chuẩn bị chu đáo trước khi lên đường, ông già Noel đưa ra một loạt ~Q~ câu hỏi cho trợ lý của ông tính toán, mỗi câu hỏi thuộc một trong hai loại sau:

• Loại 1: Cho biết ~3~ giá trị ~M, K, T~, hãy kiểm tra xem có thể tạo ra được ~T~ túi quà mà tổng khối lượng các món quà trong cả ~T~ túi đó không vượt quá ~M~ gram hay không?
• Loại 2: Cho biết 2 giá trị ~M, K~, hỏi có thể tạo ra được nhiều nhất bao nhiêu túi quà mà tổng khối lượng các món quà trong tất cả các túi đó không vượt quá ~M~ gram?

Yêu cầu: Hãy giúp trợ lý trả lời từng câu hỏi của ông già Noel.

Input

Vào từ file văn bản GIFT.INP:

• Dòng đầu chứa ~2~ số nguyên ~N, Q~ (~1 ≤ N, Q ≤ 10^5~).
• Dòng thứ hai chứa ~N~ số nguyên dương ~W_1, W_2, ..., W_N~ có giá trị không quá ~10^5~.
• Dòng thứ ba chứa ~N~ số nguyên dương ~S_1, S_2, ..., S_N~ có giá trị không quá ~10^5~.
• Mỗi dòng trong số ~Q~ dòng tiếp theo thể hiện một câu hỏi thuộc một trong hai loại:
  • Loại 1: ~1~ ~M~ ~K~ ~T~ (~1 ≤ M, K, T ≤ 10^9~).
  • Loại 2: ~2~ ~M~ ~K~ (~1 ≤ M, K ≤ 10^9~).

Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

Ghi ra file văn bản GIFT.OUT:

• Gồm ~Q~ dòng, mỗi dòng thể hiện câu trả lời cho một câu hỏi tương ứng:
  • Loại 1: Ghi ra ~1~ nếu có thể tạo được ~T~ túi quà, trái lại ghi ra ~0~.
  • Loại 2: Ghi ra một số nguyên là số lượng túi quà nhiều nhất tạo được.

Sample Input

5 3
8 3 4 10 8
5 8 2 9 10
1 19 3 2
2 19 3
2 9 1

Sample Output

0
1
3

• Với câu hỏi 1: Không có cách nào chọn được hai túi, mỗi túi có ~3~ món mà tổng khối lượng không quá ~19~ gram.
• Với câu hỏi 2: Tạo ra được nhiều nhất một túi quà. Một phương án là túi quà gồm một món quà loại ~2~, một mốn quà loại ~3~ và một món quà loại ~4~. Tổng khối lượng là ~17~ gram.
• Với câu hỏi 3: Tạo ra được nhiều nhất ba túi quà. Mỗi túi gồm đúng một món quà loại ~2~.

Subtasks

Alice là kỹ sư phát triển nền tảng mạng xã hội VOI giúp cho cộng đồng lập trình viên tương tác với nhau. Có ~N~ bài đăng được đánh số từ ~1~ đến ~N~ theo trình tự thời gian đăng bài. Alice phân loại các bài đăng theo chủ đề, bài đăng thứ ~i~ (~1 ≤ i ≤ N~) có chủ đề là ~A_i~.

Alice định nghĩa một đoạn ~[L, R]~ gồm các bài đăng liên tiếp từ chỉ số ~L~ đến chỉ số ~R~ (~1 ≤ L ≤ R ≤ N~) là toàn vẹn nếu với mỗi chủ đề ~t~, hoặc không có bài nào có chủ đề ~t~ nằm trong đoạn ~[L, R]~ hoặc tất cả các bài có chủ đề ~t~ đều nằm trong đoạn này.

Yêu cầu: Vào dịp Noel, Alice công bố dữ liệu chủ đề của ~N~ bài đăng và mở một cuộc thi trên VOI cho cộng đồng lập trình viên. Alice lần lượt đưa ra ~Q~ truy vấn, mỗi truy vấn cho biết một cặp số nguyên ~U, V~ ~(1 ≤ U ≤ V ≤ N)~ và yêu cầu thí sinh đếm số đoạn ~[L, R]~ toàn vẹn với ~U ≤ L ≤ R ≤ V~.

Cụ thể, với mỗi truy vấn, cần đếm xem bao nhiêu cặp L, R thỏa mãn:

• ~U ≤ L ≤ R ≤ V~;
• Không tồn tại hai giá trị ~i, j~ nào sao cho:
  • ~(1 ≤ i < L)~ hoặc ~(R < i ≤ N)~;
  • ~L ≤ j ≤ R~;
  • ~A_i = A_j~.

Input

Vào từ file văn bản POST.INP:

• Dòng đầu chứa hai số nguyên ~N~ và ~Q~ (~1 ≤ N, Q ≤ 3 × 10^5~).
• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2, ..., A_N~ (~1 ≤ A_1, A_2, ..., A_N ≤ 10^9~).
• Mỗi dòng trong số ~Q~ dòng tiếp theo chứa hai số nguyên dương ~U~ và ~V~.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

Ghi ra file văn bản POST.OUT:

• Gồm ~Q~ dòng, mỗi dòng một số là đáp án cho truy vấn tương ứng.

Sample Input

7 2
1 2 2 3 1 6 3
1 7
2 6

Sample Output

3
2

• Truy vấn 1, có ~3~ đoạn toàn vẹn: ~[1,7]~, ~[2,3]~, ~[6,6]~.
• Truy vấn 2, có ~2~ đoạn toàn vẹn: ~[2,3]~, ~[6,6]~.

Subtasks

Trong tiệc tất niên cuối năm, gia đình Alice chuẩn bị một bàn tiệc lớn để chào đón mọi người. Trên bàn có ~N~ đĩa thức ăn được bày biện đẹp mắt thành một hàng, được đánh số từ ~1~ đến ~N~ từ trái sang phải. Đĩa thứ ~i~ (~1 ≤ i ≤ N~) có độ hấp dẫn là một số nguyên dương ~A_i~.

Với một đoạn gồm ~M~ đĩa ở vị trí liên tiếp của bàn tiệc có độ hấp dẫn tương ứng là dãy (~B_1, B_2, ..., B_M~), Alice định nghĩa độ đa dạng của dãy đó là số lượng dãy khác nhau có thể nhận được bằng cách thực hiện không quá một phép đảo ngược trên dãy. Một phép đảo ngược được định nghĩa là chọn một cặp chỉ số ~(L, R)~ với ~1 ≤ L < R ≤ M~ và thực hiện đảo ngược dãy ~(B_L, B_{L+1}, ..., B_{R-1}, B_R)~ thành dãy ~(B_R, B_{R-1}, ..., B_{L+1}, B_L)~, các phần tử còn lại giữ nguyên. Hai dãy ~(X_1, X_2, ..., X_M)~ và ~(Y_1, Y_2, ..., Y_M)~ được xem là khác nhau nếu tồn tại chỉ số ~i~ ~(1 ≤ i ≤ M)~ sao cho ~X_i \neq Y_i~. Ví dụ, dãy ~(3, 1, 3)~ có độ đa dạng bằng ~3~ vì có thể tạo ra dãy khác nhau với một phép đảo ngược: ~(3, 1, 3)~, ~(1, 3, 3)~, ~(3, 3, 1)~.

Trong buổi tiệc, có ~Q~ vị khách lần lượt tới thăm. Với khách thứ ~j~ (~1 ≤ j ≤ Q~) đến và lấy chiếc đĩa thứ ~p_j~ để dùng bữa. Sau khi một chiếc đĩa được lấy ra, những chiếc còn lại giữ nguyên vị trí ban đầu và tạo thành các đoạn con ngăn cách bởi các vị trí trống do các đĩa đã được lấy đi. Alice tính độ đa dạng của mỗi đoạn con và muốn biết độ đa dạng lớn nhất trong số chúng.

Yêu cầu: Sau khi mỗi vị khách nhấc một chiếc đĩa đi, hãy tính độ đa dạng lớn nhất trong các đoạn con còn lại.

Input

Vào từ file văn bản TET.INP:

• Dòng đầu chứa hai số nguyên ~N~ và ~Q~ (~1 ≤ Q < N ≤ 2 \times 10^5~).
• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2, ..., A_N~ (~1 ≤ A_i ≤ 10^9~).
• Dòng thứ ~j~ trong số Q dòng tiếp theo chứa một số nguyên dương ~p_j~ (~1 ≤ p_j ≤ N~). Dữ liệu bảo đảm các giá trị ~p_j~ là khác nhau.

Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

Ghi ra file văn bản TET.OUT:

• Gồm ~Q~ dòng, mỗi dòng một số nguyên duy nhất là kết quả tìm được sau khi vị khách tương ứng nhấc một chiếc đĩa đi.

Sample Input

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

Sample Output

9
2
2

• Sau khi lấy đĩa thứ ~2~, thu được hai đoạn con là ~(4)~ và ~(3, 1, 3, 2, 1)~, với độ đa dạng lần lượt là ~1~ và ~9~.
• Sau khi lấy đĩa thứ ~5~, thu được ba đoạn con là ~(4)~, ~(3, 1)~ và ~(2, 1)~, với độ đa dạng lần lượt là ~1~, ~2~ và ~2~.
• Sau khi lấy đĩa thứ ~6~, thu được ba đoạn con là ~(4)~, ~(3, 1)~ và ~(1)~, với độ đa dạng lần lượt là ~1~, ~2~ và ~1~.

Subtasks

Ông già Noel có một cây thông khổng lồ đã trang hoàng cho đêm Giáng sinh. Trên các cành của cây thông, ông treo ~N~ tấm thiệp trang trí được đánh số từ ~1~ đến ~N~. Tấm thiệp ~i~ (~1 ≤ i ≤ N~) có độ lấp lánh được biểu thị bằng số nguyên không âm ~A_i~. Các tấm thiệp được kết nối với nhau bằng ~N - 1~ đoạn dây. Đoạn dây thứ ~i~ kết nối hai tấm thiệp ~u_i~ và ~v_i~ (~1 ≤ u_i, v_i ≤ N~). Hệ thống dây đảm bảo rằng giữa hai tấm thiệp bất kỳ trên cây luôn tồn tại duy nhất một đường đi trực tiếp kết nối hai tấm thiệp và các đoạn dây. Nói cách khác, các tấm thiệp và các đoạn dây tạo thành một đồ thị dạng cây có ~N~ đỉnh và ~N - 1~ cạnh.

Mỗi thời điểm trong đêm Giáng sinh, ông già Noel sẽ thực hiện một phép thuật. Có ~Q~ thời điểm lần lượt xảy ra đánh số từ ~1~ đến ~Q~. Tại thời điểm ~t~ (~1 ≤ t ≤ Q~), ông thực hiện một phép thuật được mô tả bằng ba số nguyên dương ~x_t, y_t, w_t~ với ý nghĩa: gán ~A_v = A_v \% w_t~ với mọi tấm thiệp ~v~ nằm trên đường kết nối từ tấm thiệp ~x_t~ đến tấm thiệp ~y_t~ (bao gồm cả ~x_t~ và ~y_t~). Sau khi thực hiện phép thuật, ông định nghĩa độ đẹp của cây tại thời điểm ~t~ là tổng độ đẹp của các tấm thiệp trên cây tại thời điểm đó, tức là: ~(A_1~ ~\%~ ~t) + (A_2~ ~\%~ ~t) + ... + (A_N~ ~\%~ ~t)~. Nhắc lại, ~\%~ là phép toán chia lấy dư.

Yêu cầu: Hãy giúp ông già Noel tính độ đẹp của cây sau mỗi lần thực hiện phép thuật.

Input

Vào từ file văn bản PINE.INP:

• Dòng đầu chứa hai số nguyên dương ~N~ và ~Q~ (~1 ≤ N, Q ≤ 2 \times 10^5~).
• Dòng thứ hai chứa ~N~ số nguyên ~A_1, A_2, ..., A_N~ (~0 ≤ A_i ≤ 2 \times 10^5~).
• Dòng thứ ~i~ trong số ~N - 1~ dòng tiếp theo chứa hai số nguyên dương phân biệt ~u_i~ và ~v_i~ mô tả một đoạn dây kết nối trực tiếp hai tấm thiệp ~u_i~ và ~v_i~ trên cây (~1 ≤ u_i, v_i ≤ N~).
• Dòng thứ ~t~ trong số ~Q~ dòng tiếp theo chứa ba số nguyên dương ~x_t, y_t, w_t~ mô tả một lần thực hiện phép thuật tại thời điểm ~t~ (~1 ≤ x_t, y_t ≤ N; w_t ≤ 2 \times 10^5~).

Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

Ghi ra file văn bản PINE.OUT:

• Gồm ~Q~ dòng, dòng thứ ~t~ chứa một số nguyên là độ đẹp của cây sau khi thực hiện phép thuật tại thời điểm ~t~.

Sample Input

5 3
2 1 4 4 8
1 2
2 3
3 4
4 5
1 5 5
1 5 3
3 3 1

Sample Output

0
3
4

• Ở thời điểm ~t = 1~, dãy ~A~ là ~(2, 1, 4, 4, 3)~. Kết quả là ~(2~ ~\%~ ~t) + (1~ ~\%~ ~t) + (4~ ~\%~ ~t) + (4~ ~\%~ ~t) + (3~ ~\%~ ~t) = 0~.
• Ở thời điểm ~t = 2~, dãy ~A~ là ~(2, 1, 1, 1, 0)~. Kết quả là ~(2~ ~\%~ ~t) + (1~ ~\%~ ~t) + (1~ ~\%~ ~t) + (1~ ~\%~ ~t) + (0~ ~\%~ ~t) = 3~.
• Ở thời điểm ~t = 3~, dãy ~A~ là ~(2, 1, 0, 1, 0)~. Kết quả là ~(2~ ~\%~ ~t) + (1~ ~\%~ ~t) + (0~ ~\%~ ~t) + (1~ ~\%~ ~t) + (0~ ~\%~ ~t) = 4~.

Subtasks