题目内容

小美和小美在玩一个卡牌游戏，初始时桌面上有$n$种卡牌，每种卡牌有$a_i$张，这些牌都是背面朝上的。玩家操作时会先翻一张牌，然后再翻一张牌，若两张牌的类型相同，则玩家获胜，否则，重新将两张票翻回背面朝上，两个玩家轮流操作。

小美和小妹总共会玩$q+1$轮游戏。第$1$轮的卡牌数量为初始数量，后续每一轮会在上一轮游戏的基础上，增加或减少一些卡牌，然后将所有卡牌翻至背面朝上并重新打乱。

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

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

每一轮都是由小美先手，小美想让小妹获胜，小美想知道他至少需要偷看多少张牌才能保证小妹一定能获得胜利？若无法保证小美一定获得胜利，则输出$-1$

输入描述

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

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

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

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

输出描述

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

样例1

输入

2 1
1 1
+ 2 2 1

输出

-1
1

说明

第$1$轮，很显然，小美和小美永远都赢不了。

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