#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <unordered_set>
using namespace std;
#if __has_include(<atcoder/all>)
#include <atcoder/all>
namespace atcoder {
ostream& operator<<(ostream& os, modint x) { return os << x.val(); }
template <int N>
ostream& operator<<(ostream& os, static_modint<N> x) {
    return os << x.val();
}
istream& operator>>(istream& is, modint x) {
    long long a;
    is >> a;
    x = a;
    return is;
}
template <int N>
istream& operator>>(istream& is, static_modint<N> x) {
    long long a;
    is >> a;
    x = a;
    return is;
}
}  // namespace atcoder
#endif
#define GET_MACRO(_1, _2, _3, NAME, ...) NAME
#define _rep(i, n) _rep2(i, 0, n)
#define _rep2(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(...) GET_MACRO(__VA_ARGS__, _rep2, _rep)(__VA_ARGS__)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define UNIQUE(x)                      \
    std::sort((x).begin(), (x).end()); \
    (x).erase(std::unique((x).begin(), (x).end()), (x).end())
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned int;
using i32 = int;
using ld = long double;
using f64 = double;
template <class T, class U>
bool chmin(T& a, const U& b) {
    return (b < a) ? (a = b, true) : false;
}
template <class T, class U>
bool chmax(T& a, const U& b) {
    return (b > a) ? (a = b, true) : false;
}
template <class T = std::string, class U = std::string>
inline void YesNo(bool f = 0, const T yes = "Yes", const U no = "No") {
    if (f)
        std::cout << yes << "\n";
    else
        std::cout << no << "\n";
}
namespace io {

template <class T, class U>
istream& operator>>(istream& i, pair<T, U>& p) {
    i >> p.first >> p.second;
    return i;
}

template <class T, class U>
ostream& operator<<(ostream& o, pair<T, U>& p) {
    o << p.first << " " << p.second;
    return o;
}

template <typename T>
istream& operator>>(istream& i, vector<T>& v) {
    rep(j, v.size()) i >> v[j];
    return i;
}
template <typename T>
string join(vector<T>& v) {
    stringstream s;
    rep(i, v.size()) s << ' ' << v[i];
    return s.str().substr(1);
}
template <typename T>
ostream& operator<<(ostream& o, vector<T>& v) {
    if (v.size()) o << join(v);
    return o;
}
template <typename T>
string join(vector<vector<T>>& vv) {
    string s = "\n";
    rep(i, vv.size()) s += join(vv[i]) + "\n";
    return s;
}
template <typename T>
ostream& operator<<(ostream& o, vector<vector<T>>& vv) {
    if (vv.size()) o << join(vv);
    return o;
}

void OUT() { std::cout << "\n"; }

template <class Head, class... Tail>
void OUT(Head&& head, Tail&&... tail) {
    std::cout << head;
    if (sizeof...(tail)) std::cout << ' ';
    OUT(std::forward<Tail>(tail)...);
}

void OUTL() { std::cout << std::endl; }

template <class Head, class... Tail>
void OUTL(Head&& head, Tail&&... tail) {
    std::cout << head;
    if (sizeof...(tail)) std::cout << ' ';
    OUTL(std::forward<Tail>(tail)...);
}

void IN() {}

template <class Head, class... Tail>
void IN(Head&& head, Tail&&... tail) {
    cin >> head;
    IN(std::forward<Tail>(tail)...);
}

}  // namespace io
using namespace io;

