题目描述

徐老师最近在做一款新的游戏，现在他准备在这款游戏中增加一个 交易系统，用于玩家们自动化交易游戏中的重要货币——「羊腿」

目前这个系统还比较简单，「羊腿」的交易规则如下：

假设有 $n$ 个玩家参与到游戏币交易过程中，玩家的编号为 $1,2,\cdots,n$，编号 $i$ 的玩家刚开始共有 $a_i$ 元钱，并且拥有 $c_i$ 个「羊腿」。

现在一共发生了 $m$ 次交易，每一次交易共有如下三种不同类型的操作：

1. 1 id x y

   • 表示编号为 $id$ 的人想用 $x$ 元每个的单价购买 $y$ 个「羊腿」。

   • 此时，如果他手上的钱足够 $x \times y$ 元。那么交易系统会查找售卖表中是否存在卖单，如果有，则会将卖价小于等于 $x$ 的卖单，按照卖价从小到大顺序取出，然后依次以卖价进行交易，直到这笔交易完整地完成，或是没有满足条件的卖单为止。如果最后没有满足条件的卖单，并且该笔交易还没有被完全完成，则该笔交易剩余的需求会进入到购买表中进行等待。

   • 如果他手上的钱不足够 $x\times y$，或者他已经有一笔交易（买单或者卖单）尚未完成，则本次交易被驳回。

   • 特别的，当 $x=0$ 时，则买价为当前交易系统最后一次成交的价格，如果之前没有成交过，则为 $0$。

2. 2 id x y

   • 表示编号为 $id$ 的人想用 $x$ 元每个的单价卖出 $y$ 个「羊腿」。

   • 此时，如果他手上的「羊腿」数量足够 $y$ 个。那么交易系统会查找购买表中是否存在买单，如果有，则会将买价大于等于 $x$ 的买单，按照买价从大到小顺序取出，然后依次以买价进行交易，直到这笔交易完整地完成，或是没有满足条件的买单为止。如果最后没有满足条件的买单，并且该笔交易还没有被完全完成，则该笔交易剩余的需求会进入到售卖表中进行等待。

   • 如果他手上的「羊腿」不足 $y$ 个，或者他已经有一笔交易（买单或者卖单）尚未完成，则本次交易被驳回。

   • 特别的，当 $x=0$ 时，则卖价为当前交易系统最后一次成交的价格，如果之前没有成交过，则为 $0$。

3. 3 id

   • 表示编号为 $id$ 的人想要撤回自己正在交易的需求。如果他有一笔买单或者卖单尚未完成，则撤回剩余的还没有完成的交易订单。

   • 如果他没有正在交易的需求，则撤回请求被驳回。

现在，徐老师想知道经过这 $m$ 次交易后，一共成交了多少次交易（每一次金额变动算成交一次），以及每个人手上分别还有多少钱和多少「羊腿」？

【提示】

1. 售卖表和购买表相当于就是一些没有成交的订单组成的两个集合。

2. 在交易时，如果有多笔符合条件的订单，则根据售卖和购买对应的规则按照价格的优先级排序，如果价格一样，则越早的订单越优先。

3. 这 $m$ 次交易操作是按照时间依次产生的

4. 本题的输入输出使用 $scanf,printf$ 会导致超时，请使用 $cin,cout$，并取消同步流，格式如下：

