A. 简单数据结构

参加完 IOI2018 之后就是姚班面试。而你，由于讨厌物理、并且想成为乔布斯一样的创业家，被成功踢回贵系。

转眼，时间的指针被指向 2019，大二，12 月初，考试周。

你早听学长说，数据结构期中考很难，对竞赛生不友好，集训队选手做不完卷子。

你冷笑。哼，堂堂国际金，这点难度的考试算什么。

两小时，你看完习题解析前五章所有内容，并且倒背如流；

一小时，你看了 500 页的讲义，并且记忆犹新；

十分钟，你骑车到考场，自信的你只带了一把水笔，虽然考试让带资料；

现在，摊开传说中神级卷子，你定神一看——

给出一个长度为 的序列 ，如果 中的一个子序列 ，满足条件：

• ，

那么称 为 的上升倍数子序列。

现在有一个长度为 的序列 被初始化为 ，以及 次对序列 的操作。此处要求实现如下四种操作：

• 0 x：在序列 的最左端插入一个数字 ；
• 1 x：在序列 的最右端插入一个数字 ；
• 2：移除序列 最左端的一个数字；
• 3：移除序列 最右端的一个数字；

在初始化序列 和每次操作之后，请计算此时序列 中最长上升倍数子序列的长度 ，以及所有长度为 的上升倍数子序列的不同的开头数 ，输出 和 。

为了大幅度降低题目难度，保证在任意时刻序列 非空，其中的元素互不相等，并且均为 之间的正整数；同一个数字最多只会被插入 次。

输入第一行包含三个正整数 ，具体含义见上，保证 ，，；

输入第二行包含 个正整数，为 ，保证 ，并且序列 中的元素互不相等；

接下来共 行输入，每行输入格式形如0 x或者1 x或者2或者3，具体含义见上。

输出共 行，在初始化和每次对序列 操作后，输出 中最长上升倍数子序列的长度 和所有长度为 的上升倍数子序列的不同的开头数 ，用一个空格隔开。

样例输入

5 10 10
1 2 5 9 10
2
1 7
3
3
0 8
3
2
1 8
3
0 3

样例输出

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

样例解释

表格中以//隔开不同开头的最长上升子序列。

对于所有的数据，有 ，，，，。

下表展示了某些数据点的一些特殊约束，其中只有1表示只有形如1 x的操作，其他表述同理。

后记

「奋战两小时，考个四五十」的表情包占领了你的朋友圈：

• 「啊，感觉自己人生完全了。」
• 「但愿……我真的能拿到四五十。」
• 「我考完了……考完了……完了。」
• 「曾经以为是开玩笑的，原来我还是 naïve 了。」

你冷笑。提前半小时交卷，你自然觉得，数据结构，满分，正常。