namespace useful {
long long modpow(long long a, long long b, long long mod) {
    long long res = 1;
    while (b) {
        if (b & 1) res *= a, res %= mod;
        a *= a;
        a %= mod;
        b >>= 1;
    }
    return res;
}

bool is_pow2(long long x) { return x > 0 && (x & (x - 1)) == 0; }

template <class T>
void rearrange(vector<T>& a, vector<int>& p) {
    vector<T> b = a;
    for (int i = 0; i < int(a.size()); i++) {
        a[i] = b[p[i]];
    }
    return;
}

template <std::forward_iterator I>
std::vector<std::pair<typename std::iterator_traits<I>::value_type, int>>
run_length_encoding(I s, I t) {
    if (s == t) return {};
    std::vector<std::pair<typename std::iterator_traits<I>::value_type, int>>
        res;
    res.emplace_back(*s, 1);
    for (auto it = ++s; it != t; it++) {
        if (*it == res.back().first)
            res.back().second++;
        else
            res.emplace_back(*it, 1);
    }
    return res;
}

vector<int> linear_sieve(int n) {
    vector<int> primes;
    vector<int> res(n + 1);
    iota(all(res), 0);
    for (int i = 2; i <= n; i++) {
        if (res[i] == i) primes.emplace_back(i);
        for (auto j : primes) {
            if (j * i > n) break;
            res[j * i] = j;
        }
    }
    return res;
    // return primes;
}

template <class T>
vector<long long> dijkstra(vector<vector<pair<int, T>>>& graph, int start) {
    int n = graph.size();
    vector<long long> res(n, 2e18);
    res[start] = 0;
    priority_queue<pair<long long, int>, vector<pair<long long, int>>,
                   greater<pair<long long, int>>>
        que;
    que.push({0, start});
    while (!que.empty()) {
        auto [c, v] = que.top();
        que.pop();
        if (res[v] < c) continue;
        for (auto [nxt, cost] : graph[v]) {
            auto x = c + cost;
            if (x < res[nxt]) {
                res[nxt] = x;
                que.push({x, nxt});
            }
        }
    }
    return res;
}

}  // namespace useful
using namespace useful;

template <class T, T l, T r>
struct RandomIntGenerator {
    std::random_device seed;
    std::mt19937_64 engine;
    std::uniform_int_distribution<T> uid;

    RandomIntGenerator() {
        engine = std::mt19937_64(seed());
        uid = std::uniform_int_distribution<T>(l, r);
    }

    T gen() { return uid(engine); }
};

// http://judge.yosupo.jp/submission/247593

#define PROBLEM "https://judge.yosupo.jp/problem/static_range_lis_query"
#include <algorithm>
#include <utility>
#include <vector>

namespace nachia {

int Popcount(unsigned long long c) noexcept {
#ifdef __GNUC__
    return __builtin_popcountll(c);
#else
    c = (c & (~0ull / 3)) + ((c >> 1) & (~0ull / 3));
    c = (c & (~0ull / 5)) + ((c >> 2) & (~0ull / 5));
    c = (c & (~0ull / 17)) + ((c >> 4) & (~0ull / 17));
    c = (c * (~0ull / 257)) >> 56;
    return c;
#endif
}

// please ensure x != 0
int MsbIndex(unsigned long long x) noexcept {
#ifdef __GNUC__
    return 63 - __builtin_clzll(x);
#else
    using u64 = unsigned long long;
    int q = (x >> 32) ? 32 : 0;
    auto m = x >> q;
    constexpr u64 hi = 0x8888'8888;
    constexpr u64 mi = 0x1111'1111;
    m = (((m | ~(hi - (m & ~hi))) & hi) * mi) >> 35;
    m = (((m | ~(hi - (x & ~hi))) & hi) * mi) >> 31;
    q += (m & 0xf) << 2;
    q += 0x3333'3333'2222'1100 >> (((x >> q) & 0xf) << 2) & 0xf;
    return q;
#endif
}

// please ensure x != 0
int LsbIndex(unsigned long long x) noexcept {
#ifdef __GNUC__
    return __builtin_ctzll(x);
#else
    return MsbIndex(x & -x);
#endif
}

}  // namespace nachia

namespace nachia {

struct WaveletMatrix {
    using u64 = unsigned long long;
    struct WordBlock {
        u64 table;
        int ptr;
    };
    int n;
    int S;
    int logS;
    std::vector<std::vector<WordBlock>> Table;

    WaveletMatrix() {}

