Beautiful Mirrors with queries

Creatnx has $n$ mirrors, numbered from $1$ to $n$. Every day, Creatnx asks exactly one mirror “Am I beautiful?”. The $i$-th mirror will tell Creatnx that he is beautiful with probability $\frac{p_i}{100}$ for all $1 \le i \le n$.

Some mirrors are called checkpoints. Initially, only the $1$st mirror is a checkpoint. It remains a checkpoint all the time.

Creatnx asks the mirrors one by one, starting from the $1$-st mirror. Every day, if he asks $i$-th mirror, there are two possibilities:

• The $i$-th mirror tells Creatnx that he is beautiful. In this case, if $i = n$ Creatnx will stop and become happy, otherwise he will continue asking the $i+1$-th mirror next day;
• In the other case, Creatnx will feel upset. The next day, Creatnx will start asking from the checkpoint with a maximal number that is less or equal to $i$.

There are some changes occur over time: some mirrors become new checkpoints and some mirrors are no longer checkpoints. You are given $q$ queries, each query is represented by an integer $u$: If the $u$-th mirror isn’t a checkpoint then we set it as a checkpoint. Otherwise, the $u$-th mirror is no longer a checkpoint.

After each query, you need to calculate the expected number of days until Creatnx becomes happy.

Each of this numbers should be found by modulo $998244353$. Formally, let $M = 998244353$. It can be shown that the answer can be expressed as an irreducible fraction $\frac{p}{q}$, where $p$ and $q$ are integers and $q \not \equiv 0 \pmod{M}$. Output the integer equal to $p \cdot q^{-1} \bmod M$. In other words, output such an integer $x$ that $0 \le x < M$ and $x \cdot q \equiv p \pmod{M}$.Input

The first line contains two integers $n$, $q$ ($2 \leq n, q \le 2 \cdot 10^5$)  — the number of mirrors and queries.

The second line contains $n$ integers: $p_1, p_2, \ldots, p_n$ ($1 \leq p_i \leq 100$).

Each of $q$ following lines contains a single integer $u$ ($2 \leq u \leq n$) — next query.Output

Print $q$ numbers – the answers after each query by modulo $998244353$.Examplesinput

2 2
50 50
2
2

output

4
6

input

5 5
10 20 30 40 50
2
3
4
5
3

output

117
665496274
332748143
831870317
499122211

Note

In the first test after the first query, the first and the second mirrors are checkpoints. Creatnx will ask the first mirror until it will say that he is beautiful, after that he will ask the second mirror until it will say that he is beautiful because the second mirror is a checkpoint. After that, he will become happy. Probabilities that the mirrors will say, that he is beautiful are equal to $\frac{1}{2}$. So, the expected number of days, until one mirror will say, that he is beautiful is equal to $2$ and the answer will be equal to $4 = 2 + 2$.

Solution:

#include <bits/stdc++.h>

using namespace std;

template <typename A, typename B>
string to_string(pair<A, B> p);

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);

string to_string(const string& s) {
return '"' + s + '"';
}

string to_string(const char* s) {
return to_string((string) s);
}

string to_string(bool b) {
return (b ? "true" : "false");
}

string to_string(vector<bool> v) {
bool first = true;
string res = "{";
for (int i = 0; i < static_cast<int>(v.size()); i++) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(v[i]);
}
res += "}";
return res;
}

template <size_t N>
string to_string(bitset<N> v) {
string res = "";
for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
}
return res;
}

template <typename A>
string to_string(A v) {
bool first = true;
string res = "{";
for (const auto &x : v) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(x);
}
res += "}";
return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << to_string(H);
  debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

template <typename T>
T inverse(T a, T m) {
T u = 0, v = 1;
while (a != 0) {
T t = m / a;
m -= t * a; swap(a, m);
u -= t * v; swap(u, v);
}
assert(m == 1);
return u;
}

