应教学安排，yy又去开心的做电学实验了。实验的内容分外的简单一串按钮通过编程了的EEPROM可以控制一串彩灯。然而选择了最low的一种一对一的控制模式，并很快按照实验指导书做完实验的yy马上感觉到十分无趣。于是他手指在一排按钮上无聊的滑来滑去，对应的彩灯也不断的变化着开关。已知每一个按钮按下会改变对应一个彩灯的状态，如此每次yy滑动都会改变一串彩灯的状态。现已知彩灯最初的状态，已经yy n次无聊的滑动的起点和终点l,r。现问彩灯最终的状态。

 

Input

有多组数据。

每组数据第一行，n(1<=n<=10^5)代表彩灯串长度，t(0<=t<=10^5)代表yy滑动的次数

第二行n个数（0表示灭1表示亮）给出n个彩灯的目前的状态。

之后t行每行两个数li，ri(1<=li<=ri<=n)代表每次滑动的区间。

 

Output

每组用一行输出最终的串的状态，格式见样例。

 

Sample Input

3 21 0 11 32 3

Sample Output

0 0 1 可以用单个位置的更新模拟出区间更新，详细见代码。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5  6 using namespace std; 7  8 const int maxn=100005; 9 int c[maxn],g[maxn],n;10 11 void update(int x,int v)12 {13     for(;x<=n;x+=x&(-x))14         g[x]+=v;15 }16 17 int getsum(int x)18 {19     int sum=0;20     for(;x>0;x-=x&(-x))21         sum+=g[x];22     return sum;23 }24 25 int main()26 {27     int m,l,r;28     while(~scanf("%d%d",&n,&m))29     {30         memset(g,0,sizeof(g));31         for(int i=1;i<=n;i++)32             scanf("%d",&c[i]);33         for(int i=0;i