第三位神秘博士曾经正确地说过,平行宇宙之间的旅行“就像横向旅行”。然而,他错误地认为存在无限个平行宇宙,而事实上,众所周知,平行宇宙永远不会超过250个。
海蒂最近得到了一个多元宇宙观察工具。她能够看到所有 $$$n$$$ 宇宙排成一排,它们之间不存在任何联系。她还注意到博士位于第 $$$k$$$ 宇宙中。
该工具还指出,由于时空不连续性的限制,宇宙的数量永远不会超过$$$m$$$。
显然,多元宇宙由于自由意志而不稳定。每次做出决定时,都会随机发生两个事件之一:创建一个新的平行宇宙,或者打破一个不存在的链接。
更具体地说,
- 当一个宇宙被创建时,它会在任何两个相邻的宇宙之间或一端出现。
- 当链接断开时,任何两个相邻宇宙之间的链接都可能被切断。将多元宇宙分成两部分后,不包含博士的部分将不复存在。
Heidi 想要执行 $$$t$$$ 决策的模拟。每次做出决定时,海蒂都想知道多元宇宙的长度(即宇宙的数量),以及博士的位置。
输入
第一行包含四个整数 $$$n$$$、$$$k$$$、$$$m$$$ 和 $$$t$$$ ($$$2 \le k \le n \le m \le 250$$$、$$$1 \le t \le 1000$$$)。
以下 $$$t$$$ 行均采用以下格式之一:
- "$$$1$$$ $$$i$$$" — 表示在 $$$i$$$ ($$$1 \le i \le l + 1$$$) 位置插入宇宙,其中 $$$l$$$ 表示多重宇宙的当前长度。
- "$$$0$$$ $$$i$$$" — 表示第 $$$i$$$ 链接已损坏 ($$$1 \le i \le l - 1$$$),其中 $$$l$$$ 表示多元宇宙的当前长度。
输出
输出 $$$t$$$ 行。每行应包含 $$$l$$$(多元宇宙的当前长度)和 $$$k$$$(Doctor 的当前位置)。
保证步骤的顺序有效,即多元宇宙的长度最多为$$$m$$$,并且当执行链接断开时,多元宇宙中将至少存在一个宇宙。
示例
输入 #1
5 2 10 4 0 1 1 1 0 4 1 2
输出 #1
4 1 5 2 4 2 5 3
注意
多元宇宙最初由 5 个宇宙组成,博士位于第二个宇宙。
首先,链接 1 被破坏,多元宇宙留下了 4 个宇宙,博士在第一个宇宙中。
然后,在多元宇宙的最左端添加了一个宇宙,将多元宇宙的长度增加到5,然后博士就在第二个宇宙中。
然后,最右边的链接被破坏了。
最后,在第一个和第二个宇宙之间添加了一个宇宙。