Problem Background

You really like Concvssion, but that doesn't stop you from solving an interesting and not-too-difficult problem.

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

Problem Description

Given sequences \(a\) and \(b\) of length \(n\), where \(\forall i \in [1, n], a_i, b_i \in [1, n]\).

Define an operation as, \(\forall i \in [1, n], b_i \gets a_{b_i}\).

You need to perform \(n\) operations sequentially, and after each operation, compute \(\displaystyle\sum_{i=1}^n b_i\) modulo \(998244353\).

Input Format

The first line contains an integer \(n\).
The second line contains \(n\) integers representing \(a\).
The third line contains \(n\) integers representing \(b\).

Output Format

Output \(n\) lines, each containing an integer representing the answer modulo \(998244353\).

Sample Input and Output

Input Sample #1

5
2 3 4 5 1
2 2 3 1 1

Output Sample #1

14
19
19
14
9

Input Sample #2

5
3 5 1 4 2
2 2 3 1 1

Output Sample #2

17
9
17
9
17

Input Sample #3

5
1 1 2 2 4
2 2 3 1 1

Output Sample #3

6
5
5
5
5

Input Sample #4

5
3 1 5 3 4
2 2 1 3 3

Output Sample #4

15
19
20
21
19

Notes

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

Concvssion - Halv (Insane15.5)

Data Scale

This problem uses bundled testing.

For \(100\%\) of the data, \(1 \le a_i, b_i \le n \le 3 \times 10^5\).

Special Scoring Method

This problem has subtask dependencies, specifically:
- For subtask \(i \in \{1, 2, 3, 5\}\), you only need to solve subtask \(i\) to get the score for subtask \(i\).
- For subtask \(i = 4\), you need to solve all subtasks \(j \in [3, 4]\) to get the score for subtask \(i\).
- For subtask \(i \in \{6, 7\}\), you need to solve all subtasks \(j \in [1, i]\) to get the score for subtask \(i\).

见题面 Input 部分

见题面 Output 部分