Start 2022-02-08 12:18:16

20220208分块重现赛

End 2022-02-28 00:00:00
Contest is over.
Now 2026-11-19 00:41:21

E. 数列操作4

Description

给出一个长为n的数列,以及n个操作,操作涉及单点插入,单点询问,数据随机生成。

Input

第一行输入一个数字n(1≤n≤100 000)。 第二行输入n个整型数,第i个数字为ai。 接下来输入n行询问,每行输入4个整型数opt,l,r,c。 若opt=0,表示在第l个数字前插入r(忽略c)。 若opt=1,表示询问ar的值(忽略l和c)。

Output

对于每次询问,输出一行一个数字表示答案。

Examples

Input

4
1 2 2 3
0 1 3 1
1 1 4 4
0 1 2 2
1 1 2 4

Output

2
3

Submit

Login

Signup
Time Limit 1 second
Memory Limit 128 MB
Submit