The Best Gift Is an Array!

Interview

Time limit2sMemory limit1024 MB

Summary

Find a contiguous subarray of a with the same length as p whose elements match p as a multiset, and print its start position or NO.

Level: Medium4 of 10
Topics: Sliding window, Hash map, Array
Solved: No attempts yet

Statement

Dim Dimych's birthday is tomorrow, and Simka wants to give him an array of natural numbers. She hid the array inside his computer's system unit so he would not find it early. Nolik ran in and shuffled all the numbers, so the array is no longer a suitable gift. Nolik remembers the original array and will restore it if Simka solves a problem for him.

He gives her a multiset of numbers $p$ and asks her to find a contiguous subsegment $q$ of the same length in the gift array such that $p$ and $q$ are almost equal. Two multisets are almost equal if their elements can be rearranged so that the two match exactly. For example, $\{1, 3, 2, 1\}$ and $\{2, 3, 1, 1\}$ are almost equal, but $\{1, 2, 3\}$ and $\{2, 3, 4\}$ are not.

Input

The first line contains a single integer $n$ ( $1 \le n \le 100\,000$ ), the number of elements in $p$ .

The second line contains $n$ integers $p_i$ ( $1 \le p_i \le 100\,000$ ), the elements of $p$ .

The third line contains an integer $m$ ( $n \le m \le 100\,000$ ), the length of the gift array.

The fourth line contains $m$ integers $a_i$ ( $1 \le a_i \le 100\,000$ ), the elements of the array.

Output

If the gift array contains a subsegment $q$ that satisfies the conditions, print YES on the first line. Otherwise, print NO. If the answer is YES, print the starting position of the subsegment on the second line. If there are several answers, you may print any of them.

Examples2

Example 1
Input
```
3
2 3 4
4
1 4 2 3
```
Expected output
```
YES
2
```
Example 2
Input
```
3
1 2 3
4
2 3 4 5
```
Expected output
```
NO
```