Подаруночки#11535

Подаруночки

1 секунда

256 мегабайтів

Середня

Якось Кіч вирішив зробити подарунок Почі на Новий рік. Він підготував $n$ мішків з подарунками, в кожному з яких є $k_{i}$ k_i подарунків різних видів. Почі має список улюблених видів подарунків, який спочатку порожній. Є $q$ запитів двох типів:

Почі сподобався подарунок виду $x$ .
Почі розподобався подарунок виду $x$ .

Після кожної зміни списку Кіч випадково обирає один з мішків, а потім випадково дістає один подарунок з цього мішка. Після цього подарунок повертається назад у мішок. Знайдіть ймовірність того, що Кіч дістане один з улюблених подарунків Почі.

Вхідні дані

У першому рядку вводяться два цілі невід'ємні числа $n$ і $q (1 \leq n, q \leq 1 0^{5})$ q~(1 \le n, q \le 10^5) — кількість мішків і кількість запитів.

Наступні $n$ рядків містять ціле невід'ємне число $k_{i} (0 \leq k_{i} \leq 1 0^{5})$ k_i~(0 \le k_i \le 10^5) — кількість подарунків у мішку, а також $k_{i}$ k_i цілих невід'ємних чисел, що позначають види подарунків.

Наступні $q$ рядків описують запити:

Для запиту першого типу: вводяться число 1 і число $x (1 \leq x \leq 1 0^{9})$ x~(1 \le x \le 10^9) — вид подарунка, який сподобався Почі.
Для запиту другого типу: вводяться число 2 і число $x (1 \leq x \leq 1 0^{9})$ x~(1 \le x \le 10^9) — вид подарунка, який розподобався Почі.

Гарантується, що Почі не розподобається подарунок, який йому не подобається до запиту, а також не почне подобатися подарунок, який і так подобався.

Сума по $k_{i}$ k_i не перевищує $2 \cdot 1 0^{5}$ 2 \cdot 10^5.

Вихідні дані

Виведіть $q$ рядків: у рядку $i$ виведіть ймовірність того, що Почі дістанеться один з його улюблених подарунків, взятий по модулю $998244353$ . Оскільки відповідь завжди можна представити у вигляді нескоротного дробу $\frac{a}{b}$ \frac{a}{b}, де $b m o d 998244353 \neq = 0$ b ~ mod ~ 998244353 \neq 0, ми просимо вас вивести $a \cdot b^{- 1} m o d 998244353$ a \cdot b^{-1} ~ mod ~ 998244353.

Приклади

Приклад 1

Приклад 2