Problem: This is an interactive problem.

Vasya and Vitya play a game. Vasya thought of two integers a and b from 1 to n and Vitya tries to guess them. Each round he tells Vasya two numbers x and y from 1 to n. If both x=a and y=b then Vitya wins. Else Vasya must say one of the three phrases: 

  1. x is less than a; 
  2. y is less than b; 
  3. x is greater than a or y is greater than b. 



Vasya can't lie, but if multiple phrases are true, he may choose any of them. For example, if Vasya thought of numbers 2 and 4, then he answers with the phrase 3 to a query (3, 4), and he can answer with the phrase 1 or phrase 3 to a query (1, 5).

Help Vitya win in no more than 600 rounds. 

Input

The first line contains a single integer n (1 ≤ n ≤ 10^{18}) — the upper limit of the numbers.

Interaction

First, you need to read the number n, after that you can make queries.

To make a query, print two integers: x and y (1 ≤ x, y ≤ n), then flush the output.

After each query, read a single integer ans (0 ≤ ans ≤ 3).

If ans > 0, then it is the number of the phrase said by Vasya.

If ans = 0, it means that you win and your program should terminate.

If you make more than 600 queries or make an incorrect query, you will get Wrong Answer.

Your solution will get Idleness Limit Exceeded, if you don't print anything or forget to flush the output.

To flush you need to do the following right after printing a query and a line end: 

  * fflush(stdout) in C++; 
  * System.out.flush() in Java; 
  * stdout.flush() in Python; 
  * flush(output) in Pascal; 
  * For other languages see documentation. 



Hacks format

For hacks, use the following format:

In the first line, print a single integer n (1 ≤ n ≤ 10^{18}) — the upper limit of the numbers.

In the second line, print two integers a and b (1 ≤ a, b ≤ n) — the numbers which Vasya thought of.

In the third line, print a single integer m (1 ≤ m ≤ 10^5) — the number of instructions for the interactor.

In each of the next m lines, print five integers: x_i, y_i, r^{12}_i, r^{13}_i, and r^{23}_i (1 ≤ x_i, y_i ≤ n), where r^{ST}_i equals to either number S or number T.

While answering the query x   y, the interactor finds a number i from 1 to n with the minimal value |x-x_i| + |y-y_i|. If multiple numbers can be chosen, the least i is preferred. Then the interactor answers to the query, but if there are two phrases S and T that can be given, then r^{ST}_i is chosen.

For example, the sample test data file contains the following: 
    
    
      
    5  
    2 4  
    2  
    2 5 1 1 2  
    4 1 2 3 3  
    

Example

Input

5
3
3
2
1
0

Output

4 3
3 4
3 3
1 5
2 4

Note

Let's analyze the sample test. The chosen numbers are 2 and 4. The interactor was given two instructions.

For the query (4, 3), it can return 2 or 3. Out of the two instructions the second one is chosen, so the interactor returns a^{23}_2=3.

For the query (3, 4), it can return only 3.

For the query (3, 3), it can return 2 or 3. Out of the two instructions the first one is chosen (since in case of equal values, the least number is preferred), so the interactor returns a^{23}_1=2.

For the query (1, 5), it can return 1 or 3. Out of the two instructions the first one is chosen, so the interactor returns a^{13}_1=1.

