U145767 「AnOI 2020」デート·ア·ライブ

>さあ，私たちのデートを始めましょう #### 人物设定 五河士道（いつか しどう）：由于过去的事件，发现自己有封印精灵灵力的能力。之后在义妹五河琴里的协助下，拯救了数名精灵。他是对有为难之人与悲伤之人绝不冷漠避之并为之敞开心胸的善良青年。 夜刀神十香（やとがみとおか）：在五河士道面前现身的第一个精灵，识别代号〈公主（Princess）〉。拥有一头及膝的黑色长发与水晶般不可思议色彩的眼睛。由于每次出现都遭到人类攻击，使她对人类充满恐惧与敌意，但在与士道相遇后逐渐改变她对人的观感，变得非常喜爱人类的世界。个性天然、喜欢士道，在士道和其他女孩子亲密时会吃醋暴走，但在得知士道行动的真意后会宣布支持士道。 鸢一折纸（とびいち おりがみ）：一头白发，像人偶一样无性格的少女。身份是陆上自卫队的对精灵部队AST的队员，阶级是上士。 五年前因精灵的现身而令双亲命丧，所以极度的憎恨着精灵。为了不会再让别人遇上和自己一样的惨剧并为父母报仇，以消灭精灵为目标而奋斗着。后期精灵化，为追寻五年前杀害双亲的〈幻影〉，借用回到过去，发现杀死父母之死的真相后精神崩溃，导致灵结晶反转。对整个天宫市展开无差别的全方位攻击。之后被士道拯救并改变过去，对其称爱情现在才开始。 冰芽川四糸乃（よしの）：长相宛若法国娃娃般美丽的蓝发少女，有着梦幻般的外貌和娇小的身材，外表年纪与五河琴里相近。第二位登场的精灵，识别名为〈隐居者（Hermit）〉。生性温驯而胆小怕生，几乎不敢与人直接对话。左手拿着的兔子型的手偶四糸奈（よしのん）是独立的人格，也是她最好的朋友。喜欢和士道在一起。 万由里（まゆり）：总是一个人静静的向士道投去视线的单马尾发型的少女。穿着来禅高校和龙胆寺女学院不一样的高中学校的制服。在和五河士道互露心声后不舍的离去。

#### 题目背景 & 描述 因为万由里的天使 **〈万象圣堂〉** ，所以士道需要和所有精灵约会。 这天轮到了十香， 十香便带着士道去了自己最爱去吃东西的一条街上， 准备把整条街都吃一遍。 可是折纸大师却表示不能将士道的身体吃坏， 便赶忙去追正在约会的士道和十香。 可是十香却早已和士道混入了人群。 无可奈何的折纸大师只好询问在一旁偷看的四系乃。 四系乃告诉折纸大师刚才士道和十香到了某个范围内的第 $K$ 矮的店里。 可是十香带着士道一路走一路吃， 所以折纸大师只好反复询问。 不过需要注意， 因为这一条街都是由生命树控制， 所以有些时候某些店会升高（虽然原番中不会） #### 一句话题意 给出一个区间， 进行 $q$ 次操作 每次操作有两种情况 1. `C l r x` ：此时将 $[l, r]$ 中所有区间的数加上 $x$。 2. `F l r k` ：此时输出 `l:x`， 其中 $l$ 为此时是第几个操作， $x$ 为区间的第 $k$ 小的值， 如果区间内的数不足 $k$ 个则输出 $0$

第一行两个数 $n$ 和 $q$， 表示初始有的房屋数量和操作数量 第二行 $n$ 个数， 表示初始房屋数量 接下来 $q$ 行， 分别表示每次操作。

每行输出一行`l:x`表示查询是第几个操作并且应该输出什么

对于前 $50\%$ $1 ≤ n ≤ 25000$ $1 ≤ q ≤ 25000$ $1 ≤ l ≤ r ≤ n$ 对于另外 $50\%$ $1 ≤ n ≤ 50000$ $1 ≤ q ≤ 50000$ $1 ≤ l ≤ r ≤ n$ 数据保证操作过程中没有一个数超过 $1000000$