描述

给定一个N个数的数组，M次操作，每次操作为下列操作之一，求最后的数组。 操作1：在第x个数后插入一个数y 操作2：删除第x个数

输入

第一行2个整数N，M（均≤100000） 第二行N个整数，表示原来的数组 接下来M行，每行第一个数opt，表示操作类型 对于操作1，接下来两个数x，y，表示在第x数后插入一个数y 对于操作2，接下来一个数x，表示要删除第x个数

输出

输出若干个数，表示最后的数组

Samples

5 3
1 2 3 4 5
1 1 6
2 1
2 2

6 3 4 5

Limitation

1s, 1024KiB for each test case.