神盾牌是科丁小学流行的一种卡牌游戏。与同学们一样，小科非常喜欢这个游戏，直到他遇到了一个手中全是英雄牌的科丁博士....小科觉得这个游戏不应该只靠卡牌好坏取胜，于是他设计了一种超级神盾牌。
 超级神盾牌中只有战士和鼓舞两种卡牌，战士可以对敌方造成一定点数的伤害(不同等级的战士牌造成的伤害不同)，而鼓舞则可以提升战士的伤害点数(不同等级的鼓舞牌提升的点数也不同)，鼓舞牌可以无限次使用，提升的伤害点数叠加。
 游戏开始时，玩家需要选出n张战士牌和n张鼓舞牌，按顺序排好(编号1到n) 。 每一轮游戏，神盾牌系统给出两个随机数l,r。代表这一轮对l到r号战士每人使用第l到r张鼓舞牌各一次。 最后一轮游戏结束后，将所有战士牌的伤害点数(包括鼓舞牌提升的点数)相加，便得到对敌人的伤害总数值。
小科给你了n张战士牌和n张鼓舞牌的排列，他想让你算出在已知神盾牌系统给出的随机数的情况下，他的排列方案中每个战士牌的伤害数值是多少。

第一行两个正整数n和m,代表选出n张战士牌，游戏共有m轮。
第二行n个整数ai(0< ai≤100)，其中ai代表i位置战士牌的伤害点数。
第三行n个整数bi(0≤bi≤100)，其中bi代表 第i张鼓舞牌可以提升的伤害点数。
之后的m行，每行有两个正整数l和r,其中第i行的数li和ri代表第i轮神盾牌系统选出的两个随机数。
数据中1≤n,m≤10^6,1≤li≤ri:≤n。

一行n个整数，代表m轮游戏后每个战士牌的伤害数值。

前缀和 差分数组 level5