小H给你一个数组{a}，要求支持以下两种操作： 1. 0 l r(1，询问区间[l,r]中权值和最大的有效子区间的权值和，一个子区间被认为是有效的当且仅当这个子区间中没有两个相邻的偶数或者奇数。 2. 1 x v(199)，将a[x]的值修改为v。

输入描述:

第一行读入两个正整数n,m(15)第二行读入n个整数，第i个表示a[i](-109 9)接下来m行，每行三个数表示操作，描述见题目描述。

输出描述:

输出每个询问的答案。