农夫约翰的N头奶牛（1≤N≤1.5⋅105）的产奶值分别是a1,…,aN（保证为整数）。也就是说，第i头奶牛每分钟产生ai单位的牛奶，其中0≤ai≤108。

每天早上，农夫约翰开始时将所有N头奶牛连接到他的挤奶机上。他必须逐一将它们解开，然后将它们送出去进行每日锻炼。奶牛挤奶的时间是有规律的：第一头奶牛在挤奶1分钟后就解开，第二头奶牛在挤奶2分钟后解开，依此类推。因为第一头奶牛（假设为奶牛x）只在挤奶机上停留了1分钟，所以她只贡献了ax单位的总牛奶。第二头奶牛（假设为奶牛y）总共在挤奶机上停留了两分钟，因此她贡献了2ay单位的总牛奶。第三头奶牛（假设为奶牛z）贡献了3az总单位的牛奶，依此类推。让T代表农夫约翰可以在最佳顺序下收集的最大牛奶总量。

农夫约翰好奇，如果他的牛群中的有一头奶牛的产奶值产生了变化，T会受到什么影响。对于每个查询（1≤Q≤1.5⋅105），由两个整数i和v指定，表示ai被设置为v（0≤v≤108），则T的新值是多少。请注意，每次查询结束后，ai会恢复到初始值。