Problem: An infinitely long Line Chillland Collider (LCC) was built in Chillland. There are n pipes with coordinates x_i that are connected to LCC. When the experiment starts at time 0, i-th proton flies from the i-th pipe with speed v_i. It flies to the right with probability p_i and flies to the left with probability (1 - p_i). The duration of the experiment is determined as the time of the first collision of any two protons. In case there is no collision, the duration of the experiment is considered to be zero.

Find the expected value of the duration of the experiment.

<image>Illustration for the first example

Input

The first line of input contains one integer n — the number of pipes (1 ≤ n ≤ 10^5). Each of the following n lines contains three integers x_i, v_i, p_i — the coordinate of the i-th pipe, the speed of the i-th proton and the probability that the i-th proton flies to the right in percentage points (-10^9 ≤ x_i ≤ 10^9, 1 ≤ v ≤ 10^6, 0 ≤ p_i ≤ 100). It is guaranteed that all x_i are distinct and sorted in increasing order.

Output

It's possible to prove that the answer can always be represented as a fraction P/Q, where P is an integer and Q is a natural number not divisible by 998 244 353. In this case, print P ⋅ Q^{-1} modulo 998 244 353.

Examples

Input


2
1 1 100
3 1 0


Output


1


Input


3
7 10 0
9 4 86
14 5 100


Output


0


Input


4
6 4 50
11 25 50
13 16 50
15 8 50


Output


