很多数字的替换操作

题目描述

给定 n 个非负整数和 q 次操作。每次操作给出三个两两不同的位置 k、i、j，将第 k 个数替换为第 i 个数与第 j 个数的和，或者替换为二者之差的绝对值。两种结果奇偶性相同。每次操作后输出当前序列中奇数的个数。

输入格式

第一行输入整数 n、q，满足 3≤n≤2×10^5、1≤q≤2×10^5。第二行输入 n 个整数 a1,a2,…,an，满足 0≤ai≤10^18。接下来 q 行，每行输入 k、i、j，满足 1≤k,i,j≤n 且三者两两不同。操作按输入顺序执行。

输出格式

每次操作后输出一行，表示当前 n 个数中奇数的个数，共输出 q 行。

样例

输入

4 2
1 2 3 4
2 1 3
4 2 3

输出

2
3