Background

You really like Concvssion, but that does not stop you from doing an interesting problem that is not difficult.

(The background image is from the Phigros music illustration. If there is any infringement, please inform the problem setter.)

Problem Description

Given sequences $a, b$ of length $n$, satisfying $\forall i\in[1,n], a_i, b_i\in[1,n]$.

Define one operation as: $\forall i\in[1,n], b_i\gets a_{b_i}$.

You need to perform $n$ operations in order. After each operation, output $\displaystyle\sum_{i=1}^n b_i \bmod 998244353$.

Input Format

The first line contains an integer $n$.

The second line contains $n$ integers representing $a_{1\sim n}$.

The third line contains $n$ integers representing $b_{1\sim n}$.

Output Format

Output $n$ lines. Each line contains one integer, the answer modulo $998244353$.

5
2 3 4 5 1
2 2 3 1 1

14
19
19
14
9

5
3 5 1 4 2
2 2 3 1 1

17
9
17
9
17

5
1 1 2 2 4
2 2 3 1 1

6
5
5
5
5

5
3 1 5 3 4
2 2 1 3 3

15
19
20
21
19

Hint

Idea: cyffff, Solution: Ntokisq / WhisperingSnowflakes, Code: cyffff / WhisperingSnowflakes, Data: cyffff.

Concvssion - Halv (Insane15.5)

Constraints

This problem uses bundled testdata.

::cute-table | $\text{Subtask}$ | $n\le$ | Special Property | $\text{Score}$ | | :----------: | :----------: | :----------: | :----------: | | $1$ | $10^4$ | None | $10$ | | $2$ | $10^5$ | $\forall i\in[1,n],a_i\le10^3$ | $10$ | | $3$ | ^ | $\forall i\in[1,n],a_i=i\bmod n+1$ | $10$ | | $4$ | ^ | $a$ is a permutation of $[1,n]$ | $15$ | | $5$ | ^ | $a_1=1,\forall i\in[2,n],a_i< i$ | $25$ | | $6$ | ^ | None | $20$ | | $7$ | $3\times10^5$ | ^ | $10$ |

For $100\%$ of the testdata, $1\le a_i,b_i\le n\le 3\times10^5$.

Special Scoring Method

This problem uses subtask dependencies, as follows:

• For subtask $i\in\{1,2,3,5\}$, you only need to solve subtask $i$ correctly to get the score for subtask $i$.
• For subtask $i=4$, you need to solve all subtasks $j\in[3,4]$ correctly to get the score for subtask $i$.
• For subtasks $i\in\{6,7\}$, you need to solve all subtasks $j\in[1,i]$ correctly to get the score for subtask $i$.

Translated by ChatGPT 5