Problem: You have a string S of length N. Initially, all characters in S are `1`s.

You will perform queries Q times. In the i-th query, you are given two integers L_i, R_i and a character D_i (which is a digit). Then, you must replace all characters from the L_i-th to the R_i-th (inclusive) with D_i.

After each query, read the string S as a decimal integer, and print its value modulo 998,244,353.

Constraints

* 1 \leq N, Q \leq 200,000
* 1 \leq L_i \leq R_i \leq N
* 1 \leq D_i \leq 9
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N Q
L_1 R_1 D_1
:
L_Q R_Q D_Q


Output

Print Q lines. In the i-th line print the value of S after the i-th query, modulo 998,244,353.

Examples

Input

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


Output

11222211
77772211
77333333
72333333
72311333


Input

200000 1
123 456 7


Output

641437905

Solution (in PYTHON3):

Solution:
# class化。
import sys

input = sys.stdin.buffer.readline

mod = 998244353


max_n = 262144 + 10
pow_list = [1] * max_n
cum_pow = [0] * max_n
cum_pow[0] = 1
for i in range(1, max_n):
    pow_list[i] = pow_list[i - 1] * 10
    pow_list[i] %= mod
    cum_pow[i] += cum_pow[i - 1] + pow_list[i]
    cum_pow[i] %= mod
cum_pow = [0] + cum_pow


class LazySegmentTree:
    # funcはseg同士、calcはpoint計算
    def __init__(self, n, ele, lazy_ele, mod=mod):
        self.n = n
        self.ele = ele
        self.lazy_ele = lazy_ele
        self.num = 2 ** ((self.n - 1).bit_length())
        self.SEG = [self.ele] * (2 * self.num)
        self.LAZY = [self.lazy_ele] * (2 * self.num)
        self.node = [1] * (self.num + self.n) + [0] * (self.num - self.n)
        for i in reversed(range(1, self.num)):
            self.node[i] = self.node[2 * i] + self.node[2 * i + 1]

    # SEG同士の計算
    def func(self, a, b, b_node):
        if b == 0:
            return a
        if a == 0:
            return b
        return (a * pow_list[b_node] + b) % mod

    # LAZYをSEGに作用
    def calc(self, idx):
        if self.LAZY[idx] == -1:
            return self.SEG[idx]
        node_num = self.node[idx]
        res = (self.LAZY[idx] * cum_pow[node_num]) % mod
        return res

    # LAZY同士の作用の蓄積
    def lazy_func(self, a, b):
        return b

    # 配列で初期化
    def initialize(self, A):
        for i, val in enumerate(A):
            i += self.num
            self.SEG[i] = val
        for i in reversed(range(1, self.num)):
            self.SEG[i] = self.func(
                self.SEG[2 * i], self.SEG[2 * i + 1], self.node[2 * i + 1]
            )

    # LAZYの値を1つ下に伝播して初期化
    def propagate_point(self, idx):
        if self.LAZY[idx] >= 0:
            self.SEG[idx] = self.calc(idx)
            # print(idx)
            self.LAZY[2 * idx] = self.lazy_func(self.LAZY[2 * idx], self.LAZY[idx])
            self.LAZY[2 * idx + 1] = self.lazy_func(
                self.LAZY[2 * idx + 1], self.LAZY[idx]
            )
            self.LAZY[idx] = lazy_ele

    # idx=1からidxの直上まで、伝播を行う
    def propagate_above(self, idx):
        height = idx.bit_length() - 1
        # print(idx, height)
        for h in reversed(range(1, height + 1)):
            self.propagate_point(idx >> h)

    # そのidxの直上の値を計算
    def recalc_above(self, idx):
        # print("ra", idx)
        while idx > 1:
            idx //= 2
            self.SEG[idx] = self.func(
                self.calc(2 * idx), self.calc(2 * idx + 1), self.node[2 * idx + 1],
            )

    # 1点更新
    def update_point(self, idx):
        idx += self.num
        while idx > 0:
            idx //= 2
            self.SEG[idx] = self.func(
                self.calc(self.SEG[2 * idx]),
                self.calc(self.SEG[2 * idx + 1]),
                self.node[2 * idx + 1],
            )

    # 範囲更新
    def update_range(self, left, right, mono):
        left += self.num
        right += self.num
        left_temp = left // (left & -left)
        right_temp = right // (right & -right) - 1
        self.propagate_above(left_temp)
        self.propagate_above(right_temp)
        while left < right:
            if left & 1:
                self.LAZY[left] = self.lazy_func(self.LAZY[left], mono)
                left += 1
            if right & 1:
                right -= 1
                self.LAZY[right] = self.lazy_func(self.LAZY[right], mono)
            left //= 2
            right //= 2
        self.recalc_above(left_temp)
        self.recalc_above(right_temp)

    # 範囲取得
    def get_range(self, left, right):
        left += self.num
        right += self.num
        self.propagate_above(left // (left & -left))
        self.propagate_above(right // (right & -right) - 1)
        res_left = self.ele
        res_left_node = 0
        res_right = self.ele
        res_right_node = 0
        while left < right:
            if left & 1:
                res_left = self.func(res_left, self.calc(left), res_left_node)
                res_left_node += self.node[left]
                left += 1
            if right & 1:
                right -= 1
                res_right = self.func(self.calc(right), res_right, res_right_node)
                res_right_node += self.node[right]
            left //= 2
            right //= 2
        # print(res_left, res_right, left, right)
        return self.func(res_right, res_left, res_left_node) % mod

    # def get_point(self, idx):
    #     a,b=self.LAZY[idx]>>32, self.LAZY[idx]&(1<<32-1)
    #     return a*self.SEG[idx]+b*self.node[idx]


ele = 0
lazy_ele = -1
n, q = map(int, input().split())
A = [1 for _ in range(n)]

# for i in range(122, 456):
#     A[i] = 7
LST = LazySegmentTree(n, ele, lazy_ele)
LST.initialize(A)

# print(LST.get_range(0, n) % mod)
for _ in range(q):
    l, r, d = map(int, input().split())
    l -= 1

    LST.update_range(l, r, d)

    print(LST.get_range(0, n) % mod)