#include "rainbow.h"
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
typedef pair<int,int> pii;
bool table[500][500];
bool table2[2][2000000];
int r,c;
int CC[2000000][2];
int STm[2000000][32][2];
int STM[2000000][32][2];
void init(int R, int C, int sr, int sc, int M, char *S) {
if(r!=2){
r=R;
c=C;
for(int i=0;i<r;i++){
for(int j=0;j<c;j++)table[i][j]=1;
}
int x,y;
x=sr-1;
y=sc-1;
table[x][y]=0;
for(int i=0;i<M;i++){
char c=S[i];
if(c=='N')x--;
if(c=='S')x++;
if(c=='E')y++;
if(c=='W')y--;
table[x][y]=0;
}
/*for(int i=0;i<r;i++){
for(int j=0;j<c;j++)cout<<table[i][j];
cout<<endl;
}*/
}
if(r==2){
r=R;
c=C;
for(int i=0;i<r;i++){
for(int j=0;j<c;j++)table2[i][j]=1;
}
int x,y;
x=sr-1;
y=sc-1;
table2[x][y]=0;
for(int i=0;i<M;i++){
char c=S[i];
if(c=='N')x--;
if(c=='S')x++;
if(c=='E')y++;
if(c=='W')y--;
table2[x][y]=0;
}
int n=c;
int color=0;
for(int i=0;i<n;i++){
if(table2[0][i]){//cout<<i<<endl;
if(i>0 && table2[0][i-1])CC[i][0]=CC[i-1][0];
else CC[i][0]=color++;
}else CC[i][0]=-1;
//cout<<CC[i][0]<<" ";
}//cout<<endl;
for(int i=0;i<n;i++){
if(table[1][i]){
if(i>0 && table2[1][i-1])CC[i][1]=CC[i-1][1];
else CC[i][1]=color++;
}else CC[i][1]=-1;
//cout<<CC[i][1]<<" ";
}//cout<<endl;
for(int i=0;i<n;i++){
STM[i][0][0]=CC[i][0];
STM[i][0][1]=CC[i][1];
}
for(int j=1;j<32;j++){for(int i=0;i<n;i++){
STM[i][j][0]=max(STM[i][j-1][0],STM[min(n-1,i+(1<<(j-1)))][j-1][0]);
STM[i][j][1]=max(STM[i][j-1][1],STM[min(n-1,i+(1<<(j-1)))][j-1][1]);
}
}
for(int i=0;i<n;i++){
STm[i][0][0]=CC[i][0];
STm[i][0][1]=CC[i][1];
if(CC[i][0]==-1)STm[i][0][0]=n+1;
if(CC[i][1]==-1)STm[i][0][1]=n+1;
}
for(int j=1;j<32;j++){
for(int i=0;i<n;i++){
STm[i][j][0]=min(STm[i][j-1][0],STm[min(n-1,i+(1<<(j-1)))][j-1][0]);
STm[i][j][1]=min(STm[i][j-1][1],STm[min(n-1,i+(1<<(j-1)))][j-1][1]);
}
}
}
}
int colour(int ar, int ac, int br, int bc){
ar--;
ac--;
br--;
bc--;
if(r!=2){
bool visited[r][c];
for(int x=ar;x<=br;x++){
for(int y=ac;y<=bc;y++){
visited[x][y]=false;
}
}
int CC=0;
for(int x=ar;x<=br;x++){
for(int y=ac;y<=bc;y++){
if(!visited[x][y] && table[x][y]){
queue<pii>q;
q.push(pii(x,y));
while(!q.empty()){
pii p=q.front();q.pop();
if(ar<=p.first && p.first<=br && ac<=p.second && p.second<=bc && !visited[p.first][p.second] && table[p.first][p.second]){
visited[p.first][p.second]=true;
q.push(pii(p.first-1,p.second));
q.push(pii(p.first+1,p.second));
q.push(pii(p.first,p.second+1));
q.push(pii(p.first,p.second-1));
}
}
CC++;
}
}
}
return CC;
}
int pow=28;
while((1<<pow)>bc-ac+1){
pow--;
}
if(ar==br){
int maximo=max(STM[ac][pow][ar],STM[bc-(1<<pow)+1][pow][ar]);
int minimo=min(STm[ac][pow][ar],STm[bc-(1<<pow)+1][pow][ar]);
//cout<<maximo<<" "<<minimo<<" "<<pow<<endl;
if(maximo==-1)return 0;
return maximo-minimo+1;
}
int CC=0;
for(int a=ar;a<=br;a++){
int maximo=max(STM[ac][pow][a],STM[bc-(1<<pow)+1][pow][a]);
int minimo=min(STm[ac][pow][a],STm[bc-(1<<pow)+1][pow][a]);
//cout<<maximo<<" "<<minimo<<endl;
if(maximo>=0)CC+=maximo-minimo+1;
}//cout<<CC<<endl;
if(table2[0][ac] && table2[1][ac])CC--;
if(bc!=ac && table2[0][bc] && table2[1][bc] && CC>1)CC--;
return CC;
}
