// http://infoarena.ro/problema/walls
#include <fstream>
#include <map>
using namespace std;
#define maxSize 100001
#define x first
#define y second
#define leftSon (node<<1)
#define rightSon (node<<1)+1
ifstream in("walls.in");
ofstream out("walls.out");
struct stuff {
long long x;
int width;
};
int nrWalls,bombs;
stuff wall[maxSize];
int tree[4*maxSize];
// de cate ori s-a lovit zidul first la inaltimea second
map< pair<int,int>, int> hits;
void update(int node,int left,int right,int position,int hits);
int query(int node,int left,int right,int x,int hits);
int main() {
in >> nrWalls;
int currentHeight;
for(int i=1;i<=nrWalls;i++) {
// latimea si inaltimea zidului
in >> wall[i].width >> currentHeight;
// ordonata sa este ordonata zidului precedent
// plus latimea acestuia plus unu (distanta intre ziduri)
wall[i].x = wall[i-1].x + wall[i-1].width + 1;
// se introduce inaltimea sa in arborele de intervale
update(1,1,nrWalls,i,currentHeight);
}
in >> bombs;
int targetWall,hitBlock;
pair<int,int> currentBomb;
for(int i=1;i<=bombs;i++) {
in >> currentBomb.x >> currentBomb.y;
targetWall = query(1,1,nrWalls,currentBomb.x,currentBomb.y);
if(!targetWall)
out << "MISS\n";
else {
out << "HIT ";
// creste numarul loviturilor in zid la inaltimea abscisei bombei
hits[make_pair(targetWall,currentBomb.y)]++;
// ordonate celului lovite (ordonata zidului plus latimea acestuia
// minus de cate ori a fost bombardata linia resprectiva
hitBlock = wall[targetWall].x + wall[targetWall].width - hits[make_pair(targetWall,currentBomb.y)];
out << hitBlock << " " << targetWall << " ";
// daca ordonata celulei lovite este egala
// cu ordonata zidului (s-a distrus un nivel intreg)
if(hitBlock == wall[targetWall].x) {
out << "YES\n";
// se actualizeaza inaltimea zidului curent cu abscisa bombei minus unu
update(1,1,nrWalls,targetWall,currentBomb.y-1);
}
else
out << "NO\n";
}
}
in.close();
out.close();
return (0);
}
void update(int node,int left,int right,int position,int height) {
if(left == right)
tree[node] = height;
else {
int middle = (left + right) >> 1;
if(position <= middle)
update(leftSon,left,middle,position,height);
else
update(rightSon,middle+1,right,position,height);
tree[node] = max(tree[leftSon],tree[rightSon]);
}
}
int query(int node,int left,int right,int x,int height) {
// daca abscisa zidului din extremitatea stanga a intervalului
// este mai mare decat abscisa cautata sau inaltimea
// zidului curent este mai mica decat cea cautata
// (intervalul in care cautam nu este bun)
if(wall[left].x > x || tree[node] < height)
return (0);
if(left == right)
return left;
int answer;
int middle = (left + right) >> 1;
answer = query(rightSon,middle+1,right,x,height);
if(!answer)
return query(leftSon,left,middle,x,height);
else
return answer;
}