In the fifth query (2, 4), the numbers are guessed correctly, the player wins.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
using namespace std;
struct BigInt {
  BigInt(int64_t initValue = 0) { *this = initValue; }
  BigInt(const std::vector<int>& s, int sign) {
    this->s = s;
    this->sign = sign;
  }
  const BigInt& operator=(int64_t value) {
    sign = value < 0 ? -1 : 1;
    uint64_t absValue;
    absValue = value < 0 ? -value : value;
    s.clear();
    if (absValue == 0) {
      s.push_back(0);
    } else {
      while (absValue != 0) {
        s.push_back(absValue % base);
        absValue /= base;
      }
    }
    return *this;
  }
  const BigInt& operator=(const BigInt& other) {
    sign = other.sign;
    s = other.s;
    return *this;
  }
  BigInt operator+(const BigInt& other) const {
    if (sign == other.sign) {
      BigInt res = other;
      for (int i = 0, carry = 0; i < s.size() || carry; ++i) {
        if (i == res.s.size()) {
          res.s.push_back(0);
        }
        res.s[i] += carry + (i < s.size() ? s[i] : 0);
        carry = res.s[i] >= base ? 1 : 0;
        if (carry) {
          res.s[i] -= base;
        }
      }
      return res;
    }
    return *this - (-other);
  }
  BigInt operator-() const {
    BigInt res = *this;
    res.sign = -sign;
    return res;
  }
  BigInt operator-(const BigInt& other) const {
    if (sign == other.sign) {
      if (this->abs() >= other.abs()) {
        BigInt res = *this;
        for (int i = 0, carry = 0; i < other.s.size() || carry; ++i) {
          res.s[i] -= carry + (i < other.s.size() ? other.s[i] : 0);
          carry = res.s[i] < 0 ? 1 : 0;
          if (carry) {
            res.s[i] += base;
          }
        }
        res.trim();
        return res;
      }
      return -(other - *this);
    }
    return *this + (-other);
  }
  BigInt operator*(const BigInt& other) const {
    BigInt res;
    res.sign = sign * other.sign;
    vector<BigInt> add;
    for (int i = 0; i < other.s.size(); ++i) {
      add.push_back(*this * other.s[i]);
    }
    int maxLevel = s.size() * other.s.size();
    int64_t carry = 0;
    for (int i = 0; i < maxLevel || carry; ++i) {
      for (int j = 0; j <= i && j < add.size(); ++j) {
        int pos = i - j;
        if (add[j].s.size() > pos) {
          carry += add[j].s[pos];
        }
      }
      if (res.s.size() <= i) {
        res.s.resize(i + 1);
      }
      res.s[i] = carry % base;
      carry /= base;
    }
    res.trim();
    return res;
  }
  BigInt operator*(int other) const {
    BigInt res = *this;
    int64_t value = other;
    if (value < 0) {
      res.sign = -sign;
      value = -value;
    }
    int64_t carry = 0;
    for (int i = 0; i < res.s.size() || carry; ++i) {
      if (i < res.s.size()) {
        carry += (int64_t)res.s[i] * value;
      } else {
        res.s.push_back(0);
      }
      res.s[i] = carry % base;
      carry /= base;
    }
    res.trim();
    return res;
  }
  void operator+=(const BigInt& other) { *this = *this + other; }
  void operator-=(const BigInt& other) { *this = *this - other; }
  void operator*=(const BigInt& other) { *this = *this * other; }
  BigInt abs() const {
    BigInt res = *this;
    res.sign = 1;
    return res;
  }
  void trim() {
    int i = s.size() - 1;
    while (i > 0 && s[i] == 0) {
      --i;
    }
    s.resize(i + 1);
    if (s.size() == 1 && s[0] == 0) {
      sign = 1;
    }
  }
  int compare(const BigInt& other) const {
    if (sign != other.sign) {
      return sign == 1 ? 1 : -1;
    }
    if (s.size() != other.s.size()) {
      return s.size() > other.s.size() ? sign : -sign;
    }
    for (int i = s.size() - 1; i >= 0; --i) {
      if (s[i] != other.s[i]) {
        return s[i] > other.s[i] ? sign : -sign;
      }
    }
    return 0;
  }
  bool operator<(const BigInt& other) const { return compare(other) == -1; }
  bool operator==(const BigInt& other) const { return compare(other) == 0; }
  bool operator>(const BigInt& other) const { return compare(other) == 1; }
  bool operator<=(const BigInt& other) const { return compare(other) <= 0; }
  bool operator>=(const BigInt& other) const { return compare(other) >= 0; }
  std::string toString() const {
    std::string res;
    if (sign == -1) {
      res.push_back('-');
    }
    char buf[40];
    sprintf(buf, "%d", s.back());
    res += buf;
    for (int i = s.size() - 2; i >= 0; --i) {
      sprintf(buf, "%09d", s[i]);
      res += buf;
    }
    return res;
  }
  static constexpr int base = 1000000000;
  int sign;
  vector<int> s;
};
static inline ostream& operator<<(ostream& os, const BigInt& b) {
  return os << b.toString();
}
typedef int (*AnswerFnType)(int64_t, int64_t);
int64_t n;
int checkAnswer(int64_t x, int64_t y) {
  static int count = 0;
  int64_t a = 76717313154795141ULL;
  int64_t b = 106780775536689089ULL;
  int res;
  if (x > a || y > b) {
    res = 3;
  } else if (x < a) {
    res = 1;
  } else if (y < b) {
    res = 2;
  } else {
    res = 0;
  }
  printf("%d try x = %" PRId64 ", y = %" PRId64 ", answer %d\n", ++count, x, y,
         res);
  return res;
}
int checkAnswerStdout(int64_t x, int64_t y) {
  printf("%" PRId64 " %" PRId64 "\n", x, y);
  fflush(stdout);
  int res;
  scanf("%d", &res);
  return res;
}
namespace Solution1 {
int64_t hardMinA = 1;
int64_t hardMinB = 1;
bool guessRange(int64_t lowA, int64_t hiA, int64_t lowB, int64_t hiB,
                AnswerFnType answerFn) {
  lowA = max(hardMinA, lowA);
  lowB = max(hardMinB, lowB);
  if (lowA > hiA || lowB > hiB) {
    return false;
  }
  int64_t midA = lowA + (hiA - lowA) / 2;
  int64_t midB = lowB + (hiB - lowB) / 2;
  int res = answerFn(midA, midB);
  if (res == 0) return true;
  if (res == 1) {
    hardMinA = midA + 1;
    return guessRange(midA + 1, hiA, lowB, hiB, answerFn);
  }
  if (res == 2) {
    hardMinB = midB + 1;
    return guessRange(lowA, hiA, midB + 1, hiB, answerFn);
  }
  return guessRange(lowA, midA - 1, lowB, hiB, answerFn) ||
         guessRange(midA, hiA, lowB, midB - 1, answerFn);
}
void guessRange(AnswerFnType answerFn) { guessRange(1, n, 1, n, answerFn); }
}  // namespace Solution1
namespace Solution2 {
struct Space {
  int64_t lowX, midX, hiX;
  int64_t lowY, midY, hiY;
  Space(int64_t x1, int64_t x2, int64_t y1, int64_t y2) {
    lowX = x1;
    midX = x2;
    hiX = x2;
    lowY = y1;
    midY = y2;
    hiY = y2;
  }
  BigInt areaA() { return BigInt(midX - lowX + 1) * BigInt(midY - lowY + 1); }
  BigInt areaB() { return BigInt(midX - lowX + 1) * BigInt(hiY - midY); }
  BigInt areaC() { return BigInt(hiX - midX) * BigInt(midY - lowY + 1); }
  void setLowX(int64_t newLowX) {
    lowX = newLowX;
    if (lowX > midX) {
      *this = Space(lowX, hiX, lowY, midY);
    }
  }
  void setLowY(int64_t newLowY) {
    lowY = newLowY;
    if (lowY > midY) {
      *this = Space(lowX, midX, lowY, hiY);
    }
  }
  void setMidX(int64_t newMidX) {
    midX = newMidX;
    if (midX < lowX) {
      *this = Space(lowX, hiX, lowY, midY);
    }
  }
  void setMidY(int64_t newMidY) {
    midY = newMidY;
    if (midY < lowY) {
      *this = Space(lowX, midX, lowY, hiY);
    }
  }
};
int64_t getMiddle(int64_t a, int64_t b) { return a + (b - a) / 2; }
void guessRange(AnswerFnType answerFn) {
  Space space(1, n, 1, n);
  while (true) {
    BigInt a = space.areaA();
    BigInt b = space.areaB();
    BigInt c = space.areaC();
    int64_t x, y;
    if (b >= a + c) {
      x = getMiddle(space.lowX, space.midX);
      y = space.midY;
    } else if (c > a + b) {
      x = space.midX;
      y = getMiddle(space.lowY, space.midY);
    } else {
      x = getMiddle(space.lowX, space.midX);
      y = getMiddle(space.lowY, space.midY);
    }
    int res = answerFn(x, y);
    if (res == 0) break;
    if (res == 1) {
      space.setLowX(x + 1);
    } else if (res == 2) {
      space.setLowY(y + 1);
    } else if (res == 3) {
      space.setMidX(x - 1);
      space.setMidY(y - 1);
    }
  }
}
}  // namespace Solution2
using namespace Solution2;
int main() {
  if (scanf("%" PRId64, &n) == 1) {
    guessRange(checkAnswerStdout);
  }
}