Problem: Hag is a very talented person. He has always had an artist inside him but his father forced him to study mechanical engineering.

Yesterday he spent all of his time cutting a giant piece of wood trying to make it look like a goose. Anyway, his dad found out that he was doing arts rather than studying mechanics and other boring subjects. He confronted Hag with the fact that he is a spoiled son that does not care about his future, and if he continues to do arts he will cut his 25 Lira monthly allowance.

Hag is trying to prove to his dad that the wooden piece is a project for mechanics subject. He also told his dad that the wooden piece is a strictly convex polygon with n vertices.

Hag brought two pins and pinned the polygon with them in the 1-st and 2-nd vertices to the wall. His dad has q queries to Hag of two types. 

  * 1 f t: pull a pin from the vertex f, wait for the wooden polygon to rotate under the gravity force (if it will rotate) and stabilize. And then put the pin in vertex t. 
  * 2 v: answer what are the coordinates of the vertex v. 



Please help Hag to answer his father's queries.

You can assume that the wood that forms the polygon has uniform density and the polygon has a positive thickness, same in all points. After every query of the 1-st type Hag's dad tries to move the polygon a bit and watches it stabilize again.

Input

The first line contains two integers n and q (3≤ n ≤ 10 000, 1 ≤ q ≤ 200000) — the number of vertices in the polygon and the number of queries.

The next n lines describe the wooden polygon, the i-th line contains two integers x_i and y_i (|x_i|, |y_i|≤ 10^8) — the coordinates of the i-th vertex of the polygon. It is guaranteed that polygon is strictly convex and the vertices are given in the counter-clockwise order and all vertices are distinct.

The next q lines describe the queries, one per line. Each query starts with its type 1 or 2. Each query of the first type continues with two integers f and t (1 ≤ f, t ≤ n) — the vertex the pin is taken from, and the vertex the pin is put to and the polygon finishes rotating. It is guaranteed that the vertex f contains a pin. Each query of the second type continues with a single integer v (1 ≤ v ≤ n) — the vertex the coordinates of which Hag should tell his father.

It is guaranteed that there is at least one query of the second type.

Output

The output should contain the answer to each query of second type — two numbers in a separate line. Your answer is considered correct, if its absolute or relative error does not exceed 10^{-4}.

Formally, let your answer be a, and the jury's answer be b. Your answer is considered correct if \frac{|a - b|}{max{(1, |b|)}} ≤ 10^{-4}

Examples

Input

3 4
0 0
2 0
2 2
1 1 2
2 1
2 2
2 3


Output

3.4142135624 -1.4142135624
2.0000000000 0.0000000000
0.5857864376 -1.4142135624


Input

3 2
-1 1
0 0
1 1
1 1 2
2 1


Output

1.0000000000 -1.0000000000

Note

In the first test note the initial and the final state of the wooden polygon. 

<image>

Red Triangle is the initial state and the green one is the triangle after rotation around (2,0).

