#include "kollib.h"
#include "message.h"
#include <iostream>
#include <cassert>
#include <vector>
#define MP make_pair
#define PB push_back
using namespace std;
typedef long long ll;
const int kMaxQ = 404;
int que[kMaxQ];
int pos[kMaxQ];
const int kRange = 1813632;
vector<pair<int, int> > hash_que[kRange];
const int kMaxInst = 1e2 + 4;
int st[kMaxInst];
struct HashPlace {
  int pos;
  int ind;
  HashPlace (int start_, int ind_) : pos(start_), ind(ind_) {}
  HashPlace () : pos(0), ind(0) {}
};
HashPlace hash_starts[kRange];
bool Check(int act_v) {
  return hash_starts[act_v % kRange].pos == act_v;
}
vector<HashPlace> hash_queries[kRange];
int died[kMaxInst];
struct Edge {
  int nei;
  int len;
  vector<pair<int, int> > found_q;
  Edge(int n_, int l_, vector<pair<int, int> >& f_) : nei(n_), len(l_), found_q(f_) {}
};
vector<Edge> edges[kMaxInst];
int vis[kMaxInst];
void Dfs(int v, int dis_from_start, int dep) {
  vis[v] = 1;
  for (auto& e : edges[v]) {
    if (!vis[e.nei] || (e.nei == 0 && dep > 1)) {
      for (auto p : e.found_q) {
        pos[p.first] = dis_from_start + p.second;
      }
      Dfs(e.nei, dis_from_start + e.len, dep + 1);
    }
  }
}
int main() {
  //cerr<<"j"<<endl;
  int n = NumberOfStudents();
  int inst_num = min(n, NumberOfNodes());
  int inst = MyNodeId();
  if (inst >= inst_num) {
    return 0;
  }
  ll s, a, b, k;
  s = 127654389 % n;
  a = 364995323;
  b = 837322103;
//   if (inst == 0) {
//     cout<<n<<endl;
//   }
  for (int i = 0; i < inst_num; i++) {
    s = ((a * s) + b) % n;
    st[i] = s + 1;
    while (hash_starts[st[i] % kRange].pos) {
      st[i] = st[i] % n + 1;
    }
//     if (inst == 0) {
//       cout<<st[i]<<" ";
//     }
    hash_starts[st[i] % kRange] = HashPlace(st[i], i);
  }
//   if (inst == 0) {
//     cout<<endl;
//   }
  //cerr<<inst<<" starts from "<<st[inst]<<endl;
  int q_num = NumberOfQueries();
  for (int i = 1; i <= q_num; i++) {
    que[2 * i - 1] = QueryFrom(i);
    que[2 * i] = QueryTo(i);
    //cerr<<que[2 * i - 1]<<" "<<que[2 * i]<<endl;
  }
  for (int i = 1; i <= 2 * q_num; i++) {
    hash_queries[que[i] % kRange].PB(HashPlace(que[i], i));
  }
  int act_v = st[inst];
  int fir = FirstNeighbor(act_v);
  int sec = SecondNeighbor(act_v);
  int beg[] = {fir, sec};
  for (int phase = 0; phase <= 1; phase++) {
    vector<pair<int, int> > found_q;
    int prev_v = st[inst];
    act_v = st[inst];
    for (auto p : hash_queries[act_v % kRange]) {
      if (p.pos != act_v) {
        continue;
      }
      //cerr<<"Proces nr "<<inst<<" znalazl "<<p.ind<<"-te q tzn. "<<p.pos<<endl;
      found_q.push_back(MP(p.ind, 0));
    }
    act_v = beg[phase];
    int act_dis = 1;
    while (!Check(act_v)) {
      
      for (auto p : hash_queries[act_v % kRange]) {
        if (p.pos != act_v) {
          continue;
        }
        //cerr<<"Proces nr "<<inst<<" znalazl "<<p.ind<<"-te q tzn. "<<p.pos<<endl;
        found_q.push_back(MP(p.ind, act_dis));
      }
      int new_v = FirstNeighbor(act_v) + SecondNeighbor(act_v) - prev_v;
      prev_v = act_v;
      act_v = new_v;
      act_dis++;
    }
    int end_in = hash_starts[act_v % kRange].ind;
    assert(st[end_in] == act_v);
    PutInt(0, inst);
    PutInt(0, end_in);
    PutInt(0, act_dis);
    PutInt(0, found_q.size());
    for (auto p : found_q) {
      //cerr<<"Hejka"<<inst<<endl;
      PutInt(0, p.first);
      PutInt(0, p.second);
    }
    Send(0);
  }
  
  if (inst != 0) {
    return 0;
  }
  int max_len = 0;
  for (int i = 0; i < inst_num; i++) {
    if (died[i]) {
      continue;
    }
    for (int zz = 1; zz <= 2; zz++) {
      Receive(i);
      int a = GetInt(i);
      int b = GetInt(i);
      int len = GetInt(i);
      max_len = max(max_len, len);
      //cout<<len<<endl;
      int found_q_num = GetInt(i);
      //cerr<<"czytam message (od "<<i<<") "<<a<<" "<<b<<" "<<len<<" "<<found_q_num<<endl;
      vector<pair<int, int> > found_q;
      for (int j = 0; j < found_q_num; j++) {
        int fir = GetInt(i);
        int sec = GetInt(i);
        //cerr<<"znalezione "<<fir<<" "<<sec<<endl;
        found_q.PB(MP(fir, sec));
      }
      edges[a].PB(Edge(b, len, found_q));
    }
  }
  Dfs(0, 0, 0);
  cerr<<1.0 * max_len / n<<endl;
  /* for (int i = 1; i <= 2 * q_num; i++) {
    cout<<pos[i]<<" ";
  }
  cout<<endl; */
  for (int i = 1; i <= q_num; i++) {
    
    int diff = abs(pos[2 * i - 1] - pos[2 * i]);
    //cout<<min(diff, n - diff)<<endl;
  }

  return 0;
}