在三国的烽火乱世中，关羽将军麾下士兵众多，且分布在不同的营地。每个营地都有一定数量的士兵，关羽将军为了更好地掌握军队状况，会不时对士兵数量进行调整，同时也需要了解特定营地区间内，士兵数量为奇数的营地个数，以便做出更精准的战略部署。

题目描述

关羽将军的军队共有 n 个营地，从 1 到 n 依次编号。初始时，每个营地有 a_i 名士兵（1\leq i \leq n）。关羽将军会进行3种指令：

指令 0：关羽会让 [l] 内的所有营地的士兵数量变成x。

指令 1：当关羽将军发出指令时，就会对某个区间 [l, r] 内的所有营地的士兵数量进行修改。具体来说，会给区间 [l, r] 内每个营地的士兵数量都加上一个值 x。

指令 2：关羽将军有时想知道在某个区间 [l, r] 内，士兵数量为奇数的营地一共有多少个，以此来评估该区间内营地的 “精锐程度”。

请你编写一个程序，帮助关羽将军处理这些操作，并输出每次查询操作的结果。

第一行包含两个整数 n 和 m（1\leq n\leq 10^6，1 \leq m \leq 10^6），分别表示营地的数量和操作的次数。

第二行包含 n 个整数 a_1, a_2, \cdots, a_n（1\leq a_i \leq 10^6），表示每个营地初始的士兵数量。

接下来的 m 行，每行表示一个操作，操作分为以下3种类型：

指令0：输入格式为 `0 p x`，表示给营地p的士兵变成 x（1\leq p \leq n，x \leq 10^6）。

指令1：输入格式为 `1 l r x`，表示给区间 [l, r] 内的每个营地的士兵数量都加上 x（1\leq l\leq r\leq n,    1\leq x\leq 10^3）。

指令2：输入格式为 `2 l r`，表示查询区间 [l, r] 内士兵数量为奇数的营地个数（1\leq l \leq r \leq n）。

对于每个查询操作，输出一行一个整数，表示该区间内士兵数量为奇数的营地个数。

40%的数据：n,m \leq 1000;

100%的数据：n,m \leq 10^6;

数据保证在变化的过程中，任意a_i\leq 10^9

样例下载