#include using namespace std; using ll=long long; ll linf=1000000000000000000; template bool chmax(T& a,T b){ if(a bool chmin(T& a,T b){ if(a>b){ a=b; return true; }else return false; } vector dx={1,0,-1,0}; vector dy={0,1,0,-1}; struct bomb{ ll c,l; int id; vector> range; bomb(){} bomb(ll c,ll l,int id):c(c),l(l),id(id){range.resize(l);} }; struct bomb_instance{ int x,y; int id; bomb_instance(){} bomb_instance(int x,int y,int id):x(x),y(y),id(id){} }; int n,m; vector bombs; vector locates; vector grid; string ans; int ans_count; void read_input(){ cin>>n>>m; ans_count=0; bombs.resize(m); grid.resize(n); for(int i=0;i>grid[i]; for(int i=0;i>c>>l; bombs[i]=bomb(c,l,i); for(int j=0;j>a>>b; bombs[i].range[j]=make_pair(a,b); } } sort(bombs.begin(),bombs.end(),[](bomb a,bomb b)->bool{ return a.c copy_grid=grid; auto good_bomb=[&](int x,int y)->void{ bomb_instance res; int max_score=0; for(int i=0;i0||ly>0)continue; }else{ if(lx>0||ly<0)continue; } }else{ if(y0)continue; }else{ if(lx<0||ly<0)continue; } } if(abs(nx)+abs(ny)=n||my<0||my>=n)continue; if(copy_grid[mx][my]!='.')score++; } if(score>max_score){ max_score=score; res=bomb_instance(x-nx,y-ny,bombs[i].id); } } int index=0; for(int i=0;i=n||res.y+ly<0||res.y+ly>=n)continue; copy_grid[res.x+lx][res.y+ly]='.'; } locates.push_back(res); }; for(int i=0;i=n/2||i-j>=n/2)continue; int x=j,y=i-j; if(copy_grid[x][y]!='.')good_bomb(x,y); if(copy_grid[n-1-x][y]!='.')good_bomb(n-1-x,y); if(copy_grid[x][n-1-y]!='.')good_bomb(x,n-1-y); if(copy_grid[n-1-x][n-1-y]!='.')good_bomb(n-1-x,n-1-y); //for(string s:copy_grid)cout<next_x){ for(int i=0;inext_y){ for(int i=0;inow_y){ for(int i=0;ii+j){ nearest_shop_x=i;nearest_shop_y=j; } } go_straight(0,nearest_shop_x*n+nearest_shop_y); for(bomb_instance b:locates){ ans+="2 "+to_string(b.id+1)+"\n"; ans_count++; } int now_x=nearest_shop_x,now_y=nearest_shop_y; int q=locates.size(); for(int i=0;i