問題文

0以上 9以下の整数からなる長さ $N$ の数列 $P = (p_1, p_2, ... ,p_N)$ が与えられます。

以下のクエリを $Q$ 個処理してください。

• $i$ 番目のクエリでは0以上 9以下の整数からなる長さ 10 の数列 $T = (t_0, ..., t_9)$ が与えられます。$1 \leq i \leq N$ に対して$p_i = t_{p_i}$ と入れ替えた時の転倒数を求めよ。

クエリごとに $P$ は独立であることに注意してください。

転倒数とは $1\leq i < j \leq N$ な $i, j$ に対して、$A_i > A_j$ である個数を言います。

制約

• $1 \leq N \leq 3 \times 10^3$　
• $1 \leq Q \leq 10^5$
• $0 \leq p_i \leq 9$ $(1 \leq i \leq N)$
• $0 \leq q_i \leq 9$ $(1 \leq i \leq Q)$
• 入力は全て整数

入力

各クエリに対して以下か入力として与えられる。

出力

整数で出力してください。

サンプル

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

3
0
10

1つ目のクエリでは数列が $(1, 1, 1, 0, 1)$に変化します。転倒数は3です。

2つ目のクエリでは数列が $(2, 2, 2, 2, 2)$に変化します。転倒数は 0です。

3つ目のクエリでは数列が $(9, 8, 7, 6, 0)$に変化します。転倒数は 10です。