P7769 "CGOI-1" Master Chooses Apprentices

Recently, many people have come to the "Ugly Country" to learn bc. The bc masters ac and mc want to choose some students from all students to teach bc skills. ###### 2021.8.29: Added a set of hack.

There are $n$ students standing in a line, and each student has an ugliness value $a_i$. Now ac and mc will **each** choose a **continuous** segment of students to teach bc. Because ac and mc have a very good relationship, the two chosen segments must have the same number of students, and the sum of the ugliness values of students in **corresponding positions** must all be $s$. (For example, if ac chooses students $1$, $2$, $3$, and mc chooses students $3$, $4$, $5$, then it must satisfy $a_1+a_3=a_2+a_4=a_3+a_5=s$.) However, ac does not know which students mc chooses or what $s$ is, so he will give several queries. For each query, you need to answer whether, for the given $s$ and the segment chosen by mc, ac can choose another segment that satisfies the requirements above. **Simplified statement:** Given $n$ and $n$ integers $a_1,\,a_2,\,\dots,\,a_n$. There are $q$ queries. Each query gives $s,l,r$. Determine whether there exists $b$ such that for all $k \in [0, r-l]$, $a_{l+k}+a_{b+k}=s$.

The first line contains two integers $n,\,q$, representing the number of students and the number of queries. The second line contains $n$ integers. The $i$-th number $a_i$ represents the ugliness value of the $i$-th student. The next $q$ lines each contain three integers $s,\,l,\,r$, representing the required sum, the index of the first student chosen by mc, and the index of the last student chosen by mc.

For each query, if it is possible to choose students that satisfy the conditions, output `Yes`; otherwise output `No`. Print one answer per line.

#### Sample Explanation: For Sample 1: In the first query, mc chooses the third student, and ac can choose the first student. In the second query, the ugliness value of the second student chosen by mc is $1$, and the total sum is also $1$, but there is no student with ugliness value $0$, so the condition cannot be satisfied. In the third query, mc chooses students from the fourth to the sixth. Then ac chooses students from the second to the fourth, and the sums of corresponding positions are $a_2+a_4=a_3+a_5=a_4+a_6=5$, which satisfies the condition. In the fourth query, mc chooses the first and second students, and ac also chooses the first and second students, so the condition is satisfied. --- #### Constraints: **This problem uses bundled testdata.** For all testdata, $1\le n,\,q\le 4\times10^5$, $1\le a_i \le n$, $1\le s\le 2n$, $1\le l\le r\le n$. * Subtask 0 (10 points): $n,\,q\le 500$. * Subtask 1 (20 points): $n,\,q\le 8\times10^3$. * Subtask 2 (20 points): All $s$ are guaranteed to be the same. * Subtask 3 (50 points): No special constraints. Translated by ChatGPT 5