    WaveletMatrix(int maxVal, std::vector<int> A) {
        S = 1;
        logS = 0;
        n = A.size();
        while (S <= maxVal) {
            S *= 2;
            logS += 1;
        }
        Table.resize(logS);
        for (int d = logS - 1; d >= 0; d--) {
            std::vector<WordBlock> tableBuf(n / 64 + 2, {0, 0});
            for (int i = 0; i < n; i++)
                tableBuf[i / 64].table |= (u64)((A[i] >> d) & 1) << (i % 64);
            for (int i = 1; i <= n / 64 + 1; i++)
                tableBuf[i].ptr =
                    tableBuf[i - 1].ptr + Popcount(tableBuf[i - 1].table);
            std::vector<int> buf;
            for (int b : {0, 1 << d})
                for (int a : A)
                    if ((a & (1 << d)) == b) buf.push_back(a);
            std::swap(Table[d], tableBuf);
            std::swap(A, buf);
        }
    }
    int getLevelRank(int level, int p) const {
        int res = Table[level][p / 64].ptr +
                  Popcount(Table[level][p / 64].table & ~(~(u64)0 << (p % 64)));
        return res;
    }
    int getLeftPointer(int level, int p) const {
        return p - getLevelRank(level, p);
    }
    int getRightPointer(int level, int p) const {
        return n - Table[level].back().ptr + getLevelRank(level, p);
    }
    int get(int p) const {
        int res = 0;
        for (int d = logS - 1; d >= 0; d--) {
            res *= 2;
            if (Table[d][p / 64].table & ((u64)1 << (p % 64))) {
                res |= 1;
                p = getRightPointer(d, p);
            } else {
                p = getLeftPointer(d, p);
            }
        }
        return res;
    }
    int count(int l, int r, int val) const {
        for (int d = logS - 1; d >= 0; d--) {
            if (val & (1 << d)) {
                l = getRightPointer(d, l);
                r = getRightPointer(d, r);
            } else {
                l = getLeftPointer(d, l);
                r = getLeftPointer(d, r);
            }
        }
        return r - l;
    }
    int countRange(int l, int r, int rval) const {
        if (rval == 0) return 0;
        int ans = 0;
        for (int d = logS - 1; d >= 0; d--) {
            if (rval & (1 << d)) {
                ans += getLeftPointer(d, r) - getLeftPointer(d, l);
                l = getRightPointer(d, l);
                r = getRightPointer(d, r);
            } else {
                l = getLeftPointer(d, l);
                r = getLeftPointer(d, r);
            }
        }
        return ans;
    }
    int count(int l, int r, int lval, int rval) const {
        return countRange(l, r, rval) - countRange(l, r, lval);
    }
    int getKthSmallest(int l, int r, int k) const {
        int res = 0;
        for (int d = logS - 1; d >= 0; d--) {
            res *= 2;
            int zerocnt = r - l;
            zerocnt -= getLevelRank(d, r);
            zerocnt += getLevelRank(d, l);
            if (k < zerocnt) {
                l = getLeftPointer(d, l);
                r = getLeftPointer(d, r);
            } else {
                res += 1;
                k -= zerocnt;
                l = getRightPointer(d, l);
                r = getRightPointer(d, r);
            }
        }
        return res;
    }
};

}  // namespace nachia

namespace nachia {

struct RangeLis {
   private:
    int n;
    WaveletMatrix ds;
    using VectorIter = std::vector<int>::iterator;
    struct Split {
        std::vector<int> I;
        std::vector<int> valL;
        std::vector<int> valR;
    };
    static Split SplitIndex(VectorIter A, int n, int m) {
        Split res;
        res.I.resize(n);
        res.valL.resize(m);
        res.valR.resize(n - m);
        for (int i = 0; i < m; i++) res.I[A[i]] += 1;
        for (int i = 0; i < n - 1; i++) res.I[i + 1] += res.I[i];
        for (int i = 0; i < m; i++) {
            int a = A[i];
            A[i] = res.I[a] - 1;
            res.valL[A[i]] = a;
        }
        for (int i = m; i < n; i++) {
            int a = A[i];
            A[i] = a - res.I[a];
            res.valR[A[i]] = a;
        }
        return res;
    }
    static std::vector<int> CertainOperator(int n, VectorIter a, VectorIter b) {
        if (n == 1) return {0};
        int m = n / 2;
        auto [AI, AvalL, AvalR] = SplitIndex(a, n, m);
        auto [BI, BvalL, BvalR] = SplitIndex(b, n, m);
        auto resL = CertainOperator(m, a, b);
        auto resR = CertainOperator(n - m, a + m, b + m);

        std::vector<int> depV(n);
        std::vector<int> depH(n);
        for (int i = 0; i < m; i++) {
            depH[AvalL[i]] = BvalL[resL[i]];
            depV[BvalL[resL[i]]] = AvalL[i];
        }
        for (int i = 0; i < n - m; i++) {
            depH[AvalR[i]] = BvalR[resR[i]] - (n + 1) + 1;
            depV[BvalR[resR[i]]] = AvalR[i] - (n + 1) + 1;
        }
        std::vector<int> res(n, -1);
        int xi = n;
        for (int yi = 0; yi <= n; yi++) {
            while (0 < xi) {
                if (depV[xi - 1] <= yi - (n + 1) || yi <= depV[xi - 1]) break;
                xi--;
                if (0 <= depV[xi] && depV[xi] <= yi) {
                    res[depV[xi]] = xi;
                }
            }
            if (yi != n) {
                if (depH[yi] <= xi - (n + 1) || xi <= depH[yi]) {
                    xi--;
                    res[yi] = xi;
                } else {
                    if (depH[yi] < 0 && xi - (n + 1) <= depH[yi]) {
                        res[yi] = depH[yi] + (n + 1) - 1;
                    }
                }
            }
        }
        return res;
    }

