Xiao Q is a designer who has meticulously designed a park. After two years of hard work, the park is finally complete. She is very happy and has invited her friend, Xiao P, to tour the park. They enthusiastically made many tour plans. However, they realized that these plans were too ambitious and they might not have the energy to complete them all. They want to use a program to evaluate the energy required for these plans, but their programming skills are limited, so they would like you to help them solve this problem.

The park has $n$ attractions and $m$ undirected roads connecting two attractions. The $i$-th road connects the $x_i$-th and $y_i$-th attractions and has a length of $l_i$. The park's layout was carefully designed by Xiao Q. Xiao Q guarantees that in the park she designed, one can reach all attractions starting from any attraction; she guarantees that each road connects two different attractions; she guarantees that no two different roads connect the same pair of attractions; and for any four distinct attractions $A, B, C, D$, it is impossible to find six paths such that any two paths share no common points except for their endpoints, and these six paths connect every pair of the four attractions: $AB, AC, AD, BC, BD, CD$.

Below are some examples of park layouts that are definitely not designed by Xiao Q:

Xiao P and her friend have made $q$ different plans. For the $i$-th plan, they have chosen $k_i$ different attractions $a_{i,1}, a_{i,2}, \dots, a_{i,k_i}$ to visit.

Let $dis(x, y)$ be the shortest path length between attraction $x$ and attraction $y$. For the $i$-th plan, you need to answer:

For every pair of distinct indices $(i_1, i_2)$ ($i_1 < i_2$), calculate the sum of the shortest path lengths between attraction $a_{i,i_1}$ and $a_{i,i_2} \pmod{2013265921}$, i.e., calculate: $$\sum_{i_1=1}^{k_i-1} \sum_{i_2=i_1+1}^{k_i} dis\left(a_{i,i_1},a_{i,i_2}\right)\bmod 2013265921$$

Input

The first line contains two positive integers $n, m$.

The next $m$ lines each contain three positive integers, where the $i$-th line represents $x_i, y_i, l_i$, the two attractions connected by the $i$-th road and its length.

The $(m+2)$-th line contains a non-negative integer $q$.

The next $q$ lines each describe a query. Each query consists of: A positive integer $k_i$, representing the number of chosen attractions. The next line contains $k_i$ integers $a_{i,1}, a_{i,2}, \dots, a_{i,k_i}$, representing the chosen attractions.

Output

For each query, output a single non-negative integer on a new line representing the answer to that query.

Examples

Input 1

2 1
1 2 5
1
2
1 2

Output 1

5

Constraints

It is guaranteed that $2\le n \le 10^5$, $1 \le q \le 10^5$, $\sum k_i \le 10^5$.

It is guaranteed that $x_i, y_i, a_{i,j} \le n$, $l_i \le 10^9$.

Normally, parks have entrances and exits. However, in this problem, you can consider the entrances and exits of the park to be attractions as well.

A cycle is defined as a set of roads forming a path where the start and end points are the same, and no attractions are repeated in between (i.e., excluding the start/end point).

Subtask 1 (5 points): $n \le 1000$, $\sum k_i \le 3000$;

Subtask 2 (5 points): $q=1$, $m=n-1$;

Subtask 3 (20 points): $m=n-1$;

Subtask 4 (10 points): $k_i=2$, and it is guaranteed that each road belongs to at most one cycle;

Subtask 5 (10 points): It is guaranteed that each road belongs to at most one cycle;

Subtask 6 (10 points): It is guaranteed that after removing the $m$-th road, each road belongs to at most one cycle;

Subtask 7 (25 points): $k_i = 2$;

Subtask 8 (15 points): No special constraints.