[Solution] Sanae and Giant Robot Codeforces Solution | Codeforces Problem Solution 2022

[Solution] Sanae and Giant Robot Codeforces Solution | Codeforces Problem Solution 2022

F. Sanae and Giant Robot

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Sanae made a giant robot — Hisoutensoku, but something is wrong with it. To make matters worse, Sanae can not figure out how to stop it, and she is forced to fix it on-the-fly.

The state of a robot can be represented by an array of integers of length n$n$. Initially, the robot is at state a$a$. She wishes to turn it into state b$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$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$a$ does not change after each copy operation in case the robot go haywire. Formally, Sanae can choose segment [l,r]$[l,r]$ and assign ai=bi$a_i=b_i$ (l≤i≤r$l\le i\le r$) if ∑i=1nai$\sum _{i=1}^n{a}_i$ does not change after the operation.

Solution Click Below:-  CLICK HERE

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

Input

Each test contains multiple test cases. The first line contains a single integer t$t$ (1≤t≤2⋅104$1\le t\le 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$n$, m$m$ (2≤n≤2⋅105$2\le n\le 2\cdot {10}^5$, 1≤m≤2⋅105$1\le m\le 2\cdot {10}^5$) — the length of a$a$, b$b$ and the number of segments.

Cirno's Perfect Bitmasks Classroom Codeforces Solution

Patchouli's Magical Talisman Codeforces Solution

Manipulating History Codeforces Solution

The Enchanted Forest Codeforces Solution

Railway System Codeforces Solution

Sanae and Giant Robot Codeforces Solution

The second line contains n$n$ intergers a1,a2,…,an$a_1,a_2,\dots ,a_n$ (1≤ai≤109$1\le a_i\le {10}^9$) — the initial state a$a$.

The third line contains n$n$ intergers b1,b2,…,bn$b_1,b_2,\dots ,b_n$ (1≤bi≤109$1\le b_i\le {10}^9$) — the desired state b$b$.

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

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

Output

For each test case, print "YES" (without quotes) if a$a$ can be turned into b$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).