   public:
    static std::vector<int> MakeTableIn(VectorIter A, int n) {
        if (n == 1) return {0, 1};
        int m = n / 2;
        auto [I, valL, valR] = SplitIndex(A, n, m);
        std::vector<int> res(n * 2, -1);
        std::vector<int> mapL(n);
        std::vector<int> opL(n);
        {
            auto BL = MakeTableIn(A, m);
            int j = 0;
            int k = 0;
            for (int i = 0; i < m * 2; i++) {
                int src = i < m ? n - m + i : n + valL[i - m];
                while (k < n - m && valR[k] < src - n) {
                    mapL[j] = n + valR[k];
                    opL[j++] = valR[k++];
                }
                if (BL[i] < m) {
                    mapL[j] = src;
                    opL[j++] = valL[BL[i]];
                } else {
                    res[src] = (n - m) * 2 + BL[i];
                }
            }
            while (k < n - m) {
                mapL[j] = n + valR[k];
                opL[j++] = valR[k++];
            }
        }
        std::vector<int> mapR(n);
        std::vector<int> opR(n);
        {
            auto BR = MakeTableIn(A + m, n - m);
            std::vector<int> mapinv(n + n - m, 1);
            for (int i = 0; i < n - m; i++) {
                int dest = (BR[i] < n - m) ? valR[BR[i]] : (m + BR[i]);
                res[i] = dest;
                mapinv[dest] = 0;
            }
            mapinv[0] -= 1;
            for (int i = 1; i < n + n - m; i++) mapinv[i] += mapinv[i - 1];
            for (int i = n - m; i < (n - m) * 2; i++) {
                int dest = (BR[i] < n - m) ? valR[BR[i]] : (m + BR[i]);
                opR[valR[i - (n - m)]] = mapinv[dest];
                mapR[mapinv[dest]] = dest;
            }
            for (int i = 0; i < m; i++) {
                int dest = mapinv[valL[i]];
                opR[valL[i]] = dest;
                mapR[dest] = valL[i];
            }
        }
        std::vector<int> opLInv(n);
        for (int i = 0; i < n; i++) opLInv[opL[i]] = i;
        auto mid = CertainOperator(n, opLInv.begin(), opR.begin());
        for (int i = 0; i < n; i++) res[mapL[i]] = mapR[mid[i]];
        return res;
    }
    static std::vector<int> MakeTable(std::vector<int> A) {
        int n = A.size();
        auto B = MakeTableIn(A.begin(), n);
        std::vector<int> res(n);
        for (int i = 0; i < n * 2; i++)
            if (B[i] < n) res[B[i]] = std::max(0, i - n + 1);
        return res;
    }
    template <class Elem>
    static std::vector<int> InterpretAsPermutation(
        const std::vector<Elem>& seq) {
        int n = int(seq.size());
        std::vector<int> I(n);
        for (int i = 0; i < n; i++) I[i] = n - 1 - i;
        std::stable_sort(I.begin(), I.end(),
                         [&](int l, int r) { return seq[l] < seq[r]; });
        return I;
    }
    RangeLis() : n(0) {}
    template <class Elem>
    RangeLis(const std::vector<Elem>& seq)
        : n(int(seq.size())), ds(n, MakeTable(InterpretAsPermutation(seq))) {}
    int lis(int l, int r) {
        if (l == r) return 0;
        return ds.countRange(l, r, l + 1);
    }
};

}  // namespace nachia
#include <cctype>
#include <cstdint>
#include <cstdio>
#include <string>

namespace nachia {

struct CInStream {
   private:
    static const unsigned int INPUT_BUF_SIZE = 1 << 17;
    unsigned int p = INPUT_BUF_SIZE;
    static char Q[INPUT_BUF_SIZE];

