Pyramids

Everyone knows that Pharaoh Khufu was a great ruler, but many are unaware that he was also a fashion enthusiast. Long ago, he had $N$ pyramids numbered from $0$ to $N - 1$, where pyramid $i$ ($0 \le i < N$) consists of $A[i]$ stones. He also had the latest catalogue of the most fashionable pyramids of the year. The catalogue has $N$ pyramids numbered from $0$ to $N - 1$, where pyramid $i$ ($0 \le i < N$) consists of $B[i]$ stones.

For any $x$ and $y$ such that $0 \le x \le y < N$, a range of pyramids $A[x..y]$ is the sequence $A[x], A[x + 1], \dots, A[y]$. A range $B[x..y]$ is defined the same way.

Every day, Khufu browses the catalogue and chooses two ranges $A[L..R]$ and $B[X..Y]$ where $R - L = Y - X$. The values of $L$, $R$, $X$, and $Y$ may differ from day to day. He then wants to know whether the range $A[L..R]$ can be transformed into the range $B[X..Y]$. A transformation performs the following step any number of times: take one stone from a pyramid within the range and move it to an adjacent pyramid within the range.

Your task is to answer queries of the following form. Given four integers $L$, $R$, $X$, and $Y$, determine whether $A[L..R]$ can be transformed into $B[X..Y]$. The number of stones in each pyramid does not change. Khufu only wants to know whether one range can be transformed into the other.

Time limit: 1000 ms. Memory limit: 1024 MB.

• $1 \le N \le 100000$
• $1 \le Q \le 100000$
• $1 \le A[i] \le 10^9$
• $1 \le B[i] \le 10^9$

In each call to can_transform:

• $0 \le L \le R < N$
• $0 \le X \le Y < N$
• $R - L = Y - X$