Problem: Requirements

* All inputs are of non-negative integer value.
* T_{\text{max}} = 10000
* 200 \leq |V| \leq 400
* 1.5 |V| \leq |E| \leq 2 |V|
* 1 \leq u_{i}, v_{i} \leq |V| (1 \leq i \leq |E|)
* 1 \leq d_{u_i, v_i} \leq \lceil 4\sqrt{2|V|} \rceil (1 \leq i \leq |E|)
* The given graph has no self-loops / multiple edges and is guaranteed to be connected.
* 0 \leq N_{\text{new}} \leq 1
* 1 \leq \mathrm{new\\_id}_{i} \leq T_{\text{last}}+1 (1 \leq i \leq N_{\text{new}}). Note: If all orders are generated by the order generation rule as explained above, the total number of orders is at most T_{\text{last}}+1. Therefore, the possible range of \mathrm{new\\_id}_{i} should be from 1 to T_{\text{last}}+1.
* 2 \leq \mathrm{dst}_i \leq |V| (1 \leq i \leq N_{\text{new}})
* The order IDs \mathrm{new\\_{id}}_i are unique.

Input Format

Input is provided in the following form:


|V| |E|
u_{1} v_{1} d_{u_{1}, v_{1}}
u_{2} v_{2} d_{u_{2}, v_{2}}
:
u_{|E|} v_{|E|} d_{u_{|E|}, v_{|E|}}
T_{\text{max}}
\mathrm{info}_{0}
\mathrm{info}_{1}
:
\mathrm{info}_{T_{\text{max}}-1}


* In the first line |V| denotes the number of vertices, while |E| denotes the number of edges.
* The following |E| lines denote the edges of the graph. In particular, in the ith line u_{i} and v_{i} denote the edge connecting u_{i} and v_{i} and d_{u_{i}, v_{i}} the corresponding distance.
* The following line denotes the number of steps T_{\text{max}}.



In the following line, \mathrm{info}_t is information about the order from the customer that occurs at time t. \mathrm{info}_t is given in the form:


N_{\text{new}}
\mathrm{new\_id}_1 \mathrm{dst}_1
\mathrm{new\_id}_2 \mathrm{dst}_2
\vdots
\mathrm{new\_id}_{N_{\text{new}}} \mathrm{dst}_{N_{\text{new}}}


* N_{\text{new}} represents the number of new orders which appear at time t.
* The next N_{\text{new}} lines give the newly generated order information. The i-th order information indicates that the order ID \mathrm{new\\_{id}}_i of the new order, while \mathrm{dst}_i denotes the vertex to which the customer wishes the order to be delivered.
* Note: If N_{\text{new}}=0, there are no new lines.

Output Format

The Output expects T_{\text{max}} integers in the format specified below.


\mathrm{command}_{0}
\mathrm{command}_{1}
:
\mathrm{command}_{T_{\text{max}}-1}


In particular, \mathrm{command}_{i} shall specify the movement of the delivery car by using one of the following two options:

1) `stay`, if the car shall not move:


-1


2) `move w`, if the car shall be moved one step towards the neighboring vertex w


w


Note that in case of 2) w has to satisfy the following conditions:

* w \in V
* If the car is at vertex u: \left\\{ u, w \right\\} \in E .
* If the car is on the edge \left\\{ u, v \right\\}, w must either satisfy u = w or v = w.



* * *

Examples

Input




Output




Input

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


Output

