假设手机中有 $k$ 个句子。为了描述每个句子的长度，我们使用一个整数序列 $S = (s_1, s_2, \dots, s_k)$，其中 $s_i$ 是第 $i$ 个句子的长度。已知 $1 \le s_i \le 24$。

为了向用户展示这些句子，手机会按顺序打印它们。然而，由于屏幕宽度有限，一行中句子的总长度不能超过 $24$。此外，为了方便阅读，每个句子必须完整地放在同一行中（换句话说，一个句子不能被拆分到多行）。

满足上述要求的规则如下：第一个句子打印在第一行。对于 $i \ge 2$，如果将第 $i$ 个句子放入当前行后，该行的总长度不超过 $24$，则手机将第 $i$ 个句子打印在最后一行。否则，它会开启新的一行，并将第 $i$ 个句子打印在新行中。

例如，如果 $S = (8, 8, 9, 12, 13)$，句子将按如下方式打印：

现在问题如下： 有 $n$ 个句子，它们的长度分别为 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 24$)。 共有 $m$ 次操作，每种操作属于以下两种类型之一：

• $op1(x, c)$：将第 $x$ 个句子的长度从 $a_x$ 修改为 $c$。
• $op2(\ell, r)$：确定在手机上打印长度为 $S = (a_\ell, a_{\ell+1}, a_{\ell+2}, \dots, a_r)$ 的句子序列时所需的行数。

你的任务是回答所有第二种类型的操作。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 10^5$)，分别表示句子的数量和操作的数量。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 24$)，表示句子的长度。 接下来 $m$ 行，每行包含三个整数，表示上述两种操作之一：

• “$1\ x\ c$”：将第 $x$ 个句子的长度从 $a_x$ 修改为 $c$ ($1 \le x \le n, 1 \le c \le 24$)。
• “$2\ \ell\ r$”：打印将第 $\ell$ 个到第 $r$ 个句子显示在屏幕上所需的行数 ($1 \le \ell \le r \le n$)。

输出格式

对于每个第二种类型的操作，输出一行答案。

样例

输入 1

5 5
8 8 9 12 13
2 1 5
2 2 4
1 5 3
2 1 5
2 2 5

输出 1

3
2
2
2