Air Bovinia collega $N$ fattorie delle mucche ($1 \le N \le 200$). Sceglie $K$ hub ($1 \le K \le 100,$ $K \le N$). Le fattorie sono numerate $1..N$, gli hub $1..K$.

Ci sono $M$ voli a senso unico ($1 \le M \le 10,000$). Il volo $i$ va da $u_i$ a $v_i$ e costa $d_i$ dollari ($1 \le d_i \le 1,000,000$).

Riceve $Q$ richieste di sola andata ($1 \le Q \le 10,000$), la $i$-esima da $a_i$ a $b_i$. Da $a_i$ a $b_i$ è ammessa qualsiasi sequenza di voli diretti, anche rivisitando fattorie, ma deve includere almeno un hub, che può essere partenza, arrivo o intermedio. Può quindi mancare un percorso valido da $a_i$ a $b_i$. Per le altre richieste trova il costo minimo valido.

Input

• Riga $1$: interi $N$, $M$, $K$, $Q$.

• Righe $2..1+M$: la riga $i+1$ contiene $u_i$, $v_i$, $d_i$ per il volo $i$.

• Righe $2+M..1+M+Q$: la riga $1+M+i$ descrive il viaggio $i$ con $a_i$ e $b_i$.

Output

• Riga $1$: numero di richieste, fra $Q$, con percorso valido.

• Riga $2$: somma dei costi minimi di tutte le richieste con percorso valido.

Esempi

Input 1

3 3 1 3
3 1 10
1 3 10
1 2 7
3 2
2 3
1 2

Output 1

2
24

Note

Ci sono $3$ fattorie numerate $1\ldots3$; $1$ è hub. Il volo da $3$ a $1$ costa $10$, ecc. Richieste: $3\to2$, $2\to3$, $1\to2$.

$3\to2$ ha un unico percorso di costo $10+7$. $2\to3$ non ne ha, poiché nessun volo parte da $2$. $1\to2$ ha un unico percorso valido di costo $7$.

Autore del problema: Kalki Seksaria