题目描述

薯条哥和鸭哥在玩一个卡牌游戏，初始时桌面上有$n$种卡牌，每种卡牌有$a_i$张，这些牌都是背面朝上的。玩家操作时会先翻一张牌，然后

再翻一张牌，若两张牌的类型相同，则玩家获胜，否则，重新将两张票翻回背面朝上，两个玩家轮流操作。

薯条哥和鸭哥总共会玩$q+1$轮游戏。第$1$轮的卡牌数量为初始数量，后续每一轮会在上一轮游戏的基础上，增加或减少一些卡牌，然后将

所有卡牌翻至背面朝上并重新打乱。

增加卡牌的操作为：$+l \ r\ x\$表示第$l$种牌到第$r$种牌各增加$x$张。

增加卡牌的操作为：$-l \ r\ x\$表示第$l$种牌到第$r$种牌各减少$x$张。

每一轮都是由薯条哥先手，薯条哥想让鸭哥获胜，薯条哥想知道他至少需要偷看多少张牌才能保证鸭哥一定能获得胜利？若无法保证鸭哥

一定获得胜利，则输出$-1$

输入描述

第一行输入$2$个正整数$n,q(1\le n,q\le 10^5)$，表示卡牌种类和游戏轮数。

第二行输入$n$个整数$a_i(0\le a_i\le 10^9)$表示数组。

接下来$q$行，每行先输入$1$个字符$c(+/-)$，再输入$3$个数字$l,x(1\le l\le r\le n),x(1\le x\le 10^9)$，表示操作。

数据保证，任意一轮开始前，每种卡牌的数量都为非负整数，且每种卡牌数量之和不小于$2$

输出描述

输出$q+1$行，每行输出一个整数表示答案。

样例

输入

2 1
1 1
+ 2 2 1

输出

-1
1

样例解释

第$1$轮，很显然，薯条哥和鸭哥永远都赢不了。

第$2$轮，薯条哥可以偷看$1$张牌，若看到的是第$1$种牌，则翻开这张牌和任意一张其他牌；若看到的是第$2$种牌，则翻开另外两张牌。