AT_abc454_g [ABC454G] Mode in the Subtree

頂点に $ 1 $ から $ N $ の番号がついた $ N $ 頂点の根付き木が与えられます。頂点 $ 1 $ が根で、頂点 $ i $ の親は頂点 $ p_i $ です( $ p_i \lt i $ )。 各頂点には色が塗られていて、頂点 $ i $ は色 $ c_i $ で塗られています( $ 1 \leq c_i \leq N $ )。 $ v = 1, 2, \dots, N $ について次の問題を解いてください。 > $ f_i $ を「頂点 $ v $ の部分木に含まれる頂点のうち色 $ i $ で塗られた頂点の個数」とします。 > > - 数列 $ (f_1, f_2, \dots, f_N) $ に含まれる値の最大値 $ m $ 、および > - $ f_i = m $ であるような $ N $ 以下の正整数 $ i $ の個数 $ k $ > > を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ \mathrm{seed} $ $ M $ $ F $ $ q_2 $ $ q_3 $ $ \dots $ $ q_M $ $ d_1 $ $ d_2 $ $ \dots $ $ d_M $

$ \left(\displaystyle \sum_{i=1}^N (m_i \oplus i)\times (k_i \oplus i)\right) \bmod 998244353 $ を出力せよ。

### 入出力の形式 今回の問題の入出力は特殊な形式で行われます。 #### 入力の形式 標準入力からは整数 $ N $ に加えて整数 $ \mathrm{seed}, M, F $ および $ q_2, q_3, \dots, q_M $ , $ d_1, d_2, \dots, d_M $ が与えられます。この時、以下の擬似コードで表される計算によって $ p_2, p_3, \dots, p_N $ および $ c_1, c_2, \dots, c_N $ を復元してください。(ここで `2^31` は $ 2^{31}=2147483648 $ を意味します。また、 $ \mathrm{state} $ は変数である点、および $ \mathrm{state} $ の計算に $ 64 $ bit 整数型が必要である点に注意してください。) ``` state = seed for i=2 to N: if i