Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VQUERY - Query

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/vquery


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*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*a+c) mod N + 1, k = (L*b+d) mod 109 + 1.
    • Nếu r = 2, truy vấn bạn cần trả lời là 2 u v với u = (L*a+c) mod N + 1, v = (L*b+d) mod 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*a + c) mod (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 <= N, R*Q <= 1000
  • 20% test tiếp theo không có truy vấn loại 3, 1 <= N, R*Q <= 105
  • 30% test tiếp theo có số lượng truy vấn loại 3 không quá 100, 1 <= N, R*Q <= 105
  • 30% test cuối cùng có 1 <= N, R*Q <= 105
  • 1 <= Ai, a, b, c, d <= 109
  • R, Q <= 5000

Example

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

Output:
6
7
5
7

Giải thích

Input Truy vấn Dãy A Kết quả 
    4 3 7 2 6   
1 0 0 2 4  1 3 5  4 3 5 2 6    
2 0 0 0 4  2 1 5 
3 0 0 0 0  3 0  4 3 7 2 6   
2 0 0 4 0  2 5 1   
3 0 0 1 0  3 1  4 3 5 2 6   
2 0 0 1 3  2 2 4   
3 0 0 2 0  3 2  4 3 7 2 6   
2 0 0 3 1  2 4 2   

Được gửi lên bởi:VOJ Team
Ngày:2013-12-20
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:RR

hide comments
2020-12-07 12:22:09
Trâu cũng AC.
2019-09-24 02:40:20
hahaha
duonght_pro_xinhgainhathemattroi_:)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.