   public:
    using MyType = CInStream;
    char seekChar() {
        if (p == INPUT_BUF_SIZE) {
            size_t len = fread(Q, 1, INPUT_BUF_SIZE, stdin);
            if (len != INPUT_BUF_SIZE) Q[len] = '\0';
            p = 0;
        }
        return Q[p];
    }
    void skipSpace() {
        while (isspace(seekChar())) p++;
    }

   private:
    template <class T, int sp = 1>
    T nextUInt() {
        if constexpr (sp) skipSpace();
        T buf = 0;
        while (true) {
            char tmp = seekChar();
            if ('9' < tmp || tmp < '0') break;
            buf = buf * 10 + (tmp - '0');
            p++;
        }
        return buf;
    }

   public:
    uint32_t nextU32() { return nextUInt<uint32_t>(); }
    int32_t nextI32() {
        skipSpace();
        if (seekChar() == '-') {
            p++;
            return (int32_t)(-nextUInt<uint32_t, 0>());
        }
        return (int32_t)nextUInt<uint32_t, 0>();
    }
    uint64_t nextU64() { return nextUInt<uint64_t>(); }
    int64_t nextI64() {
        skipSpace();
        if (seekChar() == '-') {
            p++;
            return (int64_t)(-nextUInt<int64_t, 0>());
        }
        return (int64_t)nextUInt<int64_t, 0>();
    }
    template <class T>
    T nextInt() {
        skipSpace();
        if (seekChar() == '-') {
            p++;
            return -nextUInt<T, 0>();
        }
        return nextUInt<T, 0>();
    }
    char nextChar() {
        skipSpace();
        char buf = seekChar();
        p++;
        return buf;
    }
    std::string nextToken() {
        skipSpace();
        std::string buf;
        while (true) {
            char ch = seekChar();
            if (isspace(ch) || ch == '\0') break;
            buf.push_back(ch);
            p++;
        }
        return buf;
    }
    MyType& operator>>(unsigned int& dest) {
        dest = nextU32();
        return *this;
    }
    MyType& operator>>(int& dest) {
        dest = nextI32();
        return *this;
    }
    MyType& operator>>(unsigned long& dest) {
        dest = nextU64();
        return *this;
    }
    MyType& operator>>(long& dest) {
        dest = nextI64();
        return *this;
    }
    MyType& operator>>(unsigned long long& dest) {
        dest = nextU64();
        return *this;
    }
    MyType& operator>>(long long& dest) {
        dest = nextI64();
        return *this;
    }
    MyType& operator>>(std::string& dest) {
        dest = nextToken();
        return *this;
    }
    MyType& operator>>(char& dest) {
        dest = nextChar();
        return *this;
    }
} cin;

struct FastOutputTable {
    char LZ[1000][4] = {};
    char NLZ[1000][4] = {};
    constexpr FastOutputTable() {
        using u32 = uint_fast32_t;
        for (u32 d = 0; d < 1000; d++) {
            LZ[d][0] = ('0' + d / 100 % 10);
            LZ[d][1] = ('0' + d / 10 % 10);
            LZ[d][2] = ('0' + d / 1 % 10);
            LZ[d][3] = '\0';
        }
        for (u32 d = 0; d < 1000; d++) {
            u32 i = 0;
            if (d >= 100) NLZ[d][i++] = ('0' + d / 100 % 10);
            if (d >= 10) NLZ[d][i++] = ('0' + d / 10 % 10);
            if (d >= 1) NLZ[d][i++] = ('0' + d / 1 % 10);
            NLZ[d][i++] = '\0';
        }
    }
};

struct COutStream {
   private:
    using u32 = uint32_t;
    using u64 = uint64_t;
    using MyType = COutStream;
    static const u32 OUTPUT_BUF_SIZE = 1 << 17;
    static char Q[OUTPUT_BUF_SIZE];
    static constexpr FastOutputTable TB = FastOutputTable();
    u32 p = 0;
    static constexpr u32 P10(u32 d) { return d ? P10(d - 1) * 10 : 1; }
    static constexpr u64 P10L(u32 d) { return d ? P10L(d - 1) * 10 : 1; }
    template <class T, class U>
    static void Fil(T& m, U& l, U x) {
        m = l / x;
        l -= m * x;
    }