In the second sample note that the polygon rotates 180 degrees counter-clockwise or clockwise direction (it does not matter), because Hag's father makes sure that the polygon is stable and his son does not trick him.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
using Real = long double;
Real g_err = 1e-9;
bool r_eq(Real x, Real y, Real err = g_err) {
  return abs(x - y) <= err || abs(x - y) <= abs(x) * err;
}
bool r_le(Real x, Real y, Real err = g_err) {
  return x - y <= err || x - y <= abs(x) * err;
}
bool r_ge(Real x, Real y, Real err = g_err) { return r_le(y, x, err); }
bool r_gt(Real x, Real y, Real err = g_err) { return !r_le(x, y, err); }
bool r_lt(Real x, Real y, Real err = g_err) { return !r_le(y, x, err); }
bool r_ne(Real x, Real y, Real err = g_err) { return !r_eq(x, y, err); }
bool rp_eq(Real x, Real y, Real err = g_err) { return abs(x - y) <= err; }
bool rp_le(Real x, Real y, Real err = g_err) { return x - y <= err; }
bool rp_ge(Real x, Real y, Real err = g_err) { return rp_le(y, x, err); }
bool rp_gt(Real x, Real y, Real err = g_err) { return !rp_le(x, y, err); }
bool rp_lt(Real x, Real y, Real err = g_err) { return !rp_le(y, x, err); }
bool rp_ne(Real x, Real y, Real err = g_err) { return !rp_eq(x, y, err); }
template <typename T>
bool updMax(T& tmax, const T& x) {
  if (x > tmax) {
    tmax = x;
    return true;
  } else {
    return false;
  }
}
template <typename T>
bool updMin(T& tmin, const T& x) {
  if (x < tmin) {
    tmin = x;
    return true;
  } else {
    return false;
  }
}
struct Point {
  Real x;
  Real y;
  Point() : x(0), y(0) {}
  Point(Real x_, Real y_) : x(x_), y(y_) {}
  bool operator==(const Point& p) const { return x == p.x && y == p.y; }
  bool operator!=(const Point& p) const { return !(*this == p); }
  bool sim(const Point& p, Real err = g_err) const {
    return r_eq(x, p.x, err) && r_eq(y, p.y, err);
  }
  static bool sim(const Point& p1, const Point& p2, Real err = g_err) {
    return p1.sim(p2, err);
  }
  Point& operator+=(const Point& p) {
    x += p.x;
    y += p.y;
    return *this;
  }
  Point& operator-=(const Point& p) {
    x -= p.x;
    y -= p.y;
    return *this;
  }
  Point& operator*=(Real k) {
    x *= k;
    y *= k;
    return *this;
  }
  Point& operator/=(Real k) {
    x /= k;
    y /= k;
    return *this;
  }
  Point operator+(const Point& p) const { return Point(*this) += p; }
  Point operator-(const Point& p) const { return Point(*this) -= p; }
  Point operator*(Real k) const { return Point(*this) *= k; }
  Point operator/(Real k) const { return Point(*this) /= k; }
  Point operator-() const { return (*this) * (-1); }
  Real len() const { return hypot(x, y); }
  static Point polar(Real r, Real th) {
    return Point(r * cos(th), r * sin(th));
  }
  Point rotate(Real th) const { return polar(len(), atan2(y, x) + th); }
  Point rotateQ() const { return Point(-y, x); }
  bool parallel(const Point& p, Real err = g_err) const {
    return r_eq(x * p.y, y * p.x, err);
  }
  Real innerProd(const Point& p) const { return x * p.x + y * p.y; }
  Real outerProd(const Point& p) const { return x * p.y - y * p.x; }
  Real arg() const { return atan2(y, x); }
  Real angle(const Point& p) const {
    Real th = atan2(p.y, p.x) - atan2(y, x);
    return th > 3.141592653589793238462643383279502884L
               ? th - 2 * 3.141592653589793238462643383279502884L
           : th <= -3.141592653589793238462643383279502884L
               ? th + 2 * 3.141592653589793238462643383279502884L
               : th;
  }
};
Point operator*(Real k, const Point& p) { return p * k; }
ostream& operator<<(ostream& os, const Point& p) {
  return os << "(" << p.x << ", " << p.y << ")";
}
struct Line;
ostream& operator<<(ostream& os, const Line& l);
struct Line {
  Point dir;
  Point base;
  static Line x_axis;
  static Line y_axis;
  static constexpr int SIDE_ON = 1;
  static constexpr int SIDE_P = 2;
  static constexpr int SIDE_N = 4;
  static constexpr int IST_NONE = -1;
  static constexpr int IST_ALL = -2;
  static constexpr int IST_ONE = 0;
  Line() : dir(0, 0), base(0, 0) {}
  Line(const Point& d, const Point& b) : dir(d), base(b) {}
  bool operator==(const Line& l) const {
    return dir == l.dir && base == l.base;
  }
  bool operator!=(const Line& l) const { return !(*this == l); }
  bool sim(const Line& l1, Real err = g_err) const {
    return dir.sim(l1.dir, err) && dir.sim(l1.base - base, err);
  }
  static bool sim(const Line& l1, const Line& l2, Real err = g_err) {
    return l1.sim(l2, err);
  }
  static Line connect(const Point& p1, const Point& p2) {
    return Line(p2 - p1, p1);
  }
  bool parallel(const Line& l, Real err = g_err) const {
    return dir.parallel(l.dir, err);
  }
  int ptSide(const Point& p, Real err = g_err) const {
    Real t1 = dir.y * (p.x - base.x);
    Real t2 = dir.x * (p.y - base.y);
    if (r_eq(t1, t2, err)) return SIDE_ON;
    if (r_lt(t1, t2, err)) return SIDE_P;
    return SIDE_N;
  }
  bool ptOn(const Point& p, Real err = g_err) const {
    return ptSide(p, err) == SIDE_ON;
  }
  tuple<int, Real, Real> intersect_coeff(const Line& l) const {
    if (dir.parallel(l.dir)) {
      if (ptOn(l.base))
        return make_tuple(IST_ALL, 0, 0);
      else
        return make_tuple(IST_NONE, 0, 0);
    } else {
      Real d = dir.x * (-l.dir.y) - (-l.dir.x) * dir.y;
      Point z = l.base - base;
      Real t1 = ((-l.dir.y) * z.x + l.dir.x * z.y) / d;
      Real t2 = ((-dir.y) * z.x + dir.x * z.y) / d;
      return {IST_ONE, t1, t2};
    }
  }
  Point unsafe_intersect(const Line& l) const {
    auto [rc, t1, t2] = intersect_coeff(l);
    assert(rc == IST_ONE);
    return base + t1 * dir;
  }
  Point perpend_foot(const Point& p) const {
    Real t1 = perpend_foot_coeff(p);
    return base + t1 * dir;
  }
  Real perpend_foot_coeff(const Point& p) const {
    auto [rc, t1, t2] = intersect_coeff(Line(dir.rotateQ(), p));
    return t1;
  }
  Real len(const Point& p) const { return (p - perpend_foot(p)).len(); }
};
ostream& operator<<(ostream& os, const Line& l) {
  return os << "[d " << l.dir << ", b " << l.base << ")";
}
Line Line::x_axis(Point(1, 0), Point(0, 0));
Line Line::y_axis(Point(0, 1), Point(0, 0));
struct Circle {
  Point c;
  Real r;
  Circle() : c(0, 0), r(0) {}
  Circle(const Point& c_, Real r_) : c(c_), r(r_) {}
  bool operator==(const Circle& o) const { return c == o.c && r == o.r; }
  bool operator!=(const Circle& o) const { return !(*this == o); }
  bool sim(const Circle& o, Real err = g_err) const {
    return c.sim(o.c, err) && r_eq(r, o.r, err);
  }
  static bool sim(const Circle& c1, const Circle& c2, Real err = g_err) {
    return c1.sim(c2, err);
  }
  bool ptOn(const Point& p, Real err = g_err) const {
    return r_eq((p - c).len(), r, err);
  }
  tuple<bool, Point, Point> intersect(const Line& o) const {
    Point f = o.perpend_foot(c);
    Real d = (f - c).len();
    if (d > r) return make_tuple(false, Point(), Point());
    Real t = sqrt(r * r - d * d);
    Point e = o.dir / o.dir.len();
    return make_tuple(true, f + t * e, f - t * e);
  }
  tuple<bool, Point, Point> intersect(const Circle& o) const {
    Real d = (o.c - c).len();
    if (d + r < o.r || d + o.r < r || r + o.r < d) {
      return make_tuple(false, Point(), Point());
    }
    Point v = (o.c - c) / d;
    Real t = (r * r - o.r * o.r + d * d) / (2 * d);
    Line l(v.rotateQ(), c + t * v);
    return intersect(l);
  }
};
ostream& operator<<(ostream& os, const Circle& circ) {
  return os << "[c " << circ.c << ", " << circ.r << "]";
}
Point circumcenter(const Point& z1, const Point& z2, const Point& z3) {
  Line l12((z2 - z1).rotateQ(), (z1 + z2) / 2);
  Line l23((z3 - z2).rotateQ(), (z2 + z3) / 2);
  return l12.unsafe_intersect(l23);
}
vector<Point> convex_hull(const vector<Point>& pts) {
  vector<Point> spts(pts);
  int n = pts.size();
  if (n == 0) return vector<Point>();
  auto sub = [&]() -> vector<Point> {
    vector<Point> ret;
    for (int i = 0; i < n; i++) {
      Point pt = spts.at(i);
      if (i > 0 && spts.at(i - 1).sim(spts.at(i))) continue;
      while (true) {
        int rs = ret.size();
        if (rs - 2 < 0) break;
        Point q0 = ret.at(rs - 2);
        Point q1 = ret.at(rs - 1);
        if ((q0 - q1).outerProd(pt - q1) < 0) break;
        ret.pop_back();
      }
      ret.push_back(pt);
    }
    ret.pop_back();
    return ret;
  };
  sort(spts.begin(), spts.end(), [](const Point& a, const Point& b) -> bool {
    if (a.x != b.x) return a.x < b.x;
    return a.y < b.y;
  });
  auto vec1 = sub();
  reverse(spts.begin(), spts.end());
  auto vec2 = sub();
  vec1.insert(vec1.end(), vec2.begin(), vec2.end());
  if (vec1.empty()) return vector<Point>({pts.at(0)});
  return vec1;
}
tuple<Real, int, int> convex_diameter(const vector<Point>& pts) {
  int n = pts.size();
  if (n <= 1) {
    cerr << "diameter is called with <=1 points.\n";
    exit(1);
  }
  auto conn = [&](long long int i, long long int j) -> Point {
    return pts.at(j % n) - pts.at(i % n);
  };
  auto edge = [&](long long int i) -> Point { return conn(i, i + 1); };
  if (n == 2) return make_tuple(conn(0, 1).len(), 0, 1);
  int k = -1;
  int m = -1;
  for (int i = 0, cnt = 0; cnt < 2; i++) {
    if (edge(i).y <= 0 && edge(i + 1).y > 0) {
      m = i + 1;
      cnt++;
    }
    if (edge(i).y >= 0 && edge(i + 1).y < 0) {
      k = i + 1;
      cnt++;
    }
  }
  Real vmax = 0;
  int k0 = -1, m0 = -1;
  bool run_k = true;
  bool run_m = true;
  while (run_k || run_m) {
    if (!run_m ||
        (run_k && edge(k).arg() - (-3.141592653589793238462643383279502884L) <=
                      edge(m).arg())) {
      if (updMax(vmax, conn(k + 1, m).len())) {
        k0 = k + 1, m0 = m;
      }
      k++;
      if (edge(k).y > 0) run_k = false;
    } else {
      if (updMax(vmax, conn(k, m + 1).len())) {
        k0 = k, m0 = m + 1;
      }
      m++;
      if (edge(m).y < 0) run_m = false;
    }
  }
  return make_tuple(vmax, k0 % n, m0 % n);
}
int in_triangle(const Point& pt, const Point& tr0, const Point& tr1,
                const Point& tr2) {
  auto chk = [&](const Point& b, const Point& e, const Point& p) -> bool {
    Point be = e - b;
    Point bp = p - b;
    Real r = r_eq(be.x, 0.0) ? bp.y / be.y : bp.x / be.x;
    return 0.0 <= r && r <= 1.0;
  };
  Line l01 = Line::connect(tr0, tr1);
  Line l12 = Line::connect(tr1, tr2);
  Line l20 = Line::connect(tr2, tr0);
  int side = l01.ptSide(tr2);
  if (side == Line::SIDE_ON) {
    if (!l01.ptOn(pt)) return Line::SIDE_N;
    return chk(tr0, tr1, pt) || chk(tr1, tr2, pt) || chk(tr2, tr0, pt)
               ? Line::SIDE_ON
               : Line::SIDE_N;
  }
  int other = side ^ (Line::SIDE_P | Line::SIDE_N);
  if (l01.ptSide(pt) == other || l12.ptSide(pt) == other ||
      l20.ptSide(pt) == other)
    return Line::SIDE_N;
  if (l01.ptSide(pt) == Line::SIDE_ON || l12.ptSide(pt) == Line::SIDE_ON ||
      l20.ptSide(pt) == Line::SIDE_ON)
    return Line::SIDE_ON;
  return Line::SIDE_P;
}
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
  os << "(" << p.first << ", " << p.second << ")";
  return os;
}
template <typename T1, typename T2, typename T3>
ostream& operator<<(ostream& os, const tuple<T1, T2, T3>& t) {
  os << "(" << get<0>(t) << ", " << get<1>(t) << ", " << get<2>(t) << ")";
  return os;
}
template <typename T1, typename T2, typename T3, typename T4>
ostream& operator<<(ostream& os, const tuple<T1, T2, T3, T4>& t) {
  os << "(" << get<0>(t) << ", " << get<1>(t) << ", " << get<2>(t) << ", "
     << get<3>(t) << ")";
  return os;
}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  os << '[';
  for (auto it = v.begin(); it != v.end(); it++) {
    if (it != v.begin()) os << ", ";
    os << *it;
  }
  os << ']';
  return os;
}
template <typename T, typename C>
ostream& operator<<(ostream& os, const set<T, C>& v) {
  os << '{';
  for (auto it = v.begin(); it != v.end(); it++) {
    if (it != v.begin()) os << ", ";
    os << *it;
  }
  os << '}';
  return os;
}
template <typename T, typename C>
ostream& operator<<(ostream& os, const unordered_set<T, C>& v) {
  os << '{';
  for (auto it = v.begin(); it != v.end(); it++) {
    if (it != v.begin()) os << ", ";
    os << *it;
  }
  os << '}';
  return os;
}
template <typename T, typename C>
ostream& operator<<(ostream& os, const multiset<T, C>& v) {
  os << '{';
  for (auto it = v.begin(); it != v.end(); it++) {
    if (it != v.begin()) os << ", ";
    os << *it;
  }
  os << '}';
  return os;
}
template <typename T1, typename T2, typename C>
ostream& operator<<(ostream& os, const map<T1, T2, C>& mp) {
  os << '[';
  for (auto it = mp.begin(); it != mp.end(); it++) {
    if (it != mp.begin()) os << ", ";
    os << it->first << ": " << it->second;
  }
  os << ']';
  return os;
}
template <typename T1, typename T2, typename C>
ostream& operator<<(ostream& os, const unordered_map<T1, T2, C>& mp) {
  os << '[';
  for (auto it = mp.begin(); it != mp.end(); it++) {
    if (it != mp.begin()) os << ", ";
    os << it->first << ": " << it->second;
  }
  os << ']';
  return os;
}
template <typename T, typename T2>
ostream& operator<<(ostream& os, const queue<T, T2>& orig) {
  queue<T, T2> que(orig);
  bool first = true;
  os << '[';
  while (!que.empty()) {
    T x = que.front();
    que.pop();
    if (!first) os << ", ";
    os << x;
    first = false;
  }
  return os << ']';
}
template <typename T, typename T2>
ostream& operator<<(ostream& os, const deque<T, T2>& orig) {
  deque<T, T2> que(orig);
  bool first = true;
  os << '[';
  while (!que.empty()) {
    T x = que.front();
    que.pop_front();
    if (!first) os << ", ";
    os << x;
    first = false;
  }
  return os << ']';
}
template <typename T, typename T2, typename T3>
ostream& operator<<(ostream& os, const priority_queue<T, T2, T3>& orig) {
  priority_queue<T, T2, T3> pq(orig);
  bool first = true;
  os << '[';
  while (!pq.empty()) {
    T x = pq.top();
    pq.pop();
    if (!first) os << ", ";
    os << x;
    first = false;
  }
  return os << ']';
}
template <typename T>
ostream& operator<<(ostream& os, const stack<T>& st) {
  stack<T> tmp(st);
  os << '[';
  bool first = true;
  while (!tmp.empty()) {
    T& t = tmp.top();
    if (first)
      first = false;
    else
      os << ", ";
    os << t;
    tmp.pop();
  }
  os << ']';
  return os;
}
ostream& operator<<(ostream& os, int8_t x) {
  os << (int32_t)x;
  return os;
}
template <class... Args>
string dbgFormat(const char* fmt, Args... args) {
  size_t len = snprintf(nullptr, 0, fmt, args...);
  char buf[len + 1];
  snprintf(buf, len + 1, fmt, args...);
  return string(buf);
}
template <class Head>
void dbgLog(bool with_nl, Head&& head) {
  cerr << head;
  if (with_nl) cerr << endl;
}
template <class Head, class... Tail>
void dbgLog(bool with_nl, Head&& head, Tail&&... tail) {
  cerr << head << " ";
  dbgLog(with_nl, forward<Tail>(tail)...);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << setprecision(20);
  long long int n, q;
  cin >> n >> q;
  vector<Point> P(n);
  for (long long int i = 0; i < n; i++) {
    long long int x, y;
    cin >> x >> y;
    P[i] = Point(x, y);
  }
  Point g(0, 0);
  Real tots = 0;
  for (long long int i = 1; i < n - 1; i++) {
    Point lg = (P[0] + P[i] + P[i + 1]) / 3.0;
    Point v0i = P[i] - P[0];
    Point v0j = P[i + 1] - P[0];
    Real s = abs(v0i.x * v0j.y - v0i.y * v0j.x);
    tots += s;
    g += s * lg;
  }
  g = g / tots;
  vector<Real> L(n), Th(n);
  for (long long int i = 0; i < n; i++) {
    L[i] = (P[i] - g).len();
    Th[i] = (P[0] - g).angle(P[i] - g);
  };
  ;
  ;
  Real th0 = (P[0] - g).arg();
  ;
  long long int pinA = 0, pinB = 1;
  for (long long int _q = 0; _q < q; _q++) {
    long long int tp;
    cin >> tp;
    if (tp == 1) {
      long long int f, t;
      cin >> f >> t;
      f--;
      t--;
      if (f == pinA) {
        pinA = pinB;
        pinB = t;
      } else {
        pinB = t;
      };
      Point e(L[pinA], 0);
      Point pa = g + e.rotate(th0 + Th[pinA]);
      g = pa + e.rotate(3 * 3.141592653589793238462643383279502884L / 2);
      ;
      th0 += 3.141592653589793238462643383279502884L / 2.0 - (th0 + Th[pinA]);
      ;
    } else if (tp == 2) {
      long long int v;
      cin >> v;
      v--;
      Point e(L[v], 0);
      Point pv = g + e.rotate(th0 + Th[v]);
      cout << pv.x << " " << pv.y << "\n";
    }
  }
  return 0;
}