Problem: Help! A robot escaped our lab and we need help finding it. 

The lab is at the point (0, 0) of the coordinate plane, at time 0 the robot was there. The robot's movements are defined by a program — a string of length l, consisting of characters U, L, D, R. Each second the robot executes the next command in his program: if the current coordinates of the robot are (x, y), then commands U, L, D, R move it to cells (x, y + 1), (x - 1, y), (x, y - 1), (x + 1, y) respectively. The execution of the program started at time 0. The program is looped, i.e. each l seconds of executing the program start again from the first character. Unfortunately, we don't know what program was loaded into the robot when he left the lab.

Our radars managed to find out the position of the robot at n moments of time: we know that at the moment of time ti the robot is at the point (xi, yi). Given this data, either help to determine what program could be loaded into the robot, or determine that no possible program meets the data and the robot must have broken down.

Input

The first line of the input contains two space-separated integers n and l (1 ≤ n ≤ 2·105, 1 ≤ l ≤ 2·106).

Next n lines contain three space-separated integers — ti, xi, yi (1 ≤ ti ≤ 1018,  - 1018 ≤ xi, yi ≤ 1018). The radar data is given chronologically, i.e. ti < ti + 1 for all i from 1 to n - 1.

Output

Print any of the possible programs that meet the data. If no program meets the data, print a single word 'NO' (without the quotes).

Examples

Input

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


Output

RDL


Input

2 2
1 1 0
999 1 0


Output

RL


Input

2 5
10 10 0
20 0 0


Output

NO

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
#pragma GCC optimize("unroll-all-loops")
using namespace std;
template <typename Type>
void Get_Val(Type &Ret) {
  Ret = 0;
  char ch;
  bool Neg(false);
  while (ch = getchar(), (ch > '9' || ch < '0') && ch != '-')
    ;
  if (ch == '-') {
    Neg = true;
    while (ch = getchar(), ch > '9' || ch < '0')
      ;
  }
  do {
    (Ret *= 10) += ch - '0';
  } while (ch = getchar(), ch >= '0' && ch <= '9');
  Ret = (Neg ? -Ret : Ret);
}
const int Max_N(200050);
const int Max_L(2000050);
inline long long int Abs(const long long int &x) { return x >= 0LL ? x : -x; }
struct fun {
  fun(const long long int &_k = 0LL, const long long int &_b = 0LL)
      : k(_k), b(_b) {}
  long long int k, b;
  inline bool jie(const long long int &a, long long int &x) const {
    return (Abs(a - b) % Abs(k) == 0LL) ? ((x = (a - b) / k), true) : false;
  }
  inline long long int js(const long long int &x) const { return k * x + b; }
};
inline fun operator-(const fun &a, const fun &b) {
  return fun(a.k - b.k, a.b - b.b);
}
inline bool comp(const fun &a, const fun &b) {
  return (a.k == b.k) ? (a.b < b.b) : (a.k < b.k);
}
int N, L;
long long int T[Max_N], X[Max_N], Y[Max_N], A[Max_L], B[Max_L];
void init() {
  Get_Val(N), Get_Val(L);
  long long int Xi, Yi;
  for (int i = 1; i <= N; ++i) {
    Get_Val(T[i]), Get_Val(Xi), Get_Val(Yi);
    X[i] = Xi - Yi, Y[i] = Xi + Yi;
  }
}
vector<fun> V[Max_L];
bool done[Max_L];
bool check(long long int *P) {
  done[L] = true;
  for (int i = 0; i <= L - 1; ++i) {
    if (V[i].size())
      done[i] = true, P[i] = V[i][0].js(P[L]);
    else
      done[i] = false;
    for (int j = 1; j < V[i].size(); ++j)
      if (V[i][j].js(P[L]) != P[i]) return false;
  }
  for (int i = 1, j = 0; i <= L; ++i)
    if (done[i]) {
      if (P[i] - P[j] > i - j) return false;
      if (P[i] - P[j] < -(i - j)) return false;
      if ((Abs(P[i] - P[j]) & 1LL) != ((i - j) & 1)) return false;
      for (int x = j; x <= i; ++x)
        if ((x - j) - (i - x) == P[i] - P[j]) {
          for (int k = j + 1; k <= x; ++k) P[k] = P[k - 1] + 1LL;
          for (int k = x + 1; k <= i; ++k) P[k] = P[k - 1] - 1LL;
          break;
        }
      j = i;
    }
  for (int i = L; i >= 1; --i) P[i] -= P[i - 1];
  return true;
}
void wxh(const long long int &, const long long int &);
void wzd(const long long int &, const long long int &);
long long int Min, Max;
inline void wxh(const long long int &a, const long long int &b) {
  if (a == 0LL) {
    if (0LL > b) {
      printf("NO");
      exit(0);
    }
    return;
  }
  if (a > 0LL) {
    for (Max = min(Max, b / a + 1LL);; --Max)
      if (a * Max <= b) break;
  } else
    wzd(-a, -b);
}
inline void wzd(const long long int &a, const long long int &b) {
  if (a == 0LL) {
    if (0LL < b) {
      printf("NO");
      exit(0);
    }
    return;
  }
  if (a > 0LL) {
    for (Min = max(Min, b / a - 1LL);; ++Min)
      if (a * Min >= b) break;
  } else
    wxh(-a, -b);
}
void work(long long int *A, long long int *P) {
  for (int i = 0; i <= L; ++i) V[i].clear();
  V[0].push_back(fun(0LL, 0LL));
  V[L].push_back(fun(1LL, 0LL));
  for (int i = 1; i <= N; ++i) V[T[i] % L].push_back(fun(-(T[i] / L), A[i]));
  for (int i = 0; i <= L - 1; ++i) {
    sort(V[i].begin(), V[i].end(), comp);
    for (int j = 1; j < V[i].size(); ++j)
      if (V[i][j - 1].k == V[i][j].k) {
        if (V[i][j - 1].b != V[i][j].b) {
          printf("NO");
          exit(0);
        }
      } else {
        if ((V[i][j] - V[i][j - 1]).jie(0LL, P[L]) == false) {
          printf("NO");
          exit(0);
        }
        if (check(P) == false) {
          printf("NO");
          exit(0);
        } else
          return;
      }
  }
  for (int i = 0; i <= L; ++i)
    if (V[i].size())
      done[i] = true;
    else
      done[i] = false;
  Min = -L, Max = +L;
  fun s;
  for (int i = 1, j = 0, l; i <= L; ++i)
    if (done[i]) {
      s = V[i][0] - V[j][0], l = i - j;
      wxh(s.k, +l - s.b);
      wzd(s.k, -l - s.b);
      j = i;
    }
  int Cnt(0);
  for (P[L] = Min; P[L] <= Max && Cnt <= 2; ++P[L], ++Cnt)
    if (check(P)) return;
  printf("NO");
  exit(0);
}
void work() {
  work(X, A);
  work(Y, B);
  long long int Xi, Yi;
  for (int i = 1; i <= L; ++i) {
    Xi = (A[i] + B[i]) / 2LL;
    Yi = (B[i] - A[i]) / 2LL;
    if (Xi == +1LL) printf("R");
    if (Xi == -1LL) printf("L");
    if (Yi == +1LL) printf("U");
    if (Yi == -1LL) printf("D");
  }
}
int main() {
  init();
  work();
  return 0;
}