int main(){
    freopen("transaction.in", "r", stdin);
    freopen("transaction.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    输入使用 cin
    cin >> T;

    ......
    输出使用 cout，换行使用 "\n"
    cout << ans << "\n";
}

输入格式

输入第一行包含两个整数 $n,m$ 分别表示参与交易的玩家数量和交易的操作数。

输入第二行包含 $n$ 个整数，$a_1,a_2,\cdots,a_n$ 表示每位玩家初始的资金。

输入第三行包含 $n$ 个整数，$b_1,b_2,\cdots,b_n$ 表示每位玩家初始拥有的「羊腿」数量。

接下来有 $m$ 行，每行形如：1 id x y, 2 id x y, 3 id 表示一笔交易的操作，操作含义如题。

输出格式

输出共三行。

第一行输出交易成交的次数，每一次交易产生了金额的变动就算一次交易成交（撤回操作不算）。

第二行按照编号顺序输出 $n$ 个人剩余的金额。

第三行按照编号顺序输出 $n$ 个人剩余的「羊腿」数量。

数据范围

对于 $50\%$ 的数据，$1\le n \le 1000,1\le m\le 10000$

对于 $100\%$ 的数据，$1\le n \le 10^5$,$1\le m \le 5 \times 10^5$,$1\le id \le n$,$0\le x,a_i,b_i\le 10^9,1\le y \le10^9$。

并且其中所有编号为奇数的测试数据满足：没有撤销操作

样例输入1

2 6
100 100
11 10
1 1 5 10
2 2 4 10
2 2 5 10
1 2 6 20
2 1 0 15
2 1 0 6

样例输出1

3
170 30
1 20

样例解释1

有两个玩家参与交易，分别记为玩家 $A$ 和玩家 $B$。

总共发生了 $5$ 次交易操作，按照交易顺序解释如下：

1. $A$ 想以 $5$ 元每个的单价购买 $10$ 个「羊腿」，此时售卖表中没有卖单，该交易需求进入购买表。

2. $B$ 想以 $4$ 元每个的单价售卖 $10$ 个「羊腿」，此时购买表中有一个 $A$ 的订单（$5$ 元每个购买 $10$ 个「羊腿」），所以 $B$ 以买价 $5$ 元每个成交 $10$ 个「羊腿」获得 $50$ 元。 此时 $A$ 剩余 $100-50=50$ 元 和 $11+10=21$ 个羊腿，$B$ 剩余 $100+50=150$ 元和 $10-10=0$ 个「羊腿」，且购买表和售卖表都为空。

3. $B$ 想以 $5$ 元每个的单价售卖 $10$ 个「羊腿」，由于 $B$ 没有「羊腿」，此交易被驳回，操作失败。

4. $B$ 想以 $6$ 元每个的单价购买 $20$ 个「羊腿」，售卖表中没有卖单，该交易需求进入购买表。

5. $x=0$，表示 $A$ 想以上一次系统交易成功的单价，即 $5$ 元每个出售 $15$ 个「羊腿」，此时购买表中有一个 $B$ 的订单（$6$ 元每个购买 $20$ 个「羊腿」），所以 $A$ 以买价 $6$ 元每个成交 $15$ 个「羊腿」获得 $90$ 元，购买表中 $B$ 的购买订单更新为（$6$ 元每个购买 $5$ 个「羊腿」） 此时 $A$ 剩余 $50+90=140$ 元和 $21-15=6$ 个羊腿，$B$ 剩余 $150-90=60$ 元和 $0+15=15$ 个羊腿，购买表中存在一个 $B$ 的订单。

6. $x=0$，表示 $A$ 想以上一次系统交易成功的单价，即 $6$ 元每个出售 $6$ 个「羊腿」，此时购买表中有一个 $B$ 的订单（$6$ 元每个购买 $5$ 个「羊腿」），所以 $A$ 以买价 $6$ 元每个成交 $5$ 个「羊腿」获得 $30$ 元，$B$ 的购买订单结束，而 A 此时的售卖订单进入售卖表（$6$ 元每个出售 $1$ 个「羊腿」）。 此时 $A$ 剩余 $140+30=170$ 元和 $6-5=1$ 个羊腿，$B$ 剩余 $60-30=30$ 元和 $15+5=20$ 个羊腿，售卖表中存在一个 $A$ 的订单

综上，一共成功交易了 $3$ 次，最终 $A$ 有 $170$ 元和 $1$ 个羊腿，$B$ 有 $30$ 元和 $20$ 个羊腿

样例输入2

2 7
100 100
11 10
1 1 5 10
2 2 4 10
2 2 5 10
1 2 6 20
2 1 0 15
3 2
2 1 0 6

样例输出2

2
140 60
6 15

样例解释2

步骤同上，但是由于在最后一次交易前 $B$ 撤销了自己的剩余的购买订单（$6$ 元每个购买 $5$ 个「羊腿」），所以最后一步 $A$ 在出售羊腿时购买表为空