Menurut prakiraan ahli seismologi, gempa bumi kuat diperkirakan akan melanda Bitland. Ada $n$ kota di Bitland, bernomor dari $1$ hingga $n$. Sebagian kota dihubungkan oleh jalan dua arah. Rute adalah suatu urutan kota yang setiap dua kota berurutannya dihubungkan oleh sebuah jalan. Panjang rute adalah jumlah panjang seluruh jalan yang dilalui rute tersebut. Rute terpendek antara sepasang kota $(a,b)$ didefinisikan sebagai rute dengan panjang minimum yang dimulai di kota $a$ dan berakhir di kota $b$.

Pemerintah negara tersebut menganggap kebocoran radiasi dari pembangkit listrik tenaga nuklir (PLTN) sebagai masalah utama: jika hal ini terjadi, penduduk harus dievakuasi. Setiap PLTN terletak di salah satu kota dan jumlah seluruhnya adalah $k$; setiap kota memiliki paling banyak satu PLTN. Pemerintah ingin menyusun rencana evakuasi yang dapat digunakan selama gempa bumi.

Rute evakuasi antarkota harus dipilih agar berada sejauh mungkin dari semua kota yang memiliki PLTN. Tingkat bahaya suatu rute dinilai dengan menghitung jarak minimum antara kota-kota pada rute itu dan kota mana pun yang memiliki PLTN. Secara formal, misalkan $(a_1,a_2,\ldots,a_s)$ adalah kota-kota pada rute dan $(g_1,g_2,\ldots,g_k)$ adalah kota-kota yang memiliki PLTN. Tingkat bahaya rute sama dengan nilai minimum dari seluruh nilai $dist(a_i,g_j)$, dengan $dist(a,b)$ sama dengan panjang rute terpendek antara $a$ dan $b$.

Diberikan $Q$ pasang kota $(s_i,t_i)$. Untuk setiap pasangan, Anda harus menyusun rencana evakuasi dengan tingkat bahaya maksimum.

Masukan

Baris pertama berisi dua bilangan bulat $n$ dan $m$ yang dipisahkan spasi ($2\le n\le10^5$, $1\le m\le5\cdot10^5$), yaitu jumlah kota dan jumlah jalan di Bitland. Kemudian, $m$ baris berisi deskripsi jalan, satu per baris. Setiap jalan diberikan oleh tiga bilangan $a_i,b_i,w_i$ ($1\le a_i,b_i\le n$, $1\le w_i\le1000$, $a_i\ne b_i$), yaitu pasangan kota yang dihubungkan dan panjang jalan. Baris berikutnya berisi satu bilangan bulat $k$ ($1\le k\le n$), yaitu jumlah kota yang memiliki PLTN. Baris setelahnya berisi $k$ bilangan bulat $g_i$ ($1\le g_i\le n$, untuk $1\le i\le k$), yaitu nomor kota tempat PLTN berada. Baris berikutnya berisi satu bilangan bulat $Q$ ($1\le Q\le10^5$), yaitu jumlah pasangan kota dalam rencana evakuasi. Kemudian setiap baris dari $Q$ baris berikutnya berisi pasangan kota ke-$i$, $(s_i,t_i)$ ($1\le s_i,t_i\le n$, $s_i\ne t_i$).

Dijamin tidak ada jalan yang menghubungkan sebuah kota dengan dirinya sendiri, setiap pasangan kota dihubungkan oleh paling banyak satu jalan, dan setiap kota dapat dicapai dari kota mana pun.

Keluaran

Cetak $Q$ baris.

Pada baris ke-$i$, cetak satu bilangan bulat: tingkat bahaya maksimum untuk pasangan kota $(s_i,t_i)$.

Subtugas

Soal ini terdiri dari lima subtugas:

1. $n\le10^3$, $1\le m\le10^3$, $Q\le10^3$. Untuk setiap pasangan $(s_i,t_i)$ dari $Q$ pasangan, terdapat jalan langsung. Bernilai 10 poin.
2. $n\le10^5$, $Q\le10^5$. Untuk setiap pasangan $(s_i,t_i)$ dari $Q$ pasangan, terdapat jalan langsung. Bernilai 13 poin.
3. $n\le15$, $1\le m\le200$, $1\le Q\le200$. Bernilai 12 poin.
4. $Q=1$. Bernilai 19 poin.
5. Batasan sesuai pernyataan soal di atas. Bernilai 46 poin.

Contoh

Masukan 1

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

Keluaran 1

5
5
0
7
8

Catatan