P9920 "RiOI-03" Transformation, Inversion

For the needs of this problem, we redefine multiplicative functions: **it is not guaranteed that $f(1)=1$**.

**This is a non-traditional problem.** You are given a **multiplicative function** $f(d)$. For each test point, we will provide in the attachment the values of $g(n)=\sum_{d|n}f(d)$ for $k$ selected terms $\bmod\ 998244353$, and this part will also appear in the input. Then, for each test point, there are $t$ queries. For each query, an integer $d$ is given; please output the value of $f(d)\bmod 998244353$.

The first line contains $k$. Each of the next lines contains two positive integers, $d$ and $g(d)$. Then two numbers $t, id$ are given, representing the number of queries and the test point ID. For each query, one positive integer $n$ is given.

For each query, output one non-negative integer representing the answer.

#### Sample Explanation Since $g(d)=d$, we have $f(d)=\varphi(d)$, so the result is correct. #### Constraints For each test point: If you correctly answer the testdata with $n\le k$, you will get $20\%$ of the score. If you correctly answer all testdata, you will get the remaining $80\%$. **So, if you cannot answer correctly, please output a random number to keep the format correct.** #### Constraints |$\text{Id}$|$\text{Name}$|$\text{Score}$| $n\leq$|$k=$|$t=$| |:-:|:-:|:-:|:-:|:-:|:-:| |$0$|$\text{Epsilon}$|$5$|$10^6$|$100$|$10$| |$1$|$\text{Division}$|$5$|$10^9$|$100$|$10$| |$2$|$\text{Unknown}$|$5$|$10^{18}$|$1$|$10$| |$3$|$\text{Random}$|$10$|$10^5$|$10^5$|$10^5$| |$4$|$\text{Double}$|$10$|$10^9$|$100$|$10$| |$5$|$\text{Hack}$|$10$|$10^9$|$31623$|$1$| |$6$|$\text{Square}$|$15$|$10^{18}$|$100$|$5$| |$7$|$\text{Poly}$|$20$|$10^9$|$10^5$|$100$| |$8$|$\text{Thanks}$|$20$|$10^5$|$4$|$10^5$| Translated by ChatGPT 5