2
-1
1
5

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int ITERS=100000;
const bool VISIT1=true;
const bool UPD_ORDER=true;
int n,m,tmax,tmax2,o,cnt,i,j,k,swaps,x[808],y[808],z[808],d[402][402],id[10100],dst[10100],av[10100],otm[10100],p[10100],newp[10100],fi[402];
vector<int> g[402],orders[10100],here[402];  // TODO: orders[i] can be just number, not vector
long long cur,score;
int sqr(int x) { return x*x; }
void init() {
  for (i=0; i<o; i++) p[i]=i;
  // TODO: some greedy?
}
long long deliver_here(int pos, int t) {
  long long score=0;
  for (; fi[pos]<here[pos].size(); fi[pos]++) {
    int i=here[pos][fi[pos]];
    if (av[i]==1) {
      av[i]=2;
      score+=tmax2-sqr(t-otm[i]);
      newp[cnt++]=i;
      //fprintf(stderr,"order dst=%d st=%d et=%d\n",pos,otm[i],t);  // i=%d,i
    } else if (av[i]==0) break;
  }
  return score;
}
long long calc_score() {
  long long score=cnt=0;
  int pos=1,lst=-1;
  for (int i=1; i<=n; i++) fi[i]=0;
  for (int i=0; i<o; i++) av[i]=0;
  for (int cur=0, t=0; cur<o && t<tmax; ) {
    //fprintf(stderr,"#time=%d; position=%d; nxt=%d\n",t,pos,dst[p[cur]]);
    score+=deliver_here(pos,t);
    for (; cur<o && av[p[cur]]==2; cur++);
    if (cur>=o) break;
    if (pos==1) {
      for (int i=lst+1; i<=t; i++) for (int j=0; j<orders[i].size(); j++) av[orders[i][j]]=1;
      lst=t;
    }
    int ds=(av[p[cur]]==1)?dst[p[cur]]:1;
    if (VISIT1) {
      if (pos!=1 && ds!=1 && d[pos][ds]==d[pos][1]+d[1][ds]) ds=1;
    }
    if (pos!=ds) {
      for (int i=0; i<g[pos].size(); i++) {
        int e=g[pos][i];
        int nxt=x[e]+y[e]-pos;
        if (d[ds][pos]==d[ds][nxt]+z[e]) {
          ds=nxt;
          break;
        }
      }
      t+=d[pos][ds];
      pos=ds;
    } else t++;
  }
  int num=cnt;
  for (int i=0; i<o; i++) if (av[p[i]]!=2) newp[num++]=p[i];
  if (num!=o) puts("!!!!!");
  return score;
}
void print_result() {
  score=cnt=0;
  int cur=0,pos=-1,ed=0,lst=-1;
  for (int i=1; i<=n; i++) fi[i]=0;
  for (int i=0; i<o; i++) av[i]=0;
  for (int t=0; t<tmax; t++) {
    //if (t>75 && t<82) printf("time %d: pos %d %d\n",t,pos,ed);
    if (pos<0) {
      score+=deliver_here(-pos,t);
      for (; cur<o && av[p[cur]]==2; cur++);
      if (cur>=o) {
        puts("-1");
        continue;
      }
      if (pos==-1) {
        for (int i=lst+1; i<=t; i++) for (int j=0; j<orders[i].size(); j++) {
          av[orders[i][j]]=1;
          //printf("%d is available\n",orders[i][j]);
        }
        lst=t;
      }
    }
    int ds=(av[p[cur]]==1)?dst[p[cur]]:1;
    //if (t>75 && t<82) printf("pcur=%d ds=%d\n",p[cur],ds);
    if (pos<0) {
      if (pos==-ds) {
        puts("-1");
        continue;
      }
      if (VISIT1) {
        if (pos!=-1 && ds!=1 && d[-pos][ds]==d[-pos][1]+d[1][ds]) ds=1;
      }
      for (int i=0; i<g[-pos].size(); i++) {
        int e=g[-pos][i];
        int nxt=x[e]+y[e]+pos;
        //printf(" nxt=%d; %d =?= %d + %d\n",nxt,d[ds][-pos],d[ds][nxt],z[e]);
        if (d[ds][-pos]==d[ds][nxt]+z[e]) {
          printf("%d\n",nxt);
          if (z[e]>1) {
            ed=(x[e]==-pos)?1:(z[e]-1);
            pos=e;
          } else pos=-nxt;
          break;
        }
      }
    } else {
      if (d[ds][x[pos]]+ed<d[ds][y[pos]]+z[pos]-ed) {
        printf("%d\n",x[pos]);
        if (ed==1) pos=-x[pos]; else ed--;
      } else {
        printf("%d\n",y[pos]);
        if (ed+1==z[pos]) pos=-y[pos]; else ed++;
      }
    }
  }
}
int main() {
  srand(371);
  scanf("%d%d",&n,&m);
  memset(d,10,sizeof(d));
  for (i=1; i<=n; i++) d[i][i]=0;
  for (i=1; i<=m; i++) {
    scanf("%d%d%d",&x[i],&y[i],&z[i]);
    d[x[i]][y[i]]=d[y[i]][x[i]]=z[i];
    g[x[i]].push_back(i);
    g[y[i]].push_back(i);
  }
  for (k=1; k<=n; k++) for (i=1; i<=n; i++) for (j=1; j<=n; j++)
    d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
  //for (i=1; i<=n; i++, puts("")) for (j=1; j<=n; j++) printf("%d ",d[i][j]);
  scanf("%d",&tmax);
  tmax2=sqr(tmax);
  for (i=0; i<tmax; i++) {
    scanf("%d",&cnt);
    for (j=0; j<cnt; j++, o++) {
      scanf("%d%d",&id[o],&dst[o]);
      here[dst[o]].push_back(o);
      orders[i].push_back(o);
      otm[o]=i;
    }
  }
  init();
  score=calc_score();
  for (int it=0; it<ITERS; it++) {
    i=rand()%o;
    j=rand()%(o-1);  // TODO: is this rand fast and good enough?
    if (j>=i) j++;
    swap(p[i],p[j]);
    cur=calc_score();
    if (cur<score) swap(p[i],p[j]); else {
      if (UPD_ORDER) for (i=0; i<o; i++) p[i]=newp[i];
      swaps++;
      score=cur;
    }
  }
  fprintf(stderr,"%d swaps made; score=%I64d; cnt=%d\n",swaps,score,cnt);
  // TODO: initial greedy + type of rand_iterations + SA/HC + V/NV
  print_result();  // TODO: print best
  fprintf(stderr,"%d swaps made; score=%I64d; cnt=%d\n",swaps,score,cnt);
  return 0;
}