Background

三体舰队发出的水滴提前到达地球惊扰了沉睡中的愚者，愚者通过愚弄时间缩短了三体舰队到达的时间，使得三体舰队一瞬间就到了地球，随后愚者为操纵三体舰队必须先削弱三体舰队的防御，愚者使用海神权柄对三体舰队造成范围伤害

Description

三体舰队有 $n$ 艘战舰，一字排开，编号从 $1～n$，第 $i$ 艘战舰的防御力为 $ai$，愚者使用海神权柄可以对范围 $[l,r]$ 的战舰造成 $ai/3$（向上取整）的伤害，同时，为保留战舰能力，不对 ai<10 的战舰造成伤害

为掌控战场的变化，需要通识者途径的你为愚者汇报情况：

在区间 $[l,r]$ 有多少艘战舰 ai<100

在区间 $[l,r]$ 的舰队总防御力

Input

第一行 $n(1<=n<=10^5)，m(1<=m<=10^5)$ 战舰数量及操作次数

第二行 $n$ 个数表示 $ai(1<=ai<=10^5)$

随后 $m$ 行，格式为 $op\ l\ r$

$op=1$，愚者对区间 $[l,r]$ 造成伤害

$op=2$，你需要向愚者汇报区间 $[l,r]$ 有多少艘战舰ai<100

$op=3$，你需要向愚者汇报区间 $[l,r]$ 的舰队总防御力

Output

对 $op=2/3$ 的操作输出答案

Samples

input1

5 5
1 10 100 1000 10000
2 1 5
3 1 5
1 1 5
2 1 5
3 1 5

output1

2
11111
3
7405