Thao tác xem, xen, xóa, sửa trên dãy số


Submit solution

Points: 4 (partial)
Time limit: 1.0s
Memory limit: 98M

Author:
Problem type

Cho dãy số nguyên dương \(a_1,a_2,..a_n\) chúng ta có thể thực hiện 4 thao tác với dãy này

  1. Xem giá trị tại vị trí nguyên dương \(k\). Nếu \(k \leq n\) thì xuất ra giá trị \(a_k\) ngược lại thì xuất ra \(-1\)

  2. Chèn vào vị trí nguyên dương \(k\) phần tử có giá trị \(x\) . Nếu \(k \leq n\) thì chèn \(x\) vào vị trí \(k\) nếu \(k>n\) thì chèn vào cuối dãy.

  3. Xóa giá trị tại vị trí nguyên dương \(k\). Nếu \(k \leq n\) thì xóa phần tử tại vị trí \(k\) ngược lại không phải làm gì

  4. Thay thế tại vị trí nguyên dương \(k\) bởi giá trị \(x\). Nếu \(k \leq n\) thì thay thế \(x\) vào vị trí \(k\) nếu \(k>n\) thì không làm gì cả.

Input

Dòng đầu chứa số \(n\) là số phần tử của dãy và số \(m\) là số thao tác thực hiện với dãy này \((1 \leq n,m \leq 10^5)\)

Dòng tiếp theo gồm \(n\) số tự nhiên có giá trị trong khoảng \([0,10^6]\) là các giá trị ban đầu của dãy

Các dòng tiếp theo gồm \(m\) dòng mỗi dòng có giá trị đầu dòng là 1 hoặc 2 hoặc 3 hoặc 4 tương ứng với 4 thao tác xem, chèn, xóa, thay thế tiếp theo là giá trị \(k\) riêng đối với thao tác 2 và 4 thì cuối cùng là giá trị \(x\) là một số tự nhiên có giá trị không vượt quá \(10^6\)

Output

Ứng với các thao tác xem thì xuất ra giá trị xem được mỗi giá trị trên một dòng

Ví dụ

Input

7 8
4 7 2 8 1 6 5
1 3
2 2 9
2 11 0
1 4
4 5 9
3 1
1 20
1 5

Output

2
2
-1
1

Giải thích :

Dãy ban đầu 4 7 2 8 1 6 5

  • Thao tác 1 3 thì xuất ra \(a_3\) là 2

  • Thao tác 2 2 9 chèn vào vị trí 2 số 9 dãy trở thành 4 9 7 2 8 1 6 5

  • Thao tác 2 11 0 chèn vào vị trí 11 số 0 vượt quá miền của nó nên chèn vào cuối dãy dãy trở thành 4 9 7 2 8 1 6 5 0

  • Thao tác 1 4 thì xuất ra \(a_4\) là 2

  • Thao tác 4 5 9 thay thế \(a_5\) thành 9 dãy dãy trở thành 4 9 7 2 9 1 6 5 0

  • Thao tác 3 1 xóa phần tử ở vị trí 1 dãy trở thành 9 7 2 9 1 6 5 0

  • Thao tác 1 20 thì xuất ra \(a_{20}\) nằm ngoài khoảng nên xuất ra \(-1\)

  • Thao tác 1 5 thì xuất ra \(a_5\) là 1

tichpx

Comments


  • 0
    cotyey  commented on Dec. 25, 2019, 2:19 a.m.

    Thầy xem lại output ạ, e code 2 cách: 1 cách blocks linkedlist (đã pass trên spoj) và 1 cách thuần mảng ra kết quả giống nhau nhưng nộp ko pass