{"code":"querymax4","name":"Query-Max 4","description":"Cho số nguyên $A$ gồm $N$ phần tử gồm các số nguyên dương $A_1, A_2, ..., A_N$. Cho $Q$ thao tác được thực hiện lần lượt bao gồm gán, truy vấn và quay lại: (Gọi $T$ là số lần gán. Ban đầu $T = 0$).\r\n+ Thao tác gán có dạng: $1$ $p$ $val$: Gán $A_p = val$ ($1 \\leq p \\leq N$, $1 \\leq val \\leq 10^9$). Và $T$ sẽ tăng lên $1$.\r\n+ Thao tác truy vấn có dạng: $2$ $u$ $v$ $t$: Tìm giá trị lớn nhất trong đoạn từ $u$ tới $v$ sau phép gán lần thứ $t$ ($1 \\leq u \\leq v \\leq N$, $0 \\leq t \\leq T$. Nếu $t = 0$ thì sẽ truy vấn trên mảng ban đầu trước khi thực hiện $Q$ thao tác). \r\n+ Thao tác quay lại có dạng: $3$ $t$: Quay lại thời điểm sau lần gán thứ $t$ ($0 \\leq t \\leq T$. Nếu $t = 0$ thì sẽ quay về mảng ban đầu trước khi thực hiện $Q$ thao tác). Mọi thao tác gán sau thời điểm $t$ sẽ bị xoá bỏ. Và $T = t$.\r\n\r\n##Yêu cầu##\r\nThực hiện lần lượt $Q$ thao tác. Với thao tác loại $2$ (Truy vấn), in ra kết quả.\r\n\r\n##Dữ liệu vào##\r\n+ Dòng thứ nhất chứa hai số nguyên dương $N$ và $Q$.\r\n+ Dòng thứ hai chứa $N$ số nguyên dương $A_1, A_2, ..., A_N$ ($A_i \\leq 10^9$).\r\n+ $Q$ dòng tiếp theo, mỗi dòng là một thao tác gán, truy vấn hoặc quay lại: $1$ $p$ $val$ hoặc $2$ $u$ $v$ $t$ hoặc $3$ $t$. \r\n\r\n##Kết quả##\r\nVới thao tác loại $2$, in ra kết quả trên một dòng.\r\n\r\n##Ràng buộc##\r\n+ $30\\%$ số test đầu tiên tương đương với $30\\%$ số điểm có $N, Q \\leq 10^3$.\r\n+ $30\\%$ số test tiếp theo tương đương với $30\\%$ số điểm có $N, Q \\leq 10^5$, không có thao tác $3$, mọi thao tác $2$ có $t = T$ \r\n+ $40\\%$ số test còn lại tương đương với $40\\%$ số điểm có $N, Q \\leq 10^5$.\r\n\r\n##Ví dụ##\r\n\r\n**Input**:\r\n\r\n    5 8\r\n    1 5 4 7 8\r\n    1 3 2\r\n    2 2 4 0\r\n    1 1 5\r\n    1 4 6\r\n    2 1 5 2\r\n    2 3 4 3\r\n    3 1\r\n    2 3 4 1\r\n\r\n**Output**:\r\n\r\n    7\r\n    8\r\n    6\r\n    7","points":450.0,"partial":true,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}