Under construction

Still being built. Things may change

Suspicious Reports (Basic)

Interview

Time limit1sMemory limit1024 MB

Summary
Given a full report s and a pattern t, decide whether t is the upper slice of s at some level h, and output the matching column indices.
Level

Easy3 of 10

Topics
Brute force, Implementation, Array
Solved
No attempts yet

Statement

Eddie Brock is a journalist after all. Before he met Venom, he was writing a scathing article exposing every vice of the Life Foundation (yes, we are going back to the first movie again, but what can you do). Now he is looking at recently found financial reports of the Foundation and tracing traces of its illegal activity (for example, experiments on people).

Each report is an array of numbers sis_i of size mm, drawn as a histogram: a set of columns with the corresponding heights. The accountant marks which columns correspond to illegal operations as follows.

  1. First, he picks a segment of the histogram from ll to rr that contains records of the nn most illegal operations, located in columns l⩽i1<i2<…<in⩽rl \leqslant i_1 < i_2 < \ldots < i_n \leqslant r.
  2. Then he draws a horizontal strip at height hh (possibly negative) between columns ll and rr inclusive, so that all columns of the illegal operations, being the most costly ones, are strictly above the strip, and the legal ones are not above it. Formally, the condition i∈i1,…,ini \in i_1, \ldots, i_n must be equivalent to si>hs_i > h.
  3. Then he saves the report of illegal operations in a secret folder as a sequence of length nn with tj=sij−ht_j = s_{i_j} - h. Informally, this is the upper part of a slice of the original histogram at level hh.

Eddie has a reliable full report and a separate report of illegal operations, sent by an anonymous source. The source claims that this report of illegal operations was obtained from the full report in the way described. Eddie only wants to know which exact columns of the full report correspond to the illegal operations.

Consider some examples. First the Foundation's full report, then the histogram of illegal operations:

In every example except the second, you can pick out a subsequence of columns whose heights sjs_j sit at the given levels relative to the same horizontal cut, while the remaining columns lie below it. In the second example this is impossible, because one extra column is above the cut. Note that l=1l = 1 and r=nr = n do not have to hold.

Input

The first line contains an integer nn, the length of the report of illegal operations (1⩽n⩽5001 \leqslant n \leqslant 500).

The second line contains nn space-separated integers tit_i, the column heights of the report of all illegal operations of the Foundation (1⩽ti⩽1061 \leqslant t_i \leqslant 10^6).

The third line contains an integer mm, the length of the Foundation's full report (n⩽m⩽500n \leqslant m \leqslant 500).

The next line contains mm space-separated integers sis_i, the entries of the full report.

Output

On the first line, print YES (without quotes) if the report of illegal operations could indeed have been obtained from the given full report in the described way, and NO otherwise.

If YES is printed, the second line must contain nn space-separated integers i1,i2,…,ini_1, i_2, \ldots, i_n, the indices of the columns in the full report that correspond to the Foundation's illegal operations (1⩽i1<i2<…<in⩽m1 \leqslant i_1 < i_2 < \ldots < i_n \leqslant m).

Examples4

  1. Example 1

    Input
    5
    2 1 1 1 2
    7
    6 5 4 5 5 3 6
    
    Expected output
    YES
    1 2 4 5 7
    
  2. Example 2

    Input
    5
    2 1 1 1 2
    7
    6 5 5 5 5 3 6
    
    Expected output
    NO
    
  3. Example 3

    Input
    5
    2 1 1 1 2
    7
    6 5 6 5 5 5 6
    
    Expected output
    YES
    3 4 5 6 7
    
  4. Example 4

    Input
    3
    5 5 5
    5
    5 3 3 3 5
    
    Expected output
    YES
    2 3 4