Ая изучает магию в Магическом университете Ланоа!

Сегодня Ая изучает магические круги. Магический круг перед ней состоит из окружности и $n$ магических узлов, расположенных на этой окружности. Эти $n$ узлов делят окружность на $n$ равных частей и пронумерованы по часовой стрелке от $1$ до $n$. Узел с номером $i$ имеет цвет $c_i$ и магическую силу $a_i$, где $c_i \le k$. Если два магических узла имеют одинаковый цвет, они соединяются магическим отрезком того же цвета. Магическая сила этого отрезка равна произведению магических сил двух узлов, которые он соединяет. Если два магических отрезка разных цветов пересекаются, они создают магическую интенсивность, равную произведению магических сил этих двух отрезков. Общая магическая интенсивность круга равна сумме магических интенсивностей, создаваемых каждой парой пересекающихся отрезков разных цветов.

Теперь Ая хочет узнать значение магической интенсивности магического круга перед ней. Поскольку ответ может быть очень большим, вам нужно вывести его по модулю $998244353$.

Входные данные

Первая строка содержит два целых числа $n, k$ ($4 \le n \le 5 \times 10^5, 2 \le k \le 100$), обозначающих количество магических узлов и верхнюю границу количества цветов узлов.

Вторая строка содержит $n$ целых чисел, где $i$-е число обозначает цвет $c_i$ узла с номером $i$ ($1 \le c_i \le k$).

Третья строка содержит $n$ целых чисел, где $i$-е число обозначает магическую силу $a_i$ узла с номером $i$ ($0 \le a_i < 998244353$).

Выходные данные

Выведите одно целое число — значение магической интенсивности магического круга по модулю $998244353$.

Примеры

Входные данные 1

4 2
1 2 1 2
1 2 3 4

Выходные данные 1

24

Входные данные 2

8 4
1 4 2 2 1 2 4 2
3 1000 1 1000 4 2 1000 1000

Выходные данные 2

786705612