150902884

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
struct mod_int {
  int val;
  mod_int(long long v = 0) {
    if (v < 0) v = v % MOD + MOD;
    if (v >= MOD) v %= MOD;
    val = v;
  }
  static int mod_inv(int a, int m = MOD) {
    int g = m, r = a, x = 0, y = 1;
    while (r != 0) {
      int q = g / r;
      g %= r;
      swap(g, r);
      x -= q * y;
      swap(x, y);
    }
    return x < 0 ? x + m : x;
  }
  explicit operator int() const { return val; }
  mod_int &operator+=(const mod_int &other) {
    val += other.val;
    if (val >= MOD) val -= MOD;
    return *this;
  }
  mod_int &operator-=(const mod_int &other) {
    val -= other.val;
    if (val < 0) val += MOD;
    return *this;
  }
  static unsigned fast_mod(uint64_t x, unsigned m = MOD) {
    return x % m;
    unsigned x_high = x >> 32, x_low = (unsigned)x;
    unsigned quot, rem;
    asm("divl %4\n" : "=a"(quot), "=d"(rem) : "d"(x_high), "a"(x_low), "r"(m));
    return rem;
  }
  mod_int &operator*=(const mod_int &other) {
    val = fast_mod((uint64_t)val * other.val);
    return *this;
  }
  mod_int &operator/=(const mod_int &other) { return *this *= other.inv(); }
  friend mod_int operator+(const mod_int &a, const mod_int &b) {
    return mod_int(a) += b;
  }
  friend mod_int operator-(const mod_int &a, const mod_int &b) {
    return mod_int(a) -= b;
  }
  friend mod_int operator*(const mod_int &a, const mod_int &b) {
    return mod_int(a) *= b;
  }
  friend mod_int operator/(const mod_int &a, const mod_int &b) {
    return mod_int(a) /= b;
  }
  mod_int &operator++() {
    val = val == MOD - 1 ? 0 : val + 1;
    return *this;
  }
  mod_int &operator--() {
    val = val == 0 ? MOD - 1 : val - 1;
    return *this;
  }
  mod_int operator++(int) {
    mod_int before = *this;
    ++*this;
    return before;
  }
  mod_int operator--(int) {
    mod_int before = *this;
    --*this;
    return before;
  }
  mod_int operator-() const { return val == 0 ? 0 : MOD - val; }
  bool operator==(const mod_int &other) const { return val == other.val; }
  bool operator!=(const mod_int &other) const { return val != other.val; }
  mod_int inv() const { return mod_inv(val); }
  mod_int pow(long long p) const {
    assert(p >= 0);
    mod_int a = *this, result = 1;
    while (p > 0) {
      if (p & 1) result *= a;
      a *= a;
      p >>= 1;
    }
    return result;
  }
  friend ostream &operator<<(ostream &stream, const mod_int &m) {
    return stream << m.val;
  }
};
struct mod_matrix_fixed_size {
  static const int SIZE = 2;
  mod_int values[SIZE][SIZE];
  mod_matrix_fixed_size() {
    for (int i = 0; i < SIZE; i++)
      for (int j = 0; j < SIZE; j++) values[i][j] = 0;
  }
  mod_matrix_fixed_size(const vector<vector<mod_int>> &v) {
    for (int i = 0; i < SIZE; i++)
      for (int j = 0; j < SIZE; j++) values[i][j] = v[i][j];
  }
  void make_identity() {
    for (int i = 0; i < SIZE; i++)
      for (int j = 0; j < SIZE; j++) values[i][j] = i == j ? 1 : 0;
  }
  mod_matrix_fixed_size operator*(const mod_matrix_fixed_size &other) const {
    mod_matrix_fixed_size product;
    for (int i = 0; i < SIZE; i++)
      for (int j = 0; j < SIZE; j++)
        if (values[i][j] != 0)
          for (int k = 0; k < SIZE; k++)
            product.values[i][k] += values[i][j] * other.values[j][k];
    return product;
  }
  mod_matrix_fixed_size &operator*=(const mod_matrix_fixed_size &other) {
    return *this = *this * other;
  }
  mod_matrix_fixed_size power(long long p) const {
    assert(p >= 0);
    mod_matrix_fixed_size m = *this;
    mod_matrix_fixed_size result;
    result.make_identity();
    while (p > 0) {
      if (p & 1) result *= m;
      p >>= 1;
      if (p > 0) m *= m;
    }
    return result;
  }
  void print() const {
    for (int i = 0; i < SIZE; i++)
      for (int j = 0; j < SIZE; j++)
        cout << values[i][j] << (j < SIZE - 1 ? ' ' : '\n');
  }
};
struct segment_change {
  mod_matrix_fixed_size change;
  segment_change(mod_int m00 = 1, mod_int m01 = 0, mod_int m10 = 0,
                 mod_int m11 = 1) {
    change = mod_matrix_fixed_size({{m00, m01}, {m10, m11}});
  }
  segment_change(const mod_matrix_fixed_size &m) : change(m) {}
  void reset() { change.make_identity(); }
  bool has_change() const { return true; }
  segment_change combine(const segment_change &other) const {
    return segment_change(change * other.change);
  }
};
struct segment {
  mod_matrix_fixed_size prob;
  segment(mod_int m00 = 1, mod_int m01 = 0, mod_int m10 = 0, mod_int m11 = 1) {
    prob = mod_matrix_fixed_size({{m00, m01}, {m10, m11}});
  }
  mod_int get_probability() const {
    return prob.values[0][0] + prob.values[0][1];
  }
  void apply(int length, const segment_change &change) {
    if (length == 1) prob *= change.change;
  }
  void join(const segment &other) { *this = other; }
  void join(const segment &, const segment &) {}
};
pair<int, int> right_half[32];
struct seg_tree {
  int tree_n = 0;
  vector<segment> tree;
  vector<segment_change> changes;
  seg_tree(int n = -1) {
    if (n >= 0) init(n);
  }
  void init(int n) {
    tree_n = 1;
    while (tree_n < n) tree_n *= 2;
    tree.assign(2 * tree_n, segment());
    changes.assign(tree_n, segment_change());
  }
  void build(const vector<segment> &initial) {
    int n = initial.size();
    init(n);
    assert(n <= tree_n);
    for (int i = 0; i < n; i++) tree[tree_n + i] = initial[i];
    for (int position = tree_n - 1; position > 0; position--)
      tree[position].join(tree[2 * position], tree[2 * position + 1]);
  }
  void push_down(int position, int length) {
    if (!changes[position].has_change()) return;
    if (2 * position < tree_n) {
      changes[2 * position] = changes[2 * position].combine(changes[position]);
      changes[2 * position + 1] =
          changes[2 * position + 1].combine(changes[position]);
    }
    tree[2 * position].apply(length / 2, changes[position]);
    tree[2 * position + 1].apply(length / 2, changes[position]);
    changes[position].reset();
  }
  void push_all(int a, int b) {
    assert(0 <= a && a < b && b <= tree_n);
    a += tree_n;
    b += tree_n - 1;
    for (int up = 31 - __builtin_clz(tree_n); up > 0; up--) {
      int x = a >> up, y = b >> up;
      push_down(x, 1 << up);
      if (x != y) push_down(y, 1 << up);
    }
  }
  void join_and_apply(int position, int length) {
    tree[position].join(tree[2 * position], tree[2 * position + 1]);
    tree[position].apply(length, changes[position]);
  }
  void join_all(int a, int b) {
    assert(0 <= a && a < b && b <= tree_n);
    a += tree_n;
    b += tree_n - 1;
    int length = 1;
    while (a > 1) {
      a /= 2;
      b /= 2;
      length *= 2;
      join_and_apply(a, length);
      if (a != b) join_and_apply(b, length);
    }
  }
  template <typename T_range_op>
  void process_range(int a, int b, bool needs_join, T_range_op &&range_op) {
    if (a == b) return;
    push_all(a, b);
    int original_a = a, original_b = b;
    int length = 1, r_size = 0;
    for (a += tree_n, b += tree_n; a < b; a /= 2, b /= 2, length *= 2) {
      if (a & 1) range_op(a++, length);
      if (b & 1) right_half[r_size++] = {--b, length};
    }
    for (int i = r_size - 1; i >= 0; i--)
      range_op(right_half[i].first, right_half[i].second);
    if (needs_join) join_all(original_a, original_b);
  }
  segment query(int a, int b) {
    assert(0 <= a && a <= b && b <= tree_n);
    segment answer;
    process_range(a, b, false,
                  [&](int position, int) { answer.join(tree[position]); });
    return answer;
  }
  void update(int a, int b, const segment_change &change) {
    assert(0 <= a && a <= b && b <= tree_n);
    process_range(a, b, true, [&](int position, int length) {
      tree[position].apply(length, change);
      if (position < tree_n)
        changes[position] = changes[position].combine(change);
    });
  }
};
struct event {
  long long distance = 0, velocity = 1;
  event() {}
  event(long long _distance, long long _velocity)
      : distance(_distance), velocity(_velocity) {
    assert(distance >= 0 && velocity > 0);
  }
  mod_int get_time() const { return mod_int(distance) / velocity; }
  bool operator<(const event &other) const {
    return distance * other.velocity < other.distance * velocity;
  }
  bool operator==(const event &other) const {
    return distance * other.velocity == other.distance * velocity;
  }
};
const long long DIST_INF = 2e9 + 5;
int N;
vector<int> X, V;
vector<mod_int> probability[2];
event build_event(int before, int after, int before_dir, int after_dir) {
  assert(after - before == 1);
  static const event NEVER(DIST_INF, 1);
  if (before_dir == 0 && after_dir == 1) return NEVER;
  long long distance = X[after] - X[before];
  if (before_dir == 1 && after_dir == 0)
    return event(distance, V[before] + V[after]);
  if (before_dir == 0 && after_dir == 0) {
    if (V[after] > V[before]) return event(distance, V[after] - V[before]);
    return NEVER;
  }
  if (before_dir == 1 && after_dir == 1) {
    if (V[before] > V[after]) return event(distance, V[before] - V[after]);
    return NEVER;
  }
  assert(false);
}
segment_change build_change_for_time(int before, int after, event ev) {
  assert(after - before == 1);
  mod_int m[2][2] = {{0, 0}, {0, 0}};
  for (int before_dir = 0; before_dir < 2; before_dir++)
    for (int after_dir = 0; after_dir < 2; after_dir++)
      if (ev < build_event(before, after, before_dir, after_dir))
        m[before_dir][after_dir] = probability[after_dir][after];
  return segment_change(m[0][0], m[0][1], m[1][0], m[1][1]);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> N;
  X.resize(N);
  V.resize(N);
  probability[0].resize(N);
  probability[1].resize(N);
  const mod_int INV100 = mod_int(100).inv();
  for (int i = 0; i < N; i++) {
    int P;
    cin >> X[i] >> V[i] >> P;
    probability[1][i] = P * INV100;
    probability[0][i] = 1 - probability[1][i];
  }
  vector<event> events;
  events.emplace_back(0, 1);
  events.emplace_back(DIST_INF, 1);
  for (int i = 1; i < N; i++)
    for (int before_dir = 0; before_dir < 2; before_dir++)
      for (int after_dir = 0; after_dir < 2; after_dir++) {
        event ev = build_event(i - 1, i, before_dir, after_dir);
        if (ev.distance < DIST_INF) events.push_back(ev);
      }
  sort(events.begin(), events.end());
  events.resize(unique(events.begin(), events.end()) - events.begin());
  int E = events.size();
  seg_tree tree(E);
  tree.build(
      vector<segment>(E, segment(probability[0][0], probability[1][0], 0, 0)));
  for (int i = 1; i < N; i++) {
    event together_event(X[i] - X[i - 1], V[i] + V[i - 1]);
    int together = lower_bound(events.begin(), events.end(), together_event) -
                   events.begin();
    int away = E;
    if (V[i] != V[i - 1]) {
      event away_event(X[i] - X[i - 1], abs(V[i] - V[i - 1]));
      away = lower_bound(events.begin(), events.end(), away_event) -
             events.begin();
    }
    vector<int> indices = {0, together, away, E};
    sort(indices.begin(), indices.end());
    for (int t = 0; t + 1 < (int)indices.size(); t++) {
      int start = indices[t], end = indices[t + 1];
      if (start >= E) break;
      segment_change change = build_change_for_time(i - 1, i, events[start]);
      tree.update(start, end, change);
    }
  }
  mod_int total = 0;
  for (int e = 0; e + 1 < E - 1; e++)
    total += (events[e + 1].get_time() - events[e].get_time()) *
             tree.query(e, e + 1).get_probability();
  total -=
      events[E - 2].get_time() * tree.query(E - 2, E - 1).get_probability();
  cout << total << '\n';
}