   public:
    void next_dig9(u32 x) {
        u32 y;
        Fil(y, x, P10(6));
        nextCstr(TB.LZ[y]);
        Fil(y, x, P10(3));
        nextCstr(TB.LZ[y]);
        nextCstr(TB.LZ[x]);
    }
    void nextChar(char c) {
        Q[p++] = c;
        if (p == OUTPUT_BUF_SIZE) {
            fwrite(Q, p, 1, stdout);
            p = 0;
        }
    }
    void nextEoln() { nextChar('\n'); }
    void nextCstr(const char* s) {
        while (*s) nextChar(*(s++));
    }
    void nextU32(uint32_t x) {
        u32 y = 0;
        if (x >= P10(9)) {
            Fil(y, x, P10(9));
            nextCstr(TB.NLZ[y]);
            next_dig9(x);
        } else if (x >= P10(6)) {
            Fil(y, x, P10(6));
            nextCstr(TB.NLZ[y]);
            Fil(y, x, P10(3));
            nextCstr(TB.LZ[y]);
            nextCstr(TB.LZ[x]);
        } else if (x >= P10(3)) {
            Fil(y, x, P10(3));
            nextCstr(TB.NLZ[y]);
            nextCstr(TB.LZ[x]);
        } else if (x >= 1)
            nextCstr(TB.NLZ[x]);
        else
            nextChar('0');
    }
    void nextI32(int32_t x) {
        if (x >= 0)
            nextU32(x);
        else {
            nextChar('-');
            nextU32((u32)-x);
        }
    }
    void nextU64(uint64_t x) {
        u32 y = 0;
        if (x >= P10L(18)) {
            Fil(y, x, P10L(18));
            nextU32(y);
            Fil(y, x, P10L(9));
            next_dig9(y);
            next_dig9(x);
        } else if (x >= P10L(9)) {
            Fil(y, x, P10L(9));
            nextU32(y);
            next_dig9(x);
        } else
            nextU32(x);
    }
    void nextI64(int64_t x) {
        if (x >= 0)
            nextU64(x);
        else {
            nextChar('-');
            nextU64((u64)-x);
        }
    }
    template <class T>
    void nextInt(T x) {
        if (x < 0) {
            nextChar('-');
            x = -x;
        }
        if (!(0 < x)) {
            nextChar('0');
            return;
        }
        std::string buf;
        while (0 < x) {
            buf.push_back('0' + (int)(x % 10));
            x /= 10;
        }
        for (int i = (int)buf.size() - 1; i >= 0; i--) {
            nextChar(buf[i]);
        }
    }
    void writeToFile(bool flush = false) {
        fwrite(Q, p, 1, stdout);
        if (flush) fflush(stdout);
        p = 0;
    }
    COutStream() { Q[0] = 0; }
    ~COutStream() { writeToFile(); }
    MyType& operator<<(unsigned int tg) {
        nextU32(tg);
        return *this;
    }
    MyType& operator<<(unsigned long tg) {
        nextU64(tg);
        return *this;
    }
    MyType& operator<<(unsigned long long tg) {
        nextU64(tg);
        return *this;
    }
    MyType& operator<<(int tg) {
        nextI32(tg);
        return *this;
    }
    MyType& operator<<(long tg) {
        nextI64(tg);
        return *this;
    }
    MyType& operator<<(long long tg) {
        nextI64(tg);
        return *this;
    }
    MyType& operator<<(const std::string& tg) {
        nextCstr(tg.c_str());
        return *this;
    }
    MyType& operator<<(const char* tg) {
        nextCstr(tg);
        return *this;
    }
    MyType& operator<<(char tg) {
        nextChar(tg);
        return *this;
    }
} cout;

char CInStream::Q[INPUT_BUF_SIZE];
char COutStream::Q[OUTPUT_BUF_SIZE];

}  // namespace nachia

int main() {
    std::cout << fixed << setprecision(15);
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n, m;
    IN(n, m);
    vector<vector<pair<int, i64>>> g(n + 1);
    vector<array<int, 3>> Q(m);
    rep(i, m) {
        int l, r, k;
        IN(l, r, k);
        l--;
        Q[i] = {l, r, k};
        if (k > r - l) {
            OUT("No");
            return 0;
        }
        g[r].emplace_back(l, k);
    }
    rep(i, n) {
        g[i + 1].emplace_back(i, 1);
        g[i].emplace_back(i + 1, 0);
    }
    auto z = dijkstra(g, n);
    z.pop_back();
    for (auto& e : z) e = n + 1 - e;
    auto ds = nachia::RangeLis(z);
    for (auto [l, r, k] : Q) {
        if (ds.lis(l, r) != k) {
            OUT("No");
            return 0;
        }
    }
    OUT("Yes");
    OUT(z);
}