Letter Delivery 2

Students at Hello High School often exchange letters with friends in other classes. Hello High School has N classes numbered 1 to N, and the classrooms sit along a straight corridor in order of class number.

Donggyu likes walking the corridor during breaks, so he agreed to deliver students' letters on his walks. A walk works as follows. First, Donggyu picks L+1 class numbers c_0, c_1, ..., c_{L-1}, c_L. Here c_0 = c_L is Donggyu's own class, and he must start and end there. The walk has L moves in total. In the i-th move, he walks straight from his current position toward class c_i. Because the classrooms lie along a straight corridor, while moving from class c_{i-1} to class c_i he passes every class between the two.

Students exchange letters in pairs, and the two students must be in different classes. Student A in class a and student B in class b exchange letters as follows.

• First, A writes a letter for B. The first time Donggyu passes class a during his walk, he receives A's letter.
• After he receives A's letter, the first time he passes class b, he delivers it to B. B writes a reply as soon as the letter arrives and hands it to Donggyu.
• After he receives B's reply, the first time he passes class a, he delivers it to A. A writes a reply as soon as the letter arrives and hands it to Donggyu.
• Until Donggyu finishes his walk, the two students keep sending replies back and forth.

A total of M pairs of students want to exchange letters. Donggyu can carry any number of letters at the same time. At the start and end of the walk, he can also receive or deliver letters in his own class. Any letter he still holds when the walk ends counts as undelivered. For each i = 1, ..., L, find the number of letters delivered so far when Donggyu finishes the i-th move.

The first line contains the integers N, L, and M, separated by spaces.

The second line contains L integers c_0, ..., c_{L-1}, separated by spaces, which describe Donggyu's walk. c_L equals c_0, so it is not given.

From the third line onward, the next M lines each give a pair a, b, separated by a space. This means the student in class a and the student in class b want to exchange letters, and the student in class a sends first.

Print L lines. On the i-th line, print the number of letters Donggyu has delivered so far when he finishes the i-th move.

• $2 \le N \le 200\,000$
• $1 \le L, M \le 200\,000$
• $1 \le c_i \le N$
• For every student pair, $1 \le a, b \le N$ and $a \ne b$.