P3765 总统选举

黑恶势力的反攻计划被小 C 成功摧毁，黑恶势力只好投降。秋之国的人民解放了，举国欢庆。此时，原秋之国总统因没能守护好国土，申请辞职，并请秋之国人民的大救星小 C 钦定下一任。 作为一名民主人士，小 C 决定举行全民大选来决定下一任。为了使最后成为总统的人得到绝大多数人认同，小 C 认为，一个人必须获得超过全部人总数的一半的票数才能成为总统。如果不存在符合条件的候选人，小 C 只好自己来当临时大总统。为了尽可能避免这种情况，小 C 决定先进行几次小规模预选，根据预选的情况，选民可以重新决定自己选票的去向。 由于秋之国人数较多，统计投票结果和选票变更也成为了麻烦的事情，小 C 找到了你，让你帮他解决这个问题。

秋之国共有 $n$ 个人，分别编号为 $1,2,…,n$，一开始每个人都投了一票，范围 $1 \sim n$，表示支持对应编号的人当总统。 共有 $m$ 次预选，每次选取编号 $[l_i,r_i]$ 内的选民展开小规模预选，在该区间内获得超过区间大小一半的票的人获胜。如果没有人获胜，则由小 C 钦定一位候选者获得此次预选的胜利（获胜者可以不在该区间内），每次预选的结果需要公布出来，并且每次会有 $k_i$ 个人决定将票改投向该次预选的获胜者。 全部预选结束后，公布最后成为总统的候选人。

无

无

对于前 $20 \%$ 的数据，$1 \leq n,m \leq 5000$。 对于前 $40 \%$ 的数据，$1 \leq n,m \leq 50000$，$\sum k_i \leq 50000$。 对于前 $50 \%$ 的数据，$1 \leq n,m \leq {10}^5$，$\sum k_i \leq 2 \times {10}^5$。 对于数据点 6~7，保证所有选票始终在 $1 \sim 10$ 之间。 对于 $100 \%$ 的数据，$1 \leq n,m \leq 5 \times {10}^5$，$\sum k_i \leq 10^6$，$1 \leq l_i \leq r_i \leq n$，$1 \leq s_i \leq n$。