#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:36777216")
using namespace std;
template <class T>
inline T &RD(T &);
template <class T>
inline void OT(const T &);
inline long long RD() {
  long long x;
  return RD(x);
}
inline double &RF(double &);
inline double RF() {
  double x;
  return RF(x);
}
inline char *RS(char *s);
inline char &RC(char &c);
inline char RC();
inline char &RC(char &c) {
  scanf(" %c", &c);
  return c;
}
inline char RC() {
  char c;
  return RC(c);
}
template <class T>
inline T &RDD(T &);
inline long long RDD() {
  long long x;
  return RDD(x);
}
template <class T0, class T1>
inline T0 &RD(T0 &x0, T1 &x1) {
  RD(x0), RD(x1);
  return x0;
}
template <class T0, class T1, class T2>
inline T0 &RD(T0 &x0, T1 &x1, T2 &x2) {
  RD(x0), RD(x1), RD(x2);
  return x0;
}
template <class T0, class T1, class T2, class T3>
inline T0 &RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3) {
  RD(x0), RD(x1), RD(x2), RD(x3);
  return x0;
}
template <class T0, class T1, class T2, class T3, class T4>
inline T0 &RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4) {
  RD(x0), RD(x1), RD(x2), RD(x3), RD(x4);
  return x0;
}
template <class T0, class T1, class T2, class T3, class T4, class T5>
inline T0 &RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5) {
  RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5);
  return x0;
}
template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
inline T0 &RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5, T6 &x6) {
  RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5), RD(x6);
  return x0;
}
template <class T0, class T1>
inline void OT(const T0 &x0, const T1 &x1) {
  OT(x0), OT(x1);
}
template <class T0, class T1, class T2>
inline void OT(const T0 &x0, const T1 &x1, const T2 &x2) {
  OT(x0), OT(x1), OT(x2);
}
template <class T0, class T1, class T2, class T3>
inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3) {
  OT(x0), OT(x1), OT(x2), OT(x3);
}
template <class T0, class T1, class T2, class T3, class T4>
inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3,
               const T4 &x4) {
  OT(x0), OT(x1), OT(x2), OT(x3), OT(x4);
}
template <class T0, class T1, class T2, class T3, class T4, class T5>
inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3,
               const T4 &x4, const T5 &x5) {
  OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5);
}
template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3,
               const T4 &x4, const T5 &x5, const T6 &x6) {
  OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5), OT(x6);
}
inline char &RC(char &a, char &b) {
  RC(a), RC(b);
  return a;
}
inline char &RC(char &a, char &b, char &c) {
  RC(a), RC(b), RC(c);
  return a;
}
inline char &RC(char &a, char &b, char &c, char &d) {
  RC(a), RC(b), RC(c), RC(d);
  return a;
}
inline char &RC(char &a, char &b, char &c, char &d, char &e) {
  RC(a), RC(b), RC(c), RC(d), RC(e);
  return a;
}
inline char &RC(char &a, char &b, char &c, char &d, char &e, char &f) {
  RC(a), RC(b), RC(c), RC(d), RC(e), RC(f);
  return a;
}
inline char &RC(char &a, char &b, char &c, char &d, char &e, char &f, char &g) {
  RC(a), RC(b), RC(c), RC(d), RC(e), RC(f), RC(g);
  return a;
}
inline double &RF(double &a, double &b) {
  RF(a), RF(b);
  return a;
}
inline double &RF(double &a, double &b, double &c) {
  RF(a), RF(b), RF(c);
  return a;
}
inline double &RF(double &a, double &b, double &c, double &d) {
  RF(a), RF(b), RF(c), RF(d);
  return a;
}
inline double &RF(double &a, double &b, double &c, double &d, double &e) {
  RF(a), RF(b), RF(c), RF(d), RF(e);
  return a;
}
inline double &RF(double &a, double &b, double &c, double &d, double &e,
                  double &f) {
  RF(a), RF(b), RF(c), RF(d), RF(e), RF(f);
  return a;
}
inline double &RF(double &a, double &b, double &c, double &d, double &e,
                  double &f, double &g) {
  RF(a), RF(b), RF(c), RF(d), RF(e), RF(f), RF(g);
  return a;
}
inline void RS(char *s1, char *s2) { RS(s1), RS(s2); }
inline void RS(char *s1, char *s2, char *s3) { RS(s1), RS(s2), RS(s3); }
template <class T0, class T1>
inline T0 &RDD(T0 &a, T1 &b) {
  RDD(a), RDD(b);
  return a;
}
template <class T0, class T1, class T2>
inline T1 &RDD(T0 &a, T1 &b, T2 &c) {
  RDD(a), RDD(b), RDD(c);
  return a;
}
template <class T>
inline void RST(T &A) {
  memset(A, 0, sizeof(A));
}
template <class T>
inline void FLC(T &A, int x) {
  memset(A, x, sizeof(A));
}
template <class T>
inline void CLR(T &A) {
  A.clear();
}
template <class T0, class T1>
inline void RST(T0 &A0, T1 &A1) {
  RST(A0), RST(A1);
}
template <class T0, class T1, class T2>
inline void RST(T0 &A0, T1 &A1, T2 &A2) {
  RST(A0), RST(A1), RST(A2);
}
template <class T0, class T1, class T2, class T3>
inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3) {
  RST(A0), RST(A1), RST(A2), RST(A3);
}
template <class T0, class T1, class T2, class T3, class T4>
inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4) {
  RST(A0), RST(A1), RST(A2), RST(A3), RST(A4);
}
template <class T0, class T1, class T2, class T3, class T4, class T5>
inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5) {
  RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5);
}
template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6) {
  RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5), RST(A6);
}
template <class T0, class T1>
inline void FLC(T0 &A0, T1 &A1, int x) {
  FLC(A0, x), FLC(A1, x);
}
template <class T0, class T1, class T2>
inline void FLC(T0 &A0, T1 &A1, T2 &A2, int x) {
  FLC(A0, x), FLC(A1, x), FLC(A2, x);
}
template <class T0, class T1, class T2, class T3>
inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, int x) {
  FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x);
}
template <class T0, class T1, class T2, class T3, class T4>
inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, int x) {
  FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x);
}
template <class T0, class T1, class T2, class T3, class T4, class T5>
inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, int x) {
  FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x), FLC(A5, x);
}
template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6, int x) {
  FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x), FLC(A5, x),
      FLC(A6, x);
}
template <class T>
inline void CLR(priority_queue<T> &Q) {
  while (!Q.empty()) Q.pop();
}
template <class T>
inline void CLR(stack<T> &S) {
  while (!S.empty()) S.pop();
}
template <class T>
inline void CLR(queue<T> &Q) {
  while (!Q.empty()) Q.pop();
}
template <class T0, class T1>
inline void CLR(T0 &A0, T1 &A1) {
  CLR(A0), CLR(A1);
}
template <class T0, class T1, class T2>
inline void CLR(T0 &A0, T1 &A1, T2 &A2) {
  CLR(A0), CLR(A1), CLR(A2);
}
template <class T0, class T1, class T2, class T3>
inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3) {
  CLR(A0), CLR(A1), CLR(A2), CLR(A3);
}
template <class T0, class T1, class T2, class T3, class T4>
inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4) {
  CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4);
}
template <class T0, class T1, class T2, class T3, class T4, class T5>
inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5) {
  CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5);
}
template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6) {
  CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5), CLR(A6);
}
template <class T>
inline void CLR(T &A, int n) {
  for (int i = 0; i < n; ++i) CLR(A[i]);
}
template <class T>
inline bool EPT(T &a) {
  return a.empty();
}
template <class T>
inline T &SRT(T &A) {
  sort(A.begin(), A.end());
  return A;
}
template <class T, class C>
inline T &SRT(T &A, C cmp) {
  sort(A.begin(), A.end(), cmp);
  return A;
}
template <class T>
inline T &RVS(T &A) {
  reverse(A.begin(), A.end());
  return A;
}
template <class T>
inline T &UNQQ(T &A) {
  A.resize(unique(A.begin(), A.end()) - A.begin());
  return A;
}
template <class T>
inline T &UNQ(T &A) {
  SRT(A);
  return UNQQ(A);
}
template <class T, class C>
inline T &UNQ(T &A, C cmp) {
  SRT(A, cmp);
  return UNQQ(A);
}
const int MOD = int(1e9) + 7;
const int INF = 0x3f3f3f3f;
const long long INFF = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;
const double OO = 1e20;
const double PI = acos(-1.0);
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, 1, -1};
template <class T>
inline bool checkMin(T &a, const T b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
inline bool checkMax(T &a, const T b) {
  return a < b ? a = b, 1 : 0;
}
template <class T, class C>
inline bool checkUpd(T &a, const T b, C c) {
  return c(b, a) ? a = b, 1 : 0;
}
template <class T>
inline T min(T a, T b, T c) {
  return min(min(a, b), c);
}
template <class T>
inline T max(T a, T b, T c) {
  return max(max(a, b), c);
}
template <class T>
inline T min(T a, T b, T c, T d) {
  return min(min(a, b), min(c, d));
}
template <class T>
inline T max(T a, T b, T c, T d) {
  return max(max(a, b), max(c, d));
}
template <class T>
inline T min(T a, T b, T c, T d, T e) {
  return min(min(min(a, b), min(c, d)), e);
}
template <class T>
inline T max(T a, T b, T c, T d, T e) {
  return max(max(max(a, b), max(c, d)), e);
}
template <class T>
inline T sqr(T a) {
  return a * a;
}
template <class T>
inline T cub(T a) {
  return a * a * a;
}
template <class T>
inline T ceil(T x, T y) {
  return (x - 1) / y + 1;
}
template <class T>
T abs(T x) {
  return x > 0 ? x : -x;
}
inline int sgn(double x) { return x < -EPS ? -1 : x > EPS; }
inline int sgn(double x, double y) { return sgn(x - y); }
inline double cos(double a, double b, double c) {
  return (sqr(a) + sqr(b) - sqr(c)) / (2 * a * b);
}
inline double cot(double x) { return 1. / tan(x); };
inline double sec(double x) { return 1. / cos(x); };
inline double csc(double x) { return 1. / sin(x); };
namespace CG {
inline double dist2(double x, double y) { return sqr(x) + sqr(y); }
struct Po {
  double x, y;
  Po(double x = 0, double y = 0) : x(x), y(y) {}
  void in() { RF(x, y); }
  void out() { printf("(%.2f,%.2f)", x, y); }
  inline friend istream &operator>>(istream &i, Po &p) {
    return i >> p.x >> p.y;
  }
  inline friend ostream &operator<<(ostream &o, Po p) {
    return o << "(" << p.x << ", " << p.y << ")";
  }
  Po operator-() const { return Po(-x, -y); }
  Po &operator+=(const Po &p) {
    x += p.x, y += p.y;
    return *this;
  }
  Po &operator-=(const Po &p) {
    x -= p.x, y -= p.y;
    return *this;
  }
  Po &operator*=(double k) {
    x *= k, y *= k;
    return *this;
  }
  Po &operator/=(double k) {
    x /= k, y /= k;
    return *this;
  }
  Po &operator*=(const Po &p) { return *this = *this * p; }
  Po &operator/=(const Po &p) { return *this = *this / p; }
  Po operator+(const Po &p) const { return Po(x + p.x, y + p.y); }
  Po operator-(const Po &p) const { return Po(x - p.x, y - p.y); }
  Po operator*(double k) const { return Po(x * k, y * k); }
  Po operator/(double k) const { return Po(x / k, y / k); }
  Po operator*(const Po &p) const {
    return Po(x * p.x - y * p.y, y * p.x + x * p.y);
  }
  Po operator/(const Po &p) const {
    return Po(x * p.x + y * p.y, y * p.x - x * p.y) / p.len2();
  }
  bool operator==(const Po &p) const { return !sgn(x, p.x) && !sgn(y, p.y); };
  bool operator!=(const Po &p) const { return sgn(x, p.x) || sgn(y, p.y); }
  bool operator<(const Po &p) const {
    return sgn(x, p.x) < 0 || !sgn(x, p.x) && sgn(y, p.y) < 0;
  }
  bool operator<=(const Po &p) const {
    return sgn(x, p.x) < 0 || !sgn(x, p.x) && sgn(y, p.y) <= 0;
  }
  bool operator>(const Po &p) const { return !(*this <= p); }
  bool operator>=(const Po &p) const { return !(*this < p); }
  double len2() const { return dist2(x, y); }
  double len() const { return sqrt(len2()); }
  double arg() const { return atan2(y, x); }
  Po &_1() { return *this /= len(); }
  Po &conj() {
    y = -y;
    return *this;
  }
  Po &lt() {
    swap(x, y), x = -x;
    return *this;
  }
  Po &rt() {
    swap(x, y), y = -y;
    return *this;
  }
  Po &rot(double a, const Po &o = Po()) {
    *this -= o;
    *this *= Po(cos(a), sin(a));
    return *this += o;
  }
  inline int q() const { return (y > 0 || y == 0 && x >= 0) ? 0 : 1; }
};
inline double dot(double x1, double y1, double x2, double y2) {
  return x1 * x2 + y1 * y2;
}
inline double dot(const Po &a, const Po &b) { return dot(a.x, a.y, b.x, b.y); }
inline double dot(const Po &p0, const Po &p1, const Po &p2) {
  return dot(p1 - p0, p2 - p0);
}
inline double det(double x1, double y1, double x2, double y2) {
  return x1 * y2 - x2 * y1;
}
inline double det(const Po &a, const Po &b) { return det(a.x, a.y, b.x, b.y); }
inline double det(const Po &p0, const Po &p1, const Po &p2) {
  return det(p1 - p0, p2 - p0);
}
inline double ang(const Po &p0, const Po &p1) {
  return acos(dot(p0, p1) / p0.len() / p1.len());
}
inline double ang(const Po &p0, const Po &p1, const Po &p2) {
  return ang(p1 - p0, p2 - p0);
}
inline double ang(const Po &p0, const Po &p1, const Po &p2, const Po &p3) {
  return ang(p1 - p0, p3 - p2);
}
inline double dist2(const Po &a, const Po &b) {
  return dist2(a.x - b.x, a.y - b.y);
}
template <class T1, class T2>
inline int dett(const T1 &x, const T2 &y) {
  return sgn(det(x, y));
}
template <class T1, class T2, class T3>
inline int dett(const T1 &x, const T2 &y, const T3 &z) {
  return sgn(det(x, y, z));
}
template <class T1, class T2, class T3, class T4>
inline int dett(const T1 &x, const T2 &y, const T3 &z, const T4 &w) {
  return sgn(det(x, y, z, w));
}
template <class T1, class T2>
inline int dott(const T1 &x, const T2 &y) {
  return sgn(dot(x, y));
}
template <class T1, class T2, class T3>
inline int dott(const T1 &x, const T2 &y, const T3 &z) {
  return sgn(dot(x, y, z));
}
template <class T1, class T2, class T3, class T4>
inline int dott(const T1 &x, const T2 &y, const T3 &z, const T4 &w) {
  return sgn(dot(x, y, z, w));
}
template <class T1, class T2>
inline double arg(const T1 &x, const T2 &y) {
  double a = ang(x, y);
  return ~dett(x, y) ? a : 2 * PI - a;
}
template <class T1, class T2, class T3>
inline double arg(const T1 &x, const T2 &y, const T3 &z) {
  double a = ang(x, y, z);
  return ~dett(x, y, z) ? a : 2 * PI - a;
}
template <class T1, class T2, class T3, class T4>
inline double arg(const T1 &x, const T2 &y, const T3 &z, const T4 &w) {
  double a = ang(x, y, z, w);
  return ~dett(x, y, z, w) ? a : 2 * PI - a;
}
template <class T1, class T2>
inline double dist(const T1 &x, const T2 &y) {
  return sqrt(dist2(x, y));
}
template <class T1, class T2, class T3>
inline double dist(const T1 &x, const T2 &y, const T3 &z) {
  return sqrt(dist2(x, y, z));
}
inline Po _1(Po p) { return p._1(); }
inline Po conj(Po p) { return p.conj(); }
inline Po lt(Po p) { return p.lt(); }
inline Po rt(Po p) { return p.rt(); }
inline Po rot(Po p, double a, const Po &o = Po()) { return p.rot(a, o); }
inline Po operator*(double k, const Po &p) { return p * k; }
inline Po operator/(double k, const Po &p) { return conj(p) * k / p.len2(); }
struct Line {
  Po a, b;
  Line(const Po &a = Po(), const Po &b = Po()) : a(a), b(b) {}
  Line(double x0, double y0, double x1, double y1)
      : a(Po(x0, y0)), b(Po(x1, y1)) {}
  Line(const Line &l) : a(l.a), b(l.b) {}
  Line(double A, double B, double C) {
    C = -C;
    if (!::sgn(A))
      a = Po(0, C / B), b = Po(1, C / B);
    else if (!::sgn(B))
      a = Po(C / A, 0), b = Po(C / A, 1);
    else
      a = Po(0, C / B), b = Po(1, (C - A) / B);
  }
  void in() { a.in(), b.in(); }
  inline friend istream &operator>>(istream &i, Line &p) {
    return i >> p.a >> p.b;
  }
  inline friend ostream &operator<<(ostream &o, Line p) {
    return o << p.a << "-" << p.b;
  }
  Line operator+(const Po &x) const { return Line(a + x, b + x); }
  Line operator-(const Po &x) const { return Line(a - x, b - x); }
  Line operator*(double k) const { return Line(a * k, b * k); }
  Line operator/(double k) const { return Line(a / k, b / k); }
  Po operator*(const Line &) const;
  Po d() const { return b - a; }
  double len2() const { return d().len2(); }
  double len() const { return d().len(); }
  double arg() const { return d().arg(); }
  int sgn(const Po &p) const { return dett(a, b, p); }
  int sgn(const Line &) const;
  bool sameSgn(const Po &p1, const Po &p2) const { return sgn(p1) == sgn(p2); }
  void getEquation(double &K, double &B) const {
    K = ::sgn(a.x, b.x) ? (b.y - a.y) / (b.x - a.x) : OO;
    B = a.y - K * a.x;
  }
  void getEquation(double &A, double &B, double &C) const {
    A = a.y - b.y, B = b.x - a.x, C = det(a, b);
  }
  Line &push(double r) {
    Po v = d()._1().lt() * r;
    a += v, b += v;
    return *this;
  }
};
inline double dot(const Line &l1, const Line &l2) {
  return dot(l1.d(), l2.d());
}
inline double dot(const Line &l, const Po &p) { return dot(l.a, l.b, p); }
inline double dot(const Po &p, const Line &l) { return dot(p, l.a, l.b); }
inline double det(const Line &l1, const Line &l2) {
  return det(l1.d(), l2.d());
}
inline double det(const Line &l, const Po &p) { return det(l.a, l.b, p); }
inline double det(const Po &p, const Line &l) { return det(p, l.a, l.b); }
inline double ang(const Line &l0, const Line &l1) {
  return ang(l0.d(), l1.d());
}
inline double ang(const Line &l, const Po &p) { return ang(l.a, l.b, p); }
inline double ang(const Po &p, const Line &l) { return ang(p, l.a, l.b); }
inline int Line::sgn(const Line &l) const { return dett(*this, l); }
inline Po Line::operator*(const Line &l) const {
  return a + d() * det(a, l) / det(*this, l);
}
inline Po operator&(const Po &p, const Line &l) {
  return l * Line(p, p + l.d().lt());
}
inline Po operator%(const Po &p, const Line &l) { return p & l * 2 - p; }
inline Line push(Line l, double r) { return l.push(r); }
struct Seg : public Line {
  Seg(const Po &a = Po(), const Po &b = Po()) : Line(a, b) {}
  Seg(double x0, double y0, double x1, double y1) : Line(x0, y0, x1, y1) {}
  Seg(const Line &l) : Line(l) {}
  Seg(const Po &a, double alpha) : Line(a, alpha) {}
  Seg(double A, double B, double C) : Line(A, B, C) {}
  inline int sgn(const Po &p) const;
  inline int sgn(const Line &l) const;
  inline bool qrt(const Seg &l) const;
  inline int sgn(const Seg &l) const;
};
inline int Seg::sgn(const Po &p) const {
  if (dett(p, a, b)) return -1;
  if (a == p || b == p) return 0;
  return -dott(p, a, b);
}
inline int Seg::sgn(const Line &l) const { return sgn(*this * l); }
inline bool Seg::qrt(const Seg &l) const {
  return min(a.x, b.x) <= max(l.a.x, l.b.x) &&
         min(l.a.x, l.b.x) <= max(a.x, b.x) &&
         min(a.y, b.y) <= max(l.a.y, l.b.y) &&
         min(l.a.y, l.b.y) <= max(a.y, b.y);
}
inline int Seg::sgn(const Seg &l) const {
  if (!qrt(l)) return -1;
  int d1 = dett(a, b, l.a), d2 = dett(a, b, l.b), d3 = dett(l.a, l.b, a),
      d4 = dett(l.a, l.b, b);
  if ((d1 ^ d2) == -2 && (d3 ^ d4) == -2) return 1;
  return ((!d1 && dott(l.a - a, l.a - b) <= 0) ||
          (!d2 && dott(l.b - a, l.b - b) <= 0) ||
          (!d3 && dott(a - l.a, a - l.b) <= 0) ||
          (!d4 && dott(b - l.a, b - l.b) <= 0))
             ? 0
             : -1;
}
inline double dist2(const Line &l, const Po &p) {
  return sqr(fabs(det(l.d(), p - l.a))) / l.len2();
}
inline double dist2(const Line &l1, const Line &l2) {
  return dett(l1, l2) ? 0 : dist2(l1, l2.a);
}
inline double dist2(const Seg &l, const Po &p) {
  Po pa = p - l.a, pb = p - l.b;
  if (dott(l.d(), pa) <= 0) return pa.len2();
  if (dott(l.d(), pb) >= 0) return pb.len2();
  return dist2(Line(l), p);
}
inline double dist2(const Seg &s, const Line &l) {
  Po v1 = s.a - l.a, v2 = s.b - l.a;
  double d1 = det(l.d(), v1), d2 = det(l.d(), v2);
  return sgn(d1) != sgn(d2) ? 0 : sqr(min(fabs(d1), fabs(d2))) / l.len2();
}
inline double dist2(const Seg &l1, const Seg &l2) {
  if (~l1.sgn(l2))
    return 0;
  else
    return min(dist2(l2, l1.a), dist2(l2, l1.b), dist2(l1, l2.a),
               dist2(l1, l2.b));
}
template <class T1, class T2>
inline double dist2(const T1 &a, const T2 &b) {
  return dist2(b, a);
}
}  // namespace CG
using namespace CG;
template <class T>
inline T &RD(T &x) {
  char c;
  while (!isdigit((c = getchar())))
    ;
  x = c - '0';
  while (isdigit((c = getchar()))) x = x * 10 + c - '0';
  return x;
}
template <class T>
inline T &RDD(T &x) {
  char c;
  while ((c = getchar()), c != '-' && !isdigit(c))
    ;
  if (c == '-') {
    x = '0' - (c = getchar());
    while (isdigit((c = getchar()))) x = x * 10 + '0' - c;
  } else {
    x = c - '0';
    while (isdigit((c = getchar()))) x = x * 10 + c - '0';
  }
  return x;
}
inline double &RF(double &x) {
  char c;
  while ((c = getchar()), c != '-' && c != '.' && !isdigit(c))
    ;
  if (c == '-')
    if ((c = getchar()) == '.') {
      x = 0;
      double l = 1;
      while (isdigit((c = getchar()))) l /= 10, x = x * 10 + '0' - c;
      x *= l;
    } else {
      x = '0' - c;
      while (isdigit((c = getchar()))) x = x * 10 + '0' - c;
      if (c == '.') {
        double l = 1;
        while (isdigit((c = getchar()))) l /= 10, x = x * 10 + '0' - c;
        x *= l;
      }
    }
  else if (c == '.') {
    x = 0;
    double l = 1;
    while (isdigit((c = getchar()))) l /= 10, x = x * 10 + c - '0';
    x *= l;
  } else {
    x = c - '0';
    while (isdigit((c = getchar()))) x = x * 10 + c - '0';
    if (c == '.') {
      double l = 1;
      while (isdigit((c = getchar()))) l /= 10, x = x * 10 + c - '0';
      x *= l;
    }
  }
  return x;
}
inline char *RS(char *s) {
  scanf("%s", s);
  return s;
}
int last_ans;
int Case;
template <class T>
inline void OT(const T &x) {
  printf("%d\n", x);
}
const int N = int(2e5) + 9;
vector<pair<int, int> > adj[N];
int e[N];
int n;
const int LV = 21;
int fa[LV][N], mx[LV][N], dep[N];
inline int move_up(int x, int t) {
  for (int lv = 0; t; ++lv, t >>= 1)
    if (t & 1) x = fa[lv][x];
  return x;
}
inline int mx_edge_up(int x, int t) {
  int z = 0;
  for (int lv = 0; t; ++lv, t >>= 1)
    if (t & 1) checkMax(z, mx[lv][x]), x = fa[lv][x];
  return z;
}
inline int lca(int x, int y) {
  if (dep[y] < dep[x]) swap(x, y);
  y = move_up(y, dep[y] - dep[x]);
  if (x == y) return x;
  for (int lv = LV - 1; lv >= 0; --lv)
    if (fa[lv][x] != fa[lv][y]) x = fa[lv][x], y = fa[lv][y];
  return fa[0][x];
}
void dfs(int u) {
  for (auto e : adj[u]) {
    int v = e.first, w = e.second;
    if (v != fa[0][u]) {
      fa[0][v] = u;
      mx[0][v] = w;
      dep[v] = dep[u] + 1;
      for (int lv = 0; mx[lv + 1][v] = max(mx[lv][v], mx[lv][fa[lv][v]]),
               fa[lv + 1][v] = fa[lv][fa[lv][v]];
           ++lv)
        ;
      dfs(v);
    }
  }
}
int maxEdge(int x, int y) {
  int z = lca(x, y);
  return max(mx_edge_up(x, dep[x] - dep[z]), mx_edge_up(y, dep[y] - dep[z]));
}
namespace DSU {
int P[N], R[N], eid[N], t[N];
inline void Make(int x) { P[x] = x, R[x] = 0, eid[x] = x, t[x] = 0; }
inline int Find(int x) { return P[x] == x ? x : P[x] = Find(P[x]); }
inline void Unionn(int x, int y) {
  if (R[x] == R[y])
    ++R[x];
  else if (R[x] < R[y])
    swap(x, y);
  P[y] = x;
  if (e[eid[x]] == e[eid[y]]) {
    checkMax(t[x], max(t[y], maxEdge(eid[x], eid[y])));
  } else {
    if (e[eid[y]] > e[eid[x]]) {
      eid[x] = eid[y];
      t[x] = t[y];
    }
  }
}
inline void Union(int x, int y) { x = Find(x), y = Find(y), Unionn(x, y); }
inline void Init() {
  for (int i = 0; i < n; ++i) Make(i);
}
}  // namespace DSU
using namespace DSU;
struct Edge {
  int a, b, c, t;
  void in() {
    RD(a, b, c, t);
    --a, --b;
    adj[a].push_back({b, t});
    adj[b].push_back({a, t});
  }
  void add() { Union(a, b); }
} E[N];
struct Query {
  int v, x, id, z1, z2;
  void in() {
    RD(v, x);
    --x;
  }
  void gao() {
    int y = eid[Find(x)];
    z1 = e[y];
    z2 = max(t[Find(x)], maxEdge(x, y));
  }
  void out() { printf("%d %d\n", z1, z2); }
} Q[N];
int main() {
  int q;
  RD(n, q);
  for (int i = 0; i < n; ++i) RD(e[i]);
  for (int i = 0; i < n - 1; ++i) E[i].in();
  for (int i = 0; i < q; ++i) Q[i].in(), Q[i].id = i;
  Init();
  dfs(0);
  sort(E, E + n - 1, [&](const Edge a, const Edge b) { return a.c > b.c; });
  sort(Q, Q + q, [&](const Query a, const Query b) { return a.v > b.v; });
  int Ei = 0;
  for (int i = 0; i < q; ++i) {
    while (Ei < n - 1 && E[Ei].c >= Q[i].v) E[Ei++].add();
    Q[i].gao();
  }
  sort(Q, Q + q, [&](const Query a, const Query b) { return a.id < b.id; });
  for (int i = 0; i < q; ++i) Q[i].out();
}

### Prompt

Create a solution in Cpp for the following problem:

Omkar is hosting tours of his country, Omkarland! There are n cities in Omkarland, and, rather curiously, there are exactly n-1 bidirectional roads connecting the cities to each other. It is guaranteed that you can reach any city from any other city through the road network.

Every city has an enjoyment value e. Each road has a capacity c, denoting the maximum number of vehicles that can be on it, and an associated toll t. However, the toll system in Omkarland has an interesting quirk: if a vehicle travels on multiple roads on a single journey, they pay only the highest toll of any single road on which they traveled. (In other words, they pay max t over all the roads on which they traveled.) If a vehicle traverses no roads, they pay 0 toll.

Omkar has decided to host q tour groups. Each tour group consists of v vehicles starting at city x. (Keep in mind that a tour group with v vehicles can travel only on roads with capacity ≥ v.) Being the tour organizer, Omkar wants his groups to have as much fun as they possibly can, but also must reimburse his groups for the tolls that they have to pay. Thus, for each tour group, Omkar wants to know two things: first, what is the enjoyment value of the city y with maximum enjoyment value that the tour group can reach from their starting city, and second, how much per vehicle will Omkar have to pay to reimburse the entire group for their trip from x to y? (This trip from x to y will always be on the shortest path from x to y.)

In the case that there are multiple reachable cities with the maximum enjoyment value, Omkar will let his tour group choose which one they want to go to. Therefore, to prepare for all possible scenarios, he wants to know the amount of money per vehicle that he needs to guarantee that he can reimburse the group regardless of which city they choose.

Input

The first line contains two integers n and q (2 ≤ n ≤ 2 ⋅ 10^5, 1 ≤ q ≤ 2 ⋅ 10^5), representing the number of cities and the number of groups, respectively.

The next line contains n integers e_1, e_2, …, e_n (1 ≤ e_i ≤ 10^9), where e_i represents the enjoyment value for city i.

The next n-1 lines each contain four integers a, b, c, and t (1 ≤ a,b ≤ n, 1 ≤ c ≤ 10^9, 1 ≤ t ≤ 10^9), representing an road between city a and city b with capacity c and toll t.

The next q lines each contain two integers v and x (1 ≤ v ≤ 10^9, 1 ≤ x ≤ n), representing the number of vehicles in the tour group and the starting city, respectively.

Output

Output q lines. The i-th line should contain two integers: the highest possible enjoyment value of a city reachable by the i-th tour group, and the amount of money per vehicle Omkar needs to guarantee that he can reimburse the i-th tour group.

Examples

Input


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


Output


3 8
3 0
3 2


Input


5 5
1 2 3 4 5
1 2 4 1
1 3 3 1
1 4 2 1
2 5 1 1
5 1
4 1
3 1
2 1
1 1


Output


1 0
2 1
3 1
4 1
5 1


Input


5 5
1 2 2 2 2
1 2 5 8
1 3 6 3
1 4 4 5
1 5 7 1
4 1
5 1
6 1
7 1
8 1


Output


2 8
2 8
2 3
2 1
1 0

Note

A map of the first sample is shown below. For the nodes, unbolded numbers represent indices and bolded numbers represent enjoyment values. For the edges, unbolded numbers represent capacities and bolded numbers represent tolls.

<image>

For the first query, a tour group of size 1 starting at city 3 can reach cities 1, 2, 3, 4, and 5. Thus, the largest enjoyment value that they can reach is 3. If the tour group chooses to go to city 4, Omkar will have to pay 8 per vehicle, which is the maximum.

For the second query, a tour group of size 9 starting at city 5 can reach only city 5. Thus, the largest reachable enjoyment value is still 3, and Omkar will pay 0 per vehicle.

For the third query, a tour group of size 6 starting at city 2 can reach cities 2 and 4. The largest reachable enjoyment value is again 3. If the tour group chooses to go to city 4, Omkar will have to pay 2 per vehicle, which is the maximum.

A map of the second sample is shown below:

<image>

For the first query, a tour group of size 5 starting at city 1 can only reach city 1. Thus, their maximum enjoyment value is 1 and the cost Omkar will have to pay is 0 per vehicle.

For the second query, a tour group of size 4 starting at city 1 can reach cities 1 and 2. Thus, their maximum enjoyment value is 2 and Omkar will pay 1 per vehicle.

For the third query, a tour group of size 3 starting at city 1 can reach cities 1, 2, and 3. Thus, their maximum enjoyment value is 3 and Omkar will pay 1 per vehicle.

For the fourth query, a tour group of size 2 starting at city 1 can reach cities 1, 2, 3 and 4. Thus, their maximum enjoyment value is 4 and Omkar will pay 1 per vehicle.

For the fifth query, a tour group of size 1 starting at city 1 can reach cities 1, 2, 3, 4, and 5. Thus, their maximum enjoyment value is 5 and Omkar will pay 1 per vehicle.

### Response

```cpp
#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:36777216")
using namespace std;
template <class T>
inline T &RD(T &);
template <class T>
inline void OT(const T &);
inline long long RD() {
  long long x;
  return RD(x);
}
inline double &RF(double &);
inline double RF() {
  double x;
  return RF(x);
}
inline char *RS(char *s);
inline char &RC(char &c);
inline char RC();
inline char &RC(char &c) {
  scanf(" %c", &c);
  return c;
}
inline char RC() {
  char c;
  return RC(c);
}
template <class T>
inline T &RDD(T &);
inline long long RDD() {
  long long x;
  return RDD(x);
}
template <class T0, class T1>
inline T0 &RD(T0 &x0, T1 &x1) {
  RD(x0), RD(x1);
  return x0;
}
template <class T0, class T1, class T2>
inline T0 &RD(T0 &x0, T1 &x1, T2 &x2) {
  RD(x0), RD(x1), RD(x2);
  return x0;
}
template <class T0, class T1, class T2, class T3>
inline T0 &RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3) {
  RD(x0), RD(x1), RD(x2), RD(x3);
  return x0;
}
template <class T0, class T1, class T2, class T3, class T4>
inline T0 &RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4) {
  RD(x0), RD(x1), RD(x2), RD(x3), RD(x4);
  return x0;
}
template <class T0, class T1, class T2, class T3, class T4, class T5>
inline T0 &RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5) {
  RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5);
  return x0;
}
template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
inline T0 &RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5, T6 &x6) {
  RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5), RD(x6);
  return x0;
}
template <class T0, class T1>
inline void OT(const T0 &x0, const T1 &x1) {
  OT(x0), OT(x1);
}
template <class T0, class T1, class T2>
inline void OT(const T0 &x0, const T1 &x1, const T2 &x2) {
  OT(x0), OT(x1), OT(x2);
}
template <class T0, class T1, class T2, class T3>
inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3) {
  OT(x0), OT(x1), OT(x2), OT(x3);
}
template <class T0, class T1, class T2, class T3, class T4>
inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3,
               const T4 &x4) {
  OT(x0), OT(x1), OT(x2), OT(x3), OT(x4);
}
template <class T0, class T1, class T2, class T3, class T4, class T5>
inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3,
               const T4 &x4, const T5 &x5) {
  OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5);
}
template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3,
               const T4 &x4, const T5 &x5, const T6 &x6) {
  OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5), OT(x6);
}
inline char &RC(char &a, char &b) {
  RC(a), RC(b);
  return a;
}
inline char &RC(char &a, char &b, char &c) {
  RC(a), RC(b), RC(c);
  return a;
}
inline char &RC(char &a, char &b, char &c, char &d) {
  RC(a), RC(b), RC(c), RC(d);
  return a;
}
inline char &RC(char &a, char &b, char &c, char &d, char &e) {
  RC(a), RC(b), RC(c), RC(d), RC(e);
  return a;
}
inline char &RC(char &a, char &b, char &c, char &d, char &e, char &f) {
  RC(a), RC(b), RC(c), RC(d), RC(e), RC(f);
  return a;
}
inline char &RC(char &a, char &b, char &c, char &d, char &e, char &f, char &g) {
  RC(a), RC(b), RC(c), RC(d), RC(e), RC(f), RC(g);
  return a;
}
inline double &RF(double &a, double &b) {
  RF(a), RF(b);
  return a;
}
inline double &RF(double &a, double &b, double &c) {
  RF(a), RF(b), RF(c);
  return a;
}
inline double &RF(double &a, double &b, double &c, double &d) {
  RF(a), RF(b), RF(c), RF(d);
  return a;
}
inline double &RF(double &a, double &b, double &c, double &d, double &e) {
  RF(a), RF(b), RF(c), RF(d), RF(e);
  return a;
}
inline double &RF(double &a, double &b, double &c, double &d, double &e,
                  double &f) {
  RF(a), RF(b), RF(c), RF(d), RF(e), RF(f);
  return a;
}
inline double &RF(double &a, double &b, double &c, double &d, double &e,
                  double &f, double &g) {
  RF(a), RF(b), RF(c), RF(d), RF(e), RF(f), RF(g);
  return a;
}
inline void RS(char *s1, char *s2) { RS(s1), RS(s2); }
inline void RS(char *s1, char *s2, char *s3) { RS(s1), RS(s2), RS(s3); }
template <class T0, class T1>
inline T0 &RDD(T0 &a, T1 &b) {
  RDD(a), RDD(b);
  return a;
}
template <class T0, class T1, class T2>
inline T1 &RDD(T0 &a, T1 &b, T2 &c) {
  RDD(a), RDD(b), RDD(c);
  return a;
}
template <class T>
inline void RST(T &A) {
  memset(A, 0, sizeof(A));
}
template <class T>
inline void FLC(T &A, int x) {
  memset(A, x, sizeof(A));
}
template <class T>
inline void CLR(T &A) {
  A.clear();
}
template <class T0, class T1>
inline void RST(T0 &A0, T1 &A1) {
  RST(A0), RST(A1);
}
template <class T0, class T1, class T2>
inline void RST(T0 &A0, T1 &A1, T2 &A2) {
  RST(A0), RST(A1), RST(A2);
}
template <class T0, class T1, class T2, class T3>
inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3) {
  RST(A0), RST(A1), RST(A2), RST(A3);
}
template <class T0, class T1, class T2, class T3, class T4>
inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4) {
  RST(A0), RST(A1), RST(A2), RST(A3), RST(A4);
}
template <class T0, class T1, class T2, class T3, class T4, class T5>
inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5) {
  RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5);
}
template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6) {
  RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5), RST(A6);
}
template <class T0, class T1>
inline void FLC(T0 &A0, T1 &A1, int x) {
  FLC(A0, x), FLC(A1, x);
}
template <class T0, class T1, class T2>
inline void FLC(T0 &A0, T1 &A1, T2 &A2, int x) {
  FLC(A0, x), FLC(A1, x), FLC(A2, x);
}
template <class T0, class T1, class T2, class T3>
inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, int x) {
  FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x);
}
template <class T0, class T1, class T2, class T3, class T4>
inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, int x) {
  FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x);
}
template <class T0, class T1, class T2, class T3, class T4, class T5>
inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, int x) {
  FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x), FLC(A5, x);
}
template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6, int x) {
  FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x), FLC(A5, x),
      FLC(A6, x);
}
template <class T>
inline void CLR(priority_queue<T> &Q) {
  while (!Q.empty()) Q.pop();
}
template <class T>
inline void CLR(stack<T> &S) {
  while (!S.empty()) S.pop();
}
template <class T>
inline void CLR(queue<T> &Q) {
  while (!Q.empty()) Q.pop();
}
template <class T0, class T1>
inline void CLR(T0 &A0, T1 &A1) {
  CLR(A0), CLR(A1);
}
template <class T0, class T1, class T2>
inline void CLR(T0 &A0, T1 &A1, T2 &A2) {
  CLR(A0), CLR(A1), CLR(A2);
}
template <class T0, class T1, class T2, class T3>
inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3) {
  CLR(A0), CLR(A1), CLR(A2), CLR(A3);
}
template <class T0, class T1, class T2, class T3, class T4>
inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4) {
  CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4);
}
template <class T0, class T1, class T2, class T3, class T4, class T5>
inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5) {
  CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5);
}
template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6) {
  CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5), CLR(A6);
}
template <class T>
inline void CLR(T &A, int n) {
  for (int i = 0; i < n; ++i) CLR(A[i]);
}
template <class T>
inline bool EPT(T &a) {
  return a.empty();
}
template <class T>
inline T &SRT(T &A) {
  sort(A.begin(), A.end());
  return A;
}
template <class T, class C>
inline T &SRT(T &A, C cmp) {
  sort(A.begin(), A.end(), cmp);
  return A;
}
template <class T>
inline T &RVS(T &A) {
  reverse(A.begin(), A.end());
  return A;
}
template <class T>
inline T &UNQQ(T &A) {
  A.resize(unique(A.begin(), A.end()) - A.begin());
  return A;
}
template <class T>
inline T &UNQ(T &A) {
  SRT(A);
  return UNQQ(A);
}
template <class T, class C>
inline T &UNQ(T &A, C cmp) {
  SRT(A, cmp);
  return UNQQ(A);
}
const int MOD = int(1e9) + 7;
const int INF = 0x3f3f3f3f;
const long long INFF = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;
const double OO = 1e20;
const double PI = acos(-1.0);
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, 1, -1};
template <class T>
inline bool checkMin(T &a, const T b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
inline bool checkMax(T &a, const T b) {
  return a < b ? a = b, 1 : 0;
}
template <class T, class C>
inline bool checkUpd(T &a, const T b, C c) {
  return c(b, a) ? a = b, 1 : 0;
}
template <class T>
inline T min(T a, T b, T c) {
  return min(min(a, b), c);
}
template <class T>
inline T max(T a, T b, T c) {
  return max(max(a, b), c);
}
template <class T>
inline T min(T a, T b, T c, T d) {
  return min(min(a, b), min(c, d));
}
template <class T>
inline T max(T a, T b, T c, T d) {
  return max(max(a, b), max(c, d));
}
template <class T>
inline T min(T a, T b, T c, T d, T e) {
  return min(min(min(a, b), min(c, d)), e);
}
template <class T>
inline T max(T a, T b, T c, T d, T e) {
  return max(max(max(a, b), max(c, d)), e);
}
template <class T>
inline T sqr(T a) {
  return a * a;
}
template <class T>
inline T cub(T a) {
  return a * a * a;
}
template <class T>
inline T ceil(T x, T y) {
  return (x - 1) / y + 1;
}
template <class T>
T abs(T x) {
  return x > 0 ? x : -x;
}
inline int sgn(double x) { return x < -EPS ? -1 : x > EPS; }
inline int sgn(double x, double y) { return sgn(x - y); }
inline double cos(double a, double b, double c) {
  return (sqr(a) + sqr(b) - sqr(c)) / (2 * a * b);
}
inline double cot(double x) { return 1. / tan(x); };
inline double sec(double x) { return 1. / cos(x); };
inline double csc(double x) { return 1. / sin(x); };
namespace CG {
inline double dist2(double x, double y) { return sqr(x) + sqr(y); }
struct Po {
  double x, y;
  Po(double x = 0, double y = 0) : x(x), y(y) {}
  void in() { RF(x, y); }
  void out() { printf("(%.2f,%.2f)", x, y); }
  inline friend istream &operator>>(istream &i, Po &p) {
    return i >> p.x >> p.y;
  }
  inline friend ostream &operator<<(ostream &o, Po p) {
    return o << "(" << p.x << ", " << p.y << ")";
  }
  Po operator-() const { return Po(-x, -y); }
  Po &operator+=(const Po &p) {
    x += p.x, y += p.y;
    return *this;
  }
  Po &operator-=(const Po &p) {
    x -= p.x, y -= p.y;
    return *this;
  }
  Po &operator*=(double k) {
    x *= k, y *= k;
    return *this;
  }
  Po &operator/=(double k) {
    x /= k, y /= k;
    return *this;
  }
  Po &operator*=(const Po &p) { return *this = *this * p; }
  Po &operator/=(const Po &p) { return *this = *this / p; }
  Po operator+(const Po &p) const { return Po(x + p.x, y + p.y); }
  Po operator-(const Po &p) const { return Po(x - p.x, y - p.y); }
  Po operator*(double k) const { return Po(x * k, y * k); }
  Po operator/(double k) const { return Po(x / k, y / k); }
  Po operator*(const Po &p) const {
    return Po(x * p.x - y * p.y, y * p.x + x * p.y);
  }
  Po operator/(const Po &p) const {
    return Po(x * p.x + y * p.y, y * p.x - x * p.y) / p.len2();
  }
  bool operator==(const Po &p) const { return !sgn(x, p.x) && !sgn(y, p.y); };
  bool operator!=(const Po &p) const { return sgn(x, p.x) || sgn(y, p.y); }
  bool operator<(const Po &p) const {
    return sgn(x, p.x) < 0 || !sgn(x, p.x) && sgn(y, p.y) < 0;
  }
  bool operator<=(const Po &p) const {
    return sgn(x, p.x) < 0 || !sgn(x, p.x) && sgn(y, p.y) <= 0;
  }
  bool operator>(const Po &p) const { return !(*this <= p); }
  bool operator>=(const Po &p) const { return !(*this < p); }
  double len2() const { return dist2(x, y); }
  double len() const { return sqrt(len2()); }
  double arg() const { return atan2(y, x); }
  Po &_1() { return *this /= len(); }
  Po &conj() {
    y = -y;
    return *this;
  }
  Po &lt() {
    swap(x, y), x = -x;
    return *this;
  }
  Po &rt() {
    swap(x, y), y = -y;
    return *this;
  }
  Po &rot(double a, const Po &o = Po()) {
    *this -= o;
    *this *= Po(cos(a), sin(a));
    return *this += o;
  }
  inline int q() const { return (y > 0 || y == 0 && x >= 0) ? 0 : 1; }
};
inline double dot(double x1, double y1, double x2, double y2) {
  return x1 * x2 + y1 * y2;
}
inline double dot(const Po &a, const Po &b) { return dot(a.x, a.y, b.x, b.y); }
inline double dot(const Po &p0, const Po &p1, const Po &p2) {
  return dot(p1 - p0, p2 - p0);
}
inline double det(double x1, double y1, double x2, double y2) {
  return x1 * y2 - x2 * y1;
}
inline double det(const Po &a, const Po &b) { return det(a.x, a.y, b.x, b.y); }
inline double det(const Po &p0, const Po &p1, const Po &p2) {
  return det(p1 - p0, p2 - p0);
}
inline double ang(const Po &p0, const Po &p1) {
  return acos(dot(p0, p1) / p0.len() / p1.len());
}
inline double ang(const Po &p0, const Po &p1, const Po &p2) {
  return ang(p1 - p0, p2 - p0);
}
inline double ang(const Po &p0, const Po &p1, const Po &p2, const Po &p3) {
  return ang(p1 - p0, p3 - p2);
}
inline double dist2(const Po &a, const Po &b) {
  return dist2(a.x - b.x, a.y - b.y);
}
template <class T1, class T2>
inline int dett(const T1 &x, const T2 &y) {
  return sgn(det(x, y));
}
template <class T1, class T2, class T3>
inline int dett(const T1 &x, const T2 &y, const T3 &z) {
  return sgn(det(x, y, z));
}
template <class T1, class T2, class T3, class T4>
inline int dett(const T1 &x, const T2 &y, const T3 &z, const T4 &w) {
  return sgn(det(x, y, z, w));
}
template <class T1, class T2>
inline int dott(const T1 &x, const T2 &y) {
  return sgn(dot(x, y));
}
template <class T1, class T2, class T3>
inline int dott(const T1 &x, const T2 &y, const T3 &z) {
  return sgn(dot(x, y, z));
}
template <class T1, class T2, class T3, class T4>
inline int dott(const T1 &x, const T2 &y, const T3 &z, const T4 &w) {
  return sgn(dot(x, y, z, w));
}
template <class T1, class T2>
inline double arg(const T1 &x, const T2 &y) {
  double a = ang(x, y);
  return ~dett(x, y) ? a : 2 * PI - a;
}
template <class T1, class T2, class T3>
inline double arg(const T1 &x, const T2 &y, const T3 &z) {
  double a = ang(x, y, z);
  return ~dett(x, y, z) ? a : 2 * PI - a;
}
template <class T1, class T2, class T3, class T4>
inline double arg(const T1 &x, const T2 &y, const T3 &z, const T4 &w) {
  double a = ang(x, y, z, w);
  return ~dett(x, y, z, w) ? a : 2 * PI - a;
}
template <class T1, class T2>
inline double dist(const T1 &x, const T2 &y) {
  return sqrt(dist2(x, y));
}
template <class T1, class T2, class T3>
inline double dist(const T1 &x, const T2 &y, const T3 &z) {
  return sqrt(dist2(x, y, z));
}
inline Po _1(Po p) { return p._1(); }
inline Po conj(Po p) { return p.conj(); }
inline Po lt(Po p) { return p.lt(); }
inline Po rt(Po p) { return p.rt(); }
inline Po rot(Po p, double a, const Po &o = Po()) { return p.rot(a, o); }
inline Po operator*(double k, const Po &p) { return p * k; }
inline Po operator/(double k, const Po &p) { return conj(p) * k / p.len2(); }
struct Line {
  Po a, b;
  Line(const Po &a = Po(), const Po &b = Po()) : a(a), b(b) {}
  Line(double x0, double y0, double x1, double y1)
      : a(Po(x0, y0)), b(Po(x1, y1)) {}
  Line(const Line &l) : a(l.a), b(l.b) {}
  Line(double A, double B, double C) {
    C = -C;
    if (!::sgn(A))
      a = Po(0, C / B), b = Po(1, C / B);
    else if (!::sgn(B))
      a = Po(C / A, 0), b = Po(C / A, 1);
    else
      a = Po(0, C / B), b = Po(1, (C - A) / B);
  }
  void in() { a.in(), b.in(); }
  inline friend istream &operator>>(istream &i, Line &p) {
    return i >> p.a >> p.b;
  }
  inline friend ostream &operator<<(ostream &o, Line p) {
    return o << p.a << "-" << p.b;
  }
  Line operator+(const Po &x) const { return Line(a + x, b + x); }
  Line operator-(const Po &x) const { return Line(a - x, b - x); }
  Line operator*(double k) const { return Line(a * k, b * k); }
  Line operator/(double k) const { return Line(a / k, b / k); }
  Po operator*(const Line &) const;
  Po d() const { return b - a; }
  double len2() const { return d().len2(); }
  double len() const { return d().len(); }
  double arg() const { return d().arg(); }
  int sgn(const Po &p) const { return dett(a, b, p); }
  int sgn(const Line &) const;
  bool sameSgn(const Po &p1, const Po &p2) const { return sgn(p1) == sgn(p2); }
  void getEquation(double &K, double &B) const {
    K = ::sgn(a.x, b.x) ? (b.y - a.y) / (b.x - a.x) : OO;
    B = a.y - K * a.x;
  }
  void getEquation(double &A, double &B, double &C) const {
    A = a.y - b.y, B = b.x - a.x, C = det(a, b);
  }
  Line &push(double r) {
    Po v = d()._1().lt() * r;
    a += v, b += v;
    return *this;
  }
};
inline double dot(const Line &l1, const Line &l2) {
  return dot(l1.d(), l2.d());
}
inline double dot(const Line &l, const Po &p) { return dot(l.a, l.b, p); }
inline double dot(const Po &p, const Line &l) { return dot(p, l.a, l.b); }
inline double det(const Line &l1, const Line &l2) {
  return det(l1.d(), l2.d());
}
inline double det(const Line &l, const Po &p) { return det(l.a, l.b, p); }
inline double det(const Po &p, const Line &l) { return det(p, l.a, l.b); }
inline double ang(const Line &l0, const Line &l1) {
  return ang(l0.d(), l1.d());
}
inline double ang(const Line &l, const Po &p) { return ang(l.a, l.b, p); }
inline double ang(const Po &p, const Line &l) { return ang(p, l.a, l.b); }
inline int Line::sgn(const Line &l) const { return dett(*this, l); }
inline Po Line::operator*(const Line &l) const {
  return a + d() * det(a, l) / det(*this, l);
}
inline Po operator&(const Po &p, const Line &l) {
  return l * Line(p, p + l.d().lt());
}
inline Po operator%(const Po &p, const Line &l) { return p & l * 2 - p; }
inline Line push(Line l, double r) { return l.push(r); }
struct Seg : public Line {
  Seg(const Po &a = Po(), const Po &b = Po()) : Line(a, b) {}
  Seg(double x0, double y0, double x1, double y1) : Line(x0, y0, x1, y1) {}
  Seg(const Line &l) : Line(l) {}
  Seg(const Po &a, double alpha) : Line(a, alpha) {}
  Seg(double A, double B, double C) : Line(A, B, C) {}
  inline int sgn(const Po &p) const;
  inline int sgn(const Line &l) const;
  inline bool qrt(const Seg &l) const;
  inline int sgn(const Seg &l) const;
};
inline int Seg::sgn(const Po &p) const {
  if (dett(p, a, b)) return -1;
  if (a == p || b == p) return 0;
  return -dott(p, a, b);
}
inline int Seg::sgn(const Line &l) const { return sgn(*this * l); }
inline bool Seg::qrt(const Seg &l) const {
  return min(a.x, b.x) <= max(l.a.x, l.b.x) &&
         min(l.a.x, l.b.x) <= max(a.x, b.x) &&
         min(a.y, b.y) <= max(l.a.y, l.b.y) &&
         min(l.a.y, l.b.y) <= max(a.y, b.y);
}
inline int Seg::sgn(const Seg &l) const {
  if (!qrt(l)) return -1;
  int d1 = dett(a, b, l.a), d2 = dett(a, b, l.b), d3 = dett(l.a, l.b, a),
      d4 = dett(l.a, l.b, b);
  if ((d1 ^ d2) == -2 && (d3 ^ d4) == -2) return 1;
  return ((!d1 && dott(l.a - a, l.a - b) <= 0) ||
          (!d2 && dott(l.b - a, l.b - b) <= 0) ||
          (!d3 && dott(a - l.a, a - l.b) <= 0) ||
          (!d4 && dott(b - l.a, b - l.b) <= 0))
             ? 0
             : -1;
}
inline double dist2(const Line &l, const Po &p) {
  return sqr(fabs(det(l.d(), p - l.a))) / l.len2();
}
inline double dist2(const Line &l1, const Line &l2) {
  return dett(l1, l2) ? 0 : dist2(l1, l2.a);
}
inline double dist2(const Seg &l, const Po &p) {
  Po pa = p - l.a, pb = p - l.b;
  if (dott(l.d(), pa) <= 0) return pa.len2();
  if (dott(l.d(), pb) >= 0) return pb.len2();
  return dist2(Line(l), p);
}
inline double dist2(const Seg &s, const Line &l) {
  Po v1 = s.a - l.a, v2 = s.b - l.a;
  double d1 = det(l.d(), v1), d2 = det(l.d(), v2);
  return sgn(d1) != sgn(d2) ? 0 : sqr(min(fabs(d1), fabs(d2))) / l.len2();
}
inline double dist2(const Seg &l1, const Seg &l2) {
  if (~l1.sgn(l2))
    return 0;
  else
    return min(dist2(l2, l1.a), dist2(l2, l1.b), dist2(l1, l2.a),
               dist2(l1, l2.b));
}
template <class T1, class T2>
inline double dist2(const T1 &a, const T2 &b) {
  return dist2(b, a);
}
}  // namespace CG
using namespace CG;
template <class T>
inline T &RD(T &x) {
  char c;
  while (!isdigit((c = getchar())))
    ;
  x = c - '0';
  while (isdigit((c = getchar()))) x = x * 10 + c - '0';
  return x;
}
template <class T>
inline T &RDD(T &x) {
  char c;
  while ((c = getchar()), c != '-' && !isdigit(c))
    ;
  if (c == '-') {
    x = '0' - (c = getchar());
    while (isdigit((c = getchar()))) x = x * 10 + '0' - c;
  } else {
    x = c - '0';
    while (isdigit((c = getchar()))) x = x * 10 + c - '0';
  }
  return x;
}
inline double &RF(double &x) {
  char c;
  while ((c = getchar()), c != '-' && c != '.' && !isdigit(c))
    ;
  if (c == '-')
    if ((c = getchar()) == '.') {
      x = 0;
      double l = 1;
      while (isdigit((c = getchar()))) l /= 10, x = x * 10 + '0' - c;
      x *= l;
    } else {
      x = '0' - c;
      while (isdigit((c = getchar()))) x = x * 10 + '0' - c;
      if (c == '.') {
        double l = 1;
        while (isdigit((c = getchar()))) l /= 10, x = x * 10 + '0' - c;
        x *= l;
      }
    }
  else if (c == '.') {
    x = 0;
    double l = 1;
    while (isdigit((c = getchar()))) l /= 10, x = x * 10 + c - '0';
    x *= l;
  } else {
    x = c - '0';
    while (isdigit((c = getchar()))) x = x * 10 + c - '0';
    if (c == '.') {
      double l = 1;
      while (isdigit((c = getchar()))) l /= 10, x = x * 10 + c - '0';
      x *= l;
    }
  }
  return x;
}
inline char *RS(char *s) {
  scanf("%s", s);
  return s;
}
int last_ans;
int Case;
template <class T>
inline void OT(const T &x) {
  printf("%d\n", x);
}
const int N = int(2e5) + 9;
vector<pair<int, int> > adj[N];
int e[N];
int n;
const int LV = 21;
int fa[LV][N], mx[LV][N], dep[N];
inline int move_up(int x, int t) {
  for (int lv = 0; t; ++lv, t >>= 1)
    if (t & 1) x = fa[lv][x];
  return x;
}
inline int mx_edge_up(int x, int t) {
  int z = 0;
  for (int lv = 0; t; ++lv, t >>= 1)
    if (t & 1) checkMax(z, mx[lv][x]), x = fa[lv][x];
  return z;
}
inline int lca(int x, int y) {
  if (dep[y] < dep[x]) swap(x, y);
  y = move_up(y, dep[y] - dep[x]);
  if (x == y) return x;
  for (int lv = LV - 1; lv >= 0; --lv)
    if (fa[lv][x] != fa[lv][y]) x = fa[lv][x], y = fa[lv][y];
  return fa[0][x];
}
void dfs(int u) {
  for (auto e : adj[u]) {
    int v = e.first, w = e.second;
    if (v != fa[0][u]) {
      fa[0][v] = u;
      mx[0][v] = w;
      dep[v] = dep[u] + 1;
      for (int lv = 0; mx[lv + 1][v] = max(mx[lv][v], mx[lv][fa[lv][v]]),
               fa[lv + 1][v] = fa[lv][fa[lv][v]];
           ++lv)
        ;
      dfs(v);
    }
  }
}
int maxEdge(int x, int y) {
  int z = lca(x, y);
  return max(mx_edge_up(x, dep[x] - dep[z]), mx_edge_up(y, dep[y] - dep[z]));
}
namespace DSU {
int P[N], R[N], eid[N], t[N];
inline void Make(int x) { P[x] = x, R[x] = 0, eid[x] = x, t[x] = 0; }
inline int Find(int x) { return P[x] == x ? x : P[x] = Find(P[x]); }
inline void Unionn(int x, int y) {
  if (R[x] == R[y])
    ++R[x];
  else if (R[x] < R[y])
    swap(x, y);
  P[y] = x;
  if (e[eid[x]] == e[eid[y]]) {
    checkMax(t[x], max(t[y], maxEdge(eid[x], eid[y])));
  } else {
    if (e[eid[y]] > e[eid[x]]) {
      eid[x] = eid[y];
      t[x] = t[y];
    }
  }
}
inline void Union(int x, int y) { x = Find(x), y = Find(y), Unionn(x, y); }
inline void Init() {
  for (int i = 0; i < n; ++i) Make(i);
}
}  // namespace DSU
using namespace DSU;
struct Edge {
  int a, b, c, t;
  void in() {
    RD(a, b, c, t);
    --a, --b;
    adj[a].push_back({b, t});
    adj[b].push_back({a, t});
  }
  void add() { Union(a, b); }
} E[N];
struct Query {
  int v, x, id, z1, z2;
  void in() {
    RD(v, x);
    --x;
  }
  void gao() {
    int y = eid[Find(x)];
    z1 = e[y];
    z2 = max(t[Find(x)], maxEdge(x, y));
  }
  void out() { printf("%d %d\n", z1, z2); }
} Q[N];
int main() {
  int q;
  RD(n, q);
  for (int i = 0; i < n; ++i) RD(e[i]);
  for (int i = 0; i < n - 1; ++i) E[i].in();
  for (int i = 0; i < q; ++i) Q[i].in(), Q[i].id = i;
  Init();
  dfs(0);
  sort(E, E + n - 1, [&](const Edge a, const Edge b) { return a.c > b.c; });
  sort(Q, Q + q, [&](const Query a, const Query b) { return a.v > b.v; });
  int Ei = 0;
  for (int i = 0; i < q; ++i) {
    while (Ei < n - 1 && E[Ei].c >= Q[i].v) E[Ei++].add();
    Q[i].gao();
  }
  sort(Q, Q + q, [&](const Query a, const Query b) { return a.id < b.id; });
  for (int i = 0; i < q; ++i) Q[i].out();
}

```