Problem: Vasya has an array a_1, a_2, ..., a_n.

You don't know this array, but he told you m facts about this array. The i-th fact is a triple of numbers t_i, l_i and r_i (0 ≤ t_i ≤ 1, 1 ≤ l_i < r_i ≤ n) and it means:

  * if t_i=1 then subbarray a_{l_i}, a_{l_i + 1}, ..., a_{r_i} is sorted in non-decreasing order; 
  * if t_i=0 then subbarray a_{l_i}, a_{l_i + 1}, ..., a_{r_i} is not sorted in non-decreasing order. A subarray is not sorted if there is at least one pair of consecutive elements in this subarray such that the former is greater than the latter. 



For example if a = [2, 1, 1, 3, 2] then he could give you three facts: t_1=1, l_1=2, r_1=4 (the subarray [a_2, a_3, a_4] = [1, 1, 3] is sorted), t_2=0, l_2=4, r_2=5 (the subarray [a_4, a_5] = [3, 2] is not sorted), and t_3=0, l_3=3, r_3=5 (the subarray [a_3, a_5] = [1, 3, 2] is not sorted).

You don't know the array a. Find any array which satisfies all the given facts.

Input

The first line contains two integers n and m (2 ≤ n ≤ 1000, 1 ≤ m ≤ 1000).

Each of the next m lines contains three integers t_i, l_i and r_i (0 ≤ t_i ≤ 1, 1 ≤ l_i < r_i ≤ n).

If t_i = 1 then subbarray a_{l_i}, a_{l_i + 1}, ... , a_{r_i} is sorted. Otherwise (if t_i = 0) subbarray a_{l_i}, a_{l_i + 1}, ... , a_{r_i} is not sorted.

Output

If there is no array that satisfies these facts in only line print NO (in any letter case).

If there is a solution, print YES (in any letter case). In second line print n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^9) — the array a, satisfying all the given facts. If there are multiple satisfying arrays you can print any of them.

Examples

Input


7 4
1 1 3
1 2 5
0 5 6
1 6 7


Output


YES
1 2 2 3 5 4 4


Input


4 2
1 1 4
0 2 3


Output


NO

Solution (in JAVA):

Solution:
import java.math.*;
import java.util.*;
import java.io.*;
public class Main {
    void solve(){
        int n=ni(),m=ni();
        int a[]=new int[n+1];

       int t[]=new int[m+1];
       int l[]=new int[m+1];
       int r[]=new int[m+1];
       for(int i=1;i<=m;i++){
           t[i]=ni(); l[i]=ni(); r[i]=ni();
           if(t[i]==1){
               for(int j=l[i]+1;j<=r[i];j++) a[j]=1;

           }
       }
     out :  for(int i=1;i<=m;i++){
           if(t[i]==1) continue;
           for(int j=l[i]+1;j<=r[i];j++){
               if(a[j]==0){
                   a[j]=-1;
                   continue out;
               }else if(a[j]==-1) continue out;
           }
           pw.println("NO");
           return;
       }
         int b[]=new int[n+1];
       Arrays.fill(b,10000000);
       for(int i=2;i<=n;i++){
           if(a[i]==-1){
               b[i]=b[i-1]-1;
           }else if(a[i]==1){
               b[i]=Math.max(b[i-1],b[i]);
           }
       }



        pw.println("YES");
        for(int i=1;i<=n;i++){

            pw.print(b[i]+" ");
        }
        pw.println("");


   }
   boolean check(int freq1[],int freq2[]){
        for(int i=-0;i<26;i++){
            if(freq1[i]<freq2[i]) return false;
        }
        return true;
   }


   long add(long a,long b){
      a+=b;
      if(a>=M) a-=M;
      return a;
   }
   long mul(long a,long b){
      a*=b;
      if(a>=M) a%=M;
      return a;
   }
   long sub(long a,long b){
      a-=b;
      if(a<0) a+=M;
      return a;
   }
 long modpow(long x, long y, long M){

      long res = 1;

      x = x % M;

      while (y > 0)
      {

         if((y & 1)==1)
            res = (res * x) % M;

         y = y >> 1;
         x = (x * x) % M;
      }
      return res;
   }
   long modInverse(long A,long M){
      return modpow(A,M-2,M);
   }


   long M =(long)1e9+7;


   InputStream is;
   PrintWriter pw;
   String INPUT = "";

   void run() throws Exception {
      is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
      pw = new PrintWriter(System.out);
      long s = System.currentTimeMillis();
      solve();
      pw.flush();
      if (!INPUT.isEmpty()) tr(System.currentTimeMillis() - s + "ms");


   }

   public static void main(String[] args) throws Exception {
      new Main().run();
   }

   private byte[] inbuf = new byte[1024];
   public int lenbuf = 0, ptrbuf = 0;

   private int readByte() {
      if (lenbuf == -1) throw new InputMismatchException();
      if (ptrbuf >= lenbuf) {
         ptrbuf = 0;
         try {
            lenbuf = is.read(inbuf);
         } catch (IOException e) {
            throw new InputMismatchException();
         }
         if (lenbuf <= 0) return -1;
      }
      return inbuf[ptrbuf++];
   }

   private boolean isSpaceChar(int c) {
      return !(c >= 33 && c <= 126);
   }

   private int skip() {
      int b;
      while ((b = readByte()) != -1 && isSpaceChar(b)) ;
      return b;
   }

   private double nd() {
      return Double.parseDouble(ns());
   }

   private char nc() {
      return (char) skip();
   }

   private String ns() {
      int b = skip();
      StringBuilder sb = new StringBuilder();
      while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != ' ')
         sb.appendCodePoint(b);
         b = readByte();
      }
      return sb.toString();
   }

   private char[] ns(int n) {
      char[] buf = new char[n];
      int b = skip(), p = 0;
      while (p < n && !(isSpaceChar(b))) {
         buf[p++] = (char) b;
         b = readByte();
      }
      return n == p ? buf : Arrays.copyOf(buf, p);
   }

   private char[][] nm(int n, int m) {
      char[][] map = new char[n][];
      for (int i = 0; i < n; i++) map[i] = ns(m);
      return map;
   }

   private int[] na(int n) {
      int[] a = new int[n];
      for (int i = 0; i < n; i++) a[i] = ni();
      return a;
   }

   private int ni() {
      int num = 0, b;
      boolean minus = false;
      while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
      if (b == '-') {
         minus = true;
         b = readByte();
      }

      while (true) {
         if (b >= '0' && b <= '9') {
            num = num * 10 + (b - '0');
         } else {
            return minus ? -num : num;
         }
         b = readByte();
      }
   }

   private long nl() {
      long num = 0;
      int b;
      boolean minus = false;
      while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
      if (b == '-') {
         minus = true;
         b = readByte();
      }

      while (true) {
         if (b >= '0' && b <= '9') {
            num = num * 10 + (b - '0');
         } else {
            return minus ? -num : num;
         }
         b = readByte();
      }
   }

   private boolean oj = System.getProperty("ONLINE_JUDGE") != null;

   private void tr(Object... o) {
      if (INPUT.length() > 0) System.out.println(Arrays.deepToString(o));
   }

}