Cho một dãy số ~A~ gồm ~N~ phần tử. Các phần tử được đánh số từ ~1~ đến ~N~. Phần tử thứ ~i~ được kí hiệu là ~A_i~.

Người ta cần thực hiện ~R \times Q~ truy vấn với dãy số, mỗi truy vấn thuộc ~1~ trong ~3~ dạng:

• ~1~ ~u~ ~k~: Gán ~A_u~ = ~k~.
• ~2~ ~u~ ~v~: Tìm giá trị của phần tử lớn nhất trong các phần tử có chỉ số từ ~u~ đến ~v~.
• ~3~ ~x~: Lấy lại dãy số ở version thứ ~x~. Các version được đánh số bằng các số nguyên từ ~0~ trở đi. Version đầu tiên (lúc chưa thực hiện thao tác ~1~ hoặc ~3~ nào) có số thứ tự ~0~. Version thứ ~x~ là version sau khi đã áp dụng ~x~ thao tác ~1~ và ~3~.

Input

• Dòng ~1~: Số nguyên dương ~N~ duy nhất

• Dòng ~2~: ~N~ số nguyên dương thể hiện dãy ~A~.

• Dòng ~3~: Gồm hai số nguyên dương ~R~ và ~Q~, chương trình của bạn sẽ lần lượt chạy ~Q~ truy vấn này ~R~ lần.

• ~Q~ dòng tiếp theo, mỗi dòng gồm ~5~ số nguyên dương ~r~, ~a~, ~b~, ~c~, ~d~ mô tả một truy vấn:

  • Đặt ~L~ là kết quả của truy vấn ~2~ gần nhất. Nếu chưa có truy vấn ~2~ nào, ~L~ = ~0~.
  • Nếu ~r = 1~, truy vấn bạn cần trả lời là ~1~ ~u~ ~k~ với ~u = (L \times a+c) \bmod N + 1~, ~k = (L \times b+d) \bmod 10^{9} + 1~.
  • Nếu ~r = 2~, truy vấn bạn cần trả lời là ~2~ ~u~ ~v~ với ~u = (L \times a+c) \bmod N + 1~, ~v = (L \times b+d) \bmod N + 1~. Chú ý rằng trong trường hợp này, ~u~ có thể lớn hơn ~v~, và bạn cần tìm số lớn nhất trong các phần tử có chỉ số từ ~v~ đến ~u~.
  • Nếu ~r~ = ~3~, truy vấn bạn cần trả lời là ~3~ ~x~ với ~x = (L \times a + c) \bmod (P+1)~, với ~P~ là số truy vấn ~1~ và ~3~ đã được thực hiện.

• Chú ý rằng theo cách xây dựng truy vấn được mô tả phía dưới, thì ~Q~ truy vấn đầu tiên bạn trả lời sẽ khác ~Q~ truy vấn tiếp theo, và ~Q~ truy vấn này lại khác ~Q~ truy vấn sau đó.

Output

Với mỗi truy vấn loại 2, in ra một dòng duy nhất là kết quả của truy vấn.

Giới hạn

• 20% test đầu tiên có ~1 \le N~, ~R \times Q \le 1000~
• 20% test tiếp theo không có truy vấn loại ~3~, ~1 \le N~, ~R \times Q \le 10^{5}~.
• 30% test tiếp theo có số lượng truy vấn loại ~3~ không quá ~100~, ~1 \le N~, ~R \times Q \le 10^{5}~
• 30% test cuối cùng có ~1 \le N~, ~R \times Q \le 10^{5}~.
• ~1 \le~ ~A_i~, ~a~, ~b~, ~c~, ~d \le 10^{9}~
• ~R~, ~Q \le 5000~

Sample Input

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

Sample Output

6
7
5
7

Note