Đô-mi-nô năm mới

Có $n$ quân đô-mi-nô đứng trên trục số. Quân thứ $i$ đứng tại tọa độ $p_i$ và có chiều cao $l_i$; các tọa độ thỏa mãn $p_1<p_2<\dots <p_n$.

Khi một quân đô-mi-nô đứng tại $p$ với chiều cao $l$ bị đẩy sang phải, nó đổ xuống và quét qua đoạn $[p,p+l]$ trên trục số. Nếu trong lúc đổ nó chạm vào một quân khác (quân thứ $j$ có $p_j\le p+l$) thì quân $j$ cũng đổ sang phải theo đúng cơ chế đó, và phản ứng dây chuyền tiếp tục. Nói cách khác, nếu ta đang đứng ở "tầm với" hiện tại $R$ và quân kế tiếp có tọa độ $p_j\le R$ thì quân đó đổ và tầm với được cập nhật thành $max(R,p_j+l_j)$.

Có $q$ kịch bản, mỗi kịch bản gồm hai số $x$ và $y$ ($x<y$): ta đẩy quân thứ $x$ và muốn quân thứ $y$ cũng đổ. Đôi khi điều này không xảy ra vì có "khoảng hụt" giữa tầm với hiện tại và quân kế tiếp. Ta được phép tăng chiều cao của một số quân đô-mi-nô (bất kỳ quân nào), mỗi lần tăng chiều cao thêm $1$ tốn chi phí $1$.

Với mỗi kịch bản, hãy tìm chi phí nhỏ nhất để khi đẩy quân $x$ thì quân $y$ chắc chắn đổ. Các kịch bản độc lập với nhau: việc tăng chiều cao trong kịch bản này không ảnh hưởng đến kịch bản khác.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$.
• $n$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $p_i$ và $l_i$.
• Dòng tiếp theo chứa số nguyên $q$.
• $q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x_j$ và $y_j$.

Dữ liệu ra

Với mỗi kịch bản, in ra một dòng chứa chi phí nhỏ nhất cần thiết. Nếu không cần chi phí nào, in ra $0$.

Ràng buộc

• $2\le n\le 2·{10}^5$
• $1\le p_i,l_i\le {10}^9$ và $p_1<p_2<\dots <p_n$
• $1\le q\le 2·{10}^5$
• $1\le x_j<y_j\le n$

Ví dụ