CSES - Aalto Competitive Programming 2024 - wk6 - Mon - Terrible security
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Syrjälä's prison has n inmates numbered 1,2,\dots,n. Each of the inmates has their own cell and each of the cells has a unique key. The guards have invented a neat convenience feature: the keys to the cells are stored in an array of tiny lockers. The lockers can be opened with a master key or with one of the other cell keys in case the master key gets lost. This is obviously terrible for security. The i-th locker can be opened with the key to cell k_i. No two lockers can be opened with the same cell key. You will be given q queries numbered 1,2,\dots,q. The i-th query asks the number of inmates that can escape if they get a hold of the key to cell x_i.

Input

The first line contains two integers n and q. The second line contains n integers k_1,\,k_2,\dots\,k_n, and the third line contains q integers x_1,\,x_2,\,\dots,\,x_q

Output

Print the answers to the queries on a single line.

Constraints

  • 1 \leq n, q \leq 10^5
  • 1 \leq k_i \leq n
  • 1 \leq x_i \leq n
  • k_i \neq k_j if i \neq j

Example 1

Input:

5 5
1 3 2 4 5 
3 5 3 4 4

Output:

2 1 2 1 1

Example 2

Input:

10 6
8 6 3 10 1 5 7 2 4 9 
9 3 5 1 7 5

Output:

3 1 5 5 1 5

Example 3

Input:

1 1
1
1

Output:

1