template <typename T>
class Modular {
public:
using Type = typename decay<decltype(T::value)>::type;

constexpr Modular() : value() {}
template <typename U>
Modular(const U& x) {
value = normalize(x);
}

template <typename U>
static Type normalize(const U& x) {
Type v;
if (-mod() <= x && x < mod()) v = static_cast<Type>(x);
else v = static_cast<Type>(x % mod());
if (v < 0) v += mod();
    return v;
  }

  const Type& operator()() const { return value; }
  template <typename U>
explicit operator U() const { return static_cast<U>(value); }
constexpr static Type mod() { return T::value; }

Modular& operator+=(const Modular& other) { if ((value += other.value) >= mod()) value -= mod(); return *this; }
Modular& operator-=(const Modular& other) { if ((value -= other.value) < 0) value += mod(); return *this; }
  template <typename U> Modular& operator+=(const U& other) { return *this += Modular(other); }
template <typename U> Modular& operator-=(const U& other) { return *this -= Modular(other); }
Modular& operator++() { return *this += 1; }
Modular& operator--() { return *this -= 1; }
Modular operator++(int) { Modular result(*this); *this += 1; return result; }
Modular operator--(int) { Modular result(*this); *this -= 1; return result; }
Modular operator-() const { return Modular(-value); }

template <typename U = T>
typename enable_if<is_same<typename Modular<U>::Type, int>::value, Modular>::type& operator*=(const Modular& rhs) {
#ifdef _WIN32
uint64_t x = static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value);
uint32_t xh = static_cast<uint32_t>(x >> 32), xl = static_cast<uint32_t>(x), d, m;
asm(
"divl %4; \n\t"
: "=a" (d), "=d" (m)
: "d" (xh), "a" (xl), "r" (mod())
);
value = m;
#else
value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
#endif
return *this;
}
template <typename U = T>
typename enable_if<is_same<typename Modular<U>::Type, int64_t>::value, Modular>::type& operator*=(const Modular& rhs) {
int64_t q = static_cast<int64_t>(static_cast<long double>(value) * rhs.value / mod());
value = normalize(value * rhs.value - q * mod());
return *this;
}
template <typename U = T>
typename enable_if<!is_integral<typename Modular<U>::Type>::value, Modular>::type& operator*=(const Modular& rhs) {
value = normalize(value * rhs.value);
return *this;
}

Modular& operator/=(const Modular& other) { return *this *= Modular(inverse(other.value, mod())); }

template <typename U>
friend const Modular<U>& abs(const Modular<U>& v) { return v; }

template <typename U>
friend bool operator==(const Modular<U>& lhs, const Modular<U>& rhs);

template <typename U>
friend bool operator<(const Modular<U>& lhs, const Modular<U>& rhs);

template <typename U>
friend std::istream& operator>>(std::istream& stream, Modular<U>& number);

private:
Type value;
};

template <typename T> bool operator==(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value == rhs.value; }
template <typename T, typename U> bool operator==(const Modular<T>& lhs, U rhs) { return lhs == Modular<T>(rhs); }
template <typename T, typename U> bool operator==(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) == rhs; }

template <typename T> bool operator!=(const Modular<T>& lhs, const Modular<T>& rhs) { return !(lhs == rhs); }
template <typename T, typename U> bool operator!=(const Modular<T>& lhs, U rhs) { return !(lhs == rhs); }
template <typename T, typename U> bool operator!=(U lhs, const Modular<T>& rhs) { return !(lhs == rhs); }

template <typename T> bool operator<(const Modular<T>& lhs, const Modular<T>& rhs) { return lhs.value < rhs.value; }

template <typename T> Modular<T> operator+(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) += rhs; }
template <typename T, typename U> Modular<T> operator+(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) += rhs; }

template <typename T> Modular<T> operator-(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) -= rhs; }
template <typename T, typename U> Modular<T> operator-(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) -= rhs; }

template <typename T> Modular<T> operator*(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) *= rhs; }
template <typename T, typename U> Modular<T> operator*(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) *= rhs; }

