f1

Se dă un tablou bidimensional cu $N$ linii și $N$ coloane. Exista $Q$ poziții distincte, etichetate cu numere naturale distincte de la 1 la $Q$, unde în tablou există valoarea 1, la toate celelalte poziții din tablou există valoarea 0. Pentru o poziție oarecare, dintre cele $Q$ date, numim "forța" acelei poziții numărul subtablourilor din tabloul dat care conțin doar o singură valoare 1, cea aflată la acea poziție, restul elementelor din subtablouri fiind egale cu 0.

Cerință

Pentru un șir format din $P$ etichete distincte, dintre cele coresponzătoare celor $Q$ poziții date, se cere să se calculeze suma "forțelor" acestora.

Date de intrare

Pe prima linie a fișierului de intrare f1.in se găsesc numerele naturale $N$, $Q$ și $P$, separate prin spațiu. Pe următoarele $Q$ linii se află câte două numere naturale, separate prin spațiu, reprezentând linia și coloana pentru fiecare dintre cele $Q$ poziții unde se află valoarea 1, în ordinea etichetelor lor. Pe următoarele $P$ linii se află câte un număr natural, reprezentând cele $P$ etichete ale pozițiilor pentru care trebuie calculată suma "forțelor".

Date de ieșire

Fișireul de ieșire f1.out va conține pe prima linie un număr natural reprezentând suma "forțelor" cerută.

Restricții

• $1 \le P \le Q \le 1000$.
• $1 \le N \le 5000$
• Liniile și coloanele tabloului sunt numerotate cu $1, 2, 3, \cdots, N$.

Subtask 1 (2 puncte)

• $Q = 1$

Subtask 2 (18 puncte)

• $Q \le 5$

Subtask 3 (7 puncte)

• Cele $Q \le 200$ poziții unde există valoarea 1 sunt ordonate strict crescător dupa linii și după coloane

Subtask 4 (7 puncte)

• Cele $Q \le 200$ poziții unde există valoarea 1 sunt situate pe aceeși linie

Subtask 5 (7 puncte)

• $N \le 10$, $Q \le 200$

Subtask 6 (12 puncte)

• $N \le 300$, $Q \le 200$

Subtask 7 (23 puncte)

• $N \le 500$, $Q \le 200$

Subtask 8 (8 puncte)

• $Q \le 200$

Subtask 9 (16 puncte)

• Nu există alte restricții suplimentare

Exemplul 1

f1.in

4 1 1
2 2
1

f1.out

36

Exemplul 2

f1.in

4 3 2
2 2
3 4
4 1
3
1

f1.out

33

Explicații ale exemplelor

În primul exemplu avem un tablou de dimensiune 4x4 și valoarea 1 la pozița (2,2). Subtablourile care conțin pozița (2,2) au colțul stânga-sus în zona delimitată de liniile 1 și 2, respectiv coloanele 1 și 2, iar colțul dreapta-jos în zona delimitată de liniile 2 și 4, respectiv coloanele 2 și 4. În total 36 subtablouri

În al doilea exemplu avem un tablou de dimensiune 4x4 și valoarea 1 la pozițile (2,2), (3,4) și (4,1). Trebuie calculate forțele poziților cu etichetele 3 și 1, deci ale poziților (4,1) și (2,2). Subtablourile care conțn doar pozița (4,1) sunt: cele cu colțul stânga sus în pozițile (1,1) sau (2,1) și colțul dreapta jos în pozița (4,1); cele cu colțul stânga sus în (3,1) sau (4,1) și colțul dreapta jos în (4,1), (4,2) sau (4,3); cea cu colțul stânga sus în (4,1) și colțul dreapta jos în (4,4). Astfel forța poziței (4,1) este 2+6+1=9. Subtablourile care conțin doar poziția (2,2) sunt: cele cu colțul stânga sus în pozițiile (1,1), (1,2), (2,1) sau (2,2) și colțul dreapta jos în pozițiile (2,2), (2,3), (2,4), (3,2) sau (3,3); cele cu colțul stânga sus în (1,2) sau (2,2) și colțul dreapta jos în (4,2) sau (4,3). Forța poziției (2,2) este egală cu 20+4=24. Suma celor două forțe este 33.