import java.util.*; import java.io.*; public class Main { public static void main (String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] first = br.readLine().split(" ", 2); int n = Integer.parseInt(first[0]); int q = Integer.parseInt(first[1]); BinaryIndexedTree bit = new BinaryIndexedTree(n + 1); String[] second = br.readLine().split(" ", n); for (int i = 0; i < n; i++) { bit.add(i + 1, Integer.parseInt(second[i])); } SegmentTree st = new SegmentTree(n + 1); StringBuilder sb = new StringBuilder(); for (int i = 0; i < q; i++) { String[] line = br.readLine().split(" ", 2); int type = Integer.parseInt(line[0]); int x = Integer.parseInt(line[1]); if (type == 1) { int left = st.getLeft(x); int right = st.getRight(x + 1); st.update(left, right, left, right); } else if (type == 2) { int left = st.getLeft(x); int right = st.getRight(x + 1); st.update(left, x, left, x); st.update(x + 1, right, x + 1, right); } else if (type == 3) { bit.add(x, 1); } else { int left = st.getLeft(x); int right = st.getRight(x); sb.append(bit.getSum(left, right)).append("\n"); } } System.out.print(sb); } } class SegmentTree { static final int INF = Integer.MAX_VALUE; int size; int base; int[] lefts; int[] rights; public SegmentTree(int size) { this.size = size; base = 1; while (base < size) { base <<= 1; } lefts = new int[base * 2 - 1]; rights = new int[base * 2 - 1]; for (int i = 1; i <= size; i++) { lefts[base - 1 + i] = i; rights[base - 1 + i] = i; } } public int getLeft(int idx) { return getLeftTree(idx + base - 1); } public int getLeftTree(int idx) { if (idx == 0) { return lefts[idx]; } int ans; if (idx % 2 == 1) { ans = getLeftTree((idx - 1) / 2); } else { ans = getLeftTree((idx - 1) / 2); } if (ans == 0) { return lefts[idx]; } else { return ans; } } public int getRight(int idx) { return getRightTree(idx + base - 1); } public int getRightTree(int idx) { if (idx == 0) { return rights[idx]; } int ans; if (idx % 2 == 1) { ans = getRightTree((idx - 1) / 2); } else { ans = getRightTree((idx - 1) / 2); } if (ans == 0) { return rights[idx]; } else { return ans; } } public void update(int min, int max, int valueL, int valueR) { update(min, max, 0, valueL, valueR, 0, base); } public void update(int min, int max, int idx, int valueL, int valueR, int left, int right) { if (min >= right || max < left) { return; } if (min <= left && right - 1 <= max) { lefts[idx] = valueL; rights[idx] = valueR; return; } update(min, max, 2 * idx + 1, valueL, valueR, left, (left + right) / 2); update(min, max, 2 * idx + 2, valueL, valueR, (left + right) / 2, right); if (lefts[idx] != 0) { int tmpL = lefts[idx]; int tmpR = rights[idx]; lefts[idx] = 0; rights[idx] = 0; if (left < min) { update(left, min - 1, idx, tmpL, tmpR, left, right); } if (max < right - 1) { update(max + 1, right, idx, tmpL, tmpR, left, right); } } } } class BinaryIndexedTree { int size; long[] tree; public BinaryIndexedTree(int size) { this.size = size; tree = new long[size]; } public void add(int idx, int value) { int mask = 1; while (idx < size) { if ((idx & mask) != 0) { tree[idx] += value; idx += mask; } mask <<= 1; } } public long getSum(int from, int to) { return getSum(to) - getSum(from - 1); } public long getSum(int x) { int mask = 1; long ans = 0; while (x > 0) { if ((x & mask) != 0) { ans += tree[x]; x -= mask; } mask <<= 1; } return ans; } }