背景

010010010 1000001 00100100101001 00111110 11101111111111111010. . . . . .

你没做太多思考，将一串数据插入其中。

你一直维护着蛮荒之地的堪称完美的科技造物——数据方尖碑，不管用何种更精确的方式测量，穷尽所有的测量技术的最高精度，方碑三边的比例仍是精确的1∶4∶9，没有任何误差。造物者以这种方式，狂妄地显示了自己的力量。

但这和你有什么关系呢，你只负责将随着时间流逝而缺失的数据串，正确的插入合适的位置。

“世界上一切生命消逝后都会成为一串数据被储存起来，世界上一切的数据最终都会流入这里，或许有一天我也会。”你无端的这样想着。但这和你有什么关系呢，你只需要看着方碑，重复这枯燥的事情，直到一切的尽头......

题目描述

请尽到你的责任，将数据插入正确的位置，以保证数据方尖碑的正常运转。 将M行数据按照给出的位置插入N行数据中,插入数据后，插入位置前面的数据不变，插入位置原本的数据及之后的数据序号往后移一位。

插入多行数据时，按照给出的顺序从上往下依次插入。

Format

Input

第一行为整数N,M

接下来前N行，每行给出序号和一串数据

后M行，每行给出要插入的位置和数据

Output

处理后的数据

Samples

3 2
1 cat 111111000000110
2 fish 1001110101101
3 dog 100001010
2 bird 100001
1 human 1111111111

1 human 1111111111
2 cat 111111000000110
3 bird 100001
4 fish 1001110101101
5 dog 100001010

Limitation

对于 100% 的数据，保证 N≤10,M≤10, 所有名字长度 生命数据长度 ≤20。

1s, 1024KiB for each test case.