Sanae and Giant Robot
Contest: Codeforces Round 796 (Div. 1)
Difficulty rating: 2500
Tags: binary search, brute force, data structures, dsu, greedy, sortings

The state of a robot can be represented by an array of integers of length $$$n$$$. Initially, the robot is at state $$$a$$$. She wishes to turn it into state $$$b$$$.

As a great programmer, Sanae knows the art of copy-and-paste. In one operation, she can choose some segment from given segments, copy the segment from $$$b$$$ and paste it into the same place of the robot, replacing the original state there. However, she has to ensure that the sum of $$$a$$$ does not change after each copy operation in case the robot go haywire. Formally, Sanae can choose segment $$$[l,r]$$$ and assign $$$a_i = b_i$$$ ($$$l\le i\le r$$$) if $$$\sum\limits_{i=1}^n a_i$$$ does not change after the operation.

Determine whether it is possible for Sanae to successfully turn the robot from the initial state $$$a$$$ to the desired state $$$b$$$ with any (possibly, zero) operations.

Input format:
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 2\cdot 10^4$$$) — the number of test cases. The descriptions of the test cases follow.

The first line of each test case contains two integers $$$n$$$, $$$m$$$ ($$$2 \leq n\leq 2\cdot 10^5$$$, $$$1 \leq m\leq 2\cdot 10^5$$$) — the length of $$$a$$$, $$$b$$$ and the number of segments.

The second line contains $$$n$$$ intergers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the initial state $$$a$$$.

The third line contains $$$n$$$ intergers $$$b_1,b_2,\ldots,b_n$$$ ($$$1 \leq b_i \leq 10^9$$$) — the desired state $$$b$$$.

Then $$$m$$$ lines follow, the $$$i$$$-th line contains two intergers $$$l_i,r_i$$$ ($$$1 \leq l_i < r_i \leq n$$$) — the segments that can be copy-pasted by Sanae.

It is guaranteed that both the sum of $$$n$$$ and the sum of $$$m$$$ over all test cases does not exceed $$$2 \cdot 10 ^ 5$$$.

Output format:
For each test case, print "YES" (without quotes) if $$$a$$$ can be turned into $$$b$$$, or "NO" (without quotes) otherwise.

You can output "YES" and "NO" in any case (for example, strings "yEs", "yes" and "Yes" will be recognized as a positive response).

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
Test case 1:

One possible way of turning $$$a$$$ to $$$b$$$:

First, select $$$[1,3]$$$. After the operation, $$$a=[3,2,5,2,3]$$$.

Then, select $$$[2,5]$$$. After the operation, $$$a=[3,2,5,4,1]=b$$$.

Test case 2:

It can be shown that it is impossible to turn $$$a$$$ into $$$b$$$.

Example input:
2
5 2
1 5 4 2 3
3 2 5 4 1
1 3
2 5
5 2
1 5 4 2 3
3 2 4 5 1
1 2
2 4

Example output:
YES
NO

Editorial:
Let $$$s_i=\sum\limits_{k=1}^i a_k-b_k$$$. The task can be described as:
Given an array $$$s$$$. For some given interval $$$[l,r]$$$ if $$$s_{l-1}=s_r$$$, we can assign $$$s_r$$$ to $$$s_i$$$ ($$$l\le i< r$$$). The goal is to make $$$s_i=0$$$ ($$$0\le i\le n$$$).
Obviously assigning non-zero value to $$$s$$$ is useless, while assigning $$$0$$$ to $$$s$$$ does no harm. Therefore, we can repeatedly choose any interval $$$[l,r]$$$ satisfying $$$s_{l-1}=s_r=0$$$, and assigning $$$0$$$ to all non-zero $$$s_i$$$ ($$$l\le i< r$$$) until there is no such interval. We can use set in c++ or disjoint set to find such $$$i$$$. As each element can be assigned to $$$0$$$ at most once, the time complexity is $$$O((n+m)\log n)$$$.