template <typename T> Modular<T> operator/(const Modular<T>& lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U> Modular<T> operator/(const Modular<T>& lhs, U rhs) { return Modular<T>(lhs) /= rhs; }
template <typename T, typename U> Modular<T> operator/(U lhs, const Modular<T>& rhs) { return Modular<T>(lhs) /= rhs; }

template<typename T, typename U>
Modular<T> power(const Modular<T>& a, const U& b) {
assert(b >= 0);
Modular<T> x = a, res = 1;
U p = b;
while (p > 0) {
if (p & 1) res *= x;
x *= x;
p >>= 1;
}
return res;
}

template <typename T>
bool IsZero(const Modular<T>& number) {
return number() == 0;
}

template <typename T>
string to_string(const Modular<T>& number) {
return to_string(number());
}

template <typename T>
std::ostream& operator<<(std::ostream& stream, const Modular<T>& number) {
return stream << number();
}

template <typename T>
std::istream& operator>>(std::istream& stream, Modular<T>& number) {
typename common_type<typename Modular<T>::Type, int64_t>::type x;
stream >> x;
number.value = Modular<T>::normalize(x);
return stream;
}

/*
using ModType = int;

struct VarMod { static ModType value; };
ModType VarMod::value;
ModType& md = VarMod::value;
using Mint = Modular<VarMod>;
*/

constexpr int md = 998244353;
using Mint = Modular<std::integral_constant<decay<decltype(md)>::type, md>>;

class segtree {
public:
struct node {
// don't forget to set default value (used for leaves)
// not necessarily neutral element!
Mint k = 1;
Mint b = 0;

void apply(int l, int r, Mint v) {
k = v;
b = 1;
}
};

node unite(const node &a, const node &b) const {
node res;
res.k = a.k * b.k;
res.b = a.b + a.k * b.b;
return res;
}

inline void push(int x, int l, int r) {
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
    // push from x into (x + 1) and z
/*
    if (tree[x].add != 0) {
      tree[x + 1].apply(l, y, tree[x].add);
      tree[z].apply(y + 1, r, tree[x].add);
      tree[x].add = 0;
    }
*/
  }

  inline void pull(int x, int z) {
    tree[x] = unite(tree[x + 1], tree[z]);
  }

  int n;
  vector<node> tree;

void build(int x, int l, int r) {
if (l == r) {
return;
}
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
    build(x + 1, l, y);
    build(z, y + 1, r);
    pull(x, z);
  }

  template <typename M>
void build(int x, int l, int r, const vector<M> &v) {
if (l == r) {
tree[x].apply(l, r, v[l]);
return;
}
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
    build(x + 1, l, y, v);
    build(z, y + 1, r, v);
    pull(x, z);
  }

  node get(int x, int l, int r, int ll, int rr) {
    if (ll <= l && r <= rr) {
      return tree[x];
    }
    int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
    push(x, l, r);
    node res{};
    if (rr <= y) {
      res = get(x + 1, l, y, ll, rr);
    } else {
      if (ll > y) {
res = get(z, y + 1, r, ll, rr);
} else {
res = unite(get(x + 1, l, y, ll, rr), get(z, y + 1, r, ll, rr));
}
}
pull(x, z);
return res;
}

template <typename... M>
void modify(int x, int l, int r, int ll, int rr, const M&... v) {
if (ll <= l && r <= rr) {
      tree[x].apply(l, r, v...);
      return;
    }
    int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
    push(x, l, r);
    if (ll <= y) {
      modify(x + 1, l, y, ll, rr, v...);
    }
    if (rr > y) {
modify(z, y + 1, r, ll, rr, v...);
}
pull(x, z);
}

int find_first_knowingly(int x, int l, int r, const function<bool(const node&)> &f) {
if (l == r) {
return l;
}
push(x, l, r);
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
    int res;
    if (f(tree[x + 1])) {
      res = find_first_knowingly(x + 1, l, y, f);
    } else {
      res = find_first_knowingly(z, y + 1, r, f);
    }
    pull(x, z);
    return res;
  }

  int find_first(int x, int l, int r, int ll, int rr, const function<bool(const node&)> &f) {
if (ll <= l && r <= rr) {
      if (!f(tree[x])) {
        return -1;
      }
      return find_first_knowingly(x, l, r, f);
    }
    push(x, l, r);
    int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
    int res = -1;
    if (ll <= y) {
      res = find_first(x + 1, l, y, ll, rr, f);
    }
    if (rr > y && res == -1) {
res = find_first(z, y + 1, r, ll, rr, f);
}
pull(x, z);
return res;
}

int find_last_knowingly(int x, int l, int r, const function<bool(const node&)> &f) {
if (l == r) {
return l;
}
push(x, l, r);
int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
    int res;
    if (f(tree[z])) {
      res = find_last_knowingly(z, y + 1, r, f);
    } else {
      res = find_last_knowingly(x + 1, l, y, f);
    }
    pull(x, z);
    return res;
  }

  int find_last(int x, int l, int r, int ll, int rr, const function<bool(const node&)> &f) {
if (ll <= l && r <= rr) {
      if (!f(tree[x])) {
        return -1;
      }
      return find_last_knowingly(x, l, r, f);
    }
    push(x, l, r);
    int y = (l + r) >> 1;
int z = x + ((y - l + 1) << 1);
    int res = -1;
    if (rr > y) {
res = find_last(z, y + 1, r, ll, rr, f);
}
if (ll <= y && res == -1) {
      res = find_last(x + 1, l, y, ll, rr, f);
    }
    pull(x, z);
    return res;
  }

  segtree(int _n) : n(_n) {
    assert(n > 0);
tree.resize(2 * n - 1);
build(0, 0, n - 1);
}

template <typename M>
segtree(const vector<M> &v) {
n = v.size();
assert(n > 0);
tree.resize(2 * n - 1);
build(0, 0, n - 1, v);
}

node get(int ll, int rr) {
assert(0 <= ll && ll <= rr && rr <= n - 1);
    return get(0, 0, n - 1, ll, rr);
  }

  node get(int p) {
    assert(0 <= p && p <= n - 1);
    return get(0, 0, n - 1, p, p);
  }

  template <typename... M>
void modify(int ll, int rr, const M&... v) {
assert(0 <= ll && ll <= rr && rr <= n - 1);
    modify(0, 0, n - 1, ll, rr, v...);
  }

  // find_first and find_last call all FALSE elements
  // to the left (right) of the sought position exactly once

  int find_first(int ll, int rr, const function<bool(const node&)> &f) {
assert(0 <= ll && ll <= rr && rr <= n - 1);
    return find_first(0, 0, n - 1, ll, rr, f);
  }

  int find_last(int ll, int rr, const function<bool(const node&)> &f) {
assert(0 <= ll && ll <= rr && rr <= n - 1);
    return find_last(0, 0, n - 1, ll, rr, f);
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, tt;
  cin >> n >> tt;
vector<Mint> p(n);
for (int i = 0; i < n; i++) {
    cin >> p[i];
p[i] /= 100;
}
segtree st(p);
auto Get = [&](int x, int y) {
auto res = st.get(x, y - 1);
debug(x, y, res.k, res.b);
return res.b / res.k;
};
set<int> chk;
chk.insert(0);
chk.insert(n);
Mint ans = Get(0, n);
while (tt--) {
int id;
cin >> id;
--id;
if (chk.find(id) == chk.end()) {
chk.insert(id);
auto it = chk.find(id);
int pr = *prev(it);
int ne = *next(it);
ans -= Get(pr, ne);
ans += Get(pr, id);
ans += Get(id, ne);
} else {
auto it = chk.find(id);
int pr = *prev(it);
int ne = *next(it);
chk.erase(it);
ans += Get(pr, ne);
ans -= Get(pr, id);
ans -= Get(id, ne);
}
cout << ans << '\n';
  }
  return 0;
}