_... Why don't you come to the planetarium?_
_The beautiful twinkling of eternity that will never fade, no matter what._
_All the stars in the sky are waiting for you..._
A planetarium, it was once where people went to soothe their hearts by gazing at a starry sky.
And Yumemi, a planetarium guide who has been waiting for a visitor for a long time, is looking up at the stars.
Stars in the sky can be defined by their brightness, denoted by $S = {b_1, b_2, \\\\cdots, b_n}$.
Yumemi found that stars always appear in groups, and she thinks the beauty of the starry night depends on the darkest one, so she defined the beauty value as $$B(S)=\sum_{1 \leq l \leq r \leq |S|}f(l,r) \ \text{mod}\ 998244353$$ where $$f(l,r)=\min\limits_{l\leq i \leq r}\{b_i\}$$
But the night sky is not always the same. The movement of celestial bodies will make more and more stars in the night sky. The following events will happen in order every second:
At the beginning, there is no star in the sky, so $S = {}$ initially.
As time goes by, because she is not as good at calculation as before, the task will be given to you.
*Note that the sequence is given in a modified way.*
To avoid huge input, we use Linear Congruential Method to generate input data, and your solution should be *on-line*.
The first line contains six integers $n, p, x, y, z, b_1 (1 <= n <= 10^7, 2 <= p <= 10^9, 0 <= x, y, z, b_1 < p)$, indicating the number of the stars and the parameters of the data generator.
You need to generate the sequence ${b_1, b_2, \\\\cdots, b_n}$by yourself using the following formula: $$ b_{i+1}=(x\times A_i+y \times b_i + z)\ \text{mod}\ p $$ where $A_i$ is the value of $B (S)$ when $| S | = i$ .
To avoid huge output, you only need to output $\bigoplus_{1 <= i <= n} A_i$, where "$bigoplus$" denotes the bitwise XOR operation (https://en.wikipedia.org/wiki/Bitwise_operation#XOR).
In the first second, $S = {b_1} = {3}$, so $A_1 = f (1, 1) " ""mod"" "998244353 = 3$.
It can be inferred that $b_2 = (2 A_1 + 1) " ""mod"" "13 = 7$.
In the second second, $S = {b_1, b_2} = {3, 7}$, so $A_2 = [ f (1, 1) + f (2, 2) + f (1, 2) ] " ""mod"" "998244353 = 13$.
It can be inferred that $b_3 = (2 A_2 + 1) " ""mod"" "13 = 1$.
Keep calculating, and you will get $A_3 = 16, b_4 = 7, A_4 = 26, b_5 = 1, A_5 = 31$.
So you should output $A_1 bigoplus A_2 bigoplus A_3 bigoplus A_4 bigoplus A_5 = 27$.
## Input
To avoid huge input, we use Linear Congruential Method to generate input data, and your solution should be *on-line*.The first line contains six integers $n, p, x, y, z, b_1 (1 <= n <= 10^7, 2 <= p <= 10^9, 0 <= x, y, z, b_1 < p)$, indicating the number of the stars and the parameters of the data generator. You need to generate the sequence ${b_1, b_2, \\\\cdots, b_n}$by yourself using the following formula: $$ b_{i+1}=(x\times A_i+y \times b_i + z)\ \text{mod}\ p $$ where $A_i$ is the value of $B (S)$ when $| S | = i$ .
## Output
To avoid huge output, you only need to output $bigoplus limits_{1 <= i <= n} A_i$, where "$bigoplus$" denotes the bitwise XOR operation (https://en.wikipedia.org/wiki/Bitwise_operation#XOR).
[samples]
## Note
In the first second, $S = {b_1} = {3}$, so $A_1 = f (1, 1) " ""mod"" "998244353 = 3$. It can be inferred that $b_2 = (2 A_1 + 1) " ""mod"" "13 = 7$.In the second second, $S = {b_1, b_2} = {3, 7}$, so $A_2 = [ f (1, 1) + f (2, 2) + f (1, 2) ] " ""mod"" "998244353 = 13$.It can be inferred that $b_3 = (2 A_2 + 1) " ""mod"" "13 = 1$.Keep calculating, and you will get $A_3 = 16, b_4 = 7, A_4 = 26, b_5 = 1, A_5 = 31$.So you should output $A_1 bigoplus A_2 bigoplus A_3 bigoplus A_4 bigoplus A_5 = 27$.
**Definitions**
Let $ G = (V, E) $ be a tree with $ n $ vertices and $ n-1 $ edges.
Let $ E = \{e_1, e_2, \dots, e_{n-1}\} $ be the set of edges, where each edge $ e_i = (u_i, v_i, w_i) $ has weight $ w_i $ (security level).
For each vertex $ u \in V $, a meeting is held at $ u $. For every other vertex $ v \ne u $, the representative from $ v $ travels along the unique shortest (and only) path from $ v $ to $ u $. On the return trip (from $ u $ to $ v $), the representative hides a copy of the information in the edge(s) with **maximum security level** along the path $ v \to u $.
Let $ c(e_i) $ denote the number of information copies hidden in edge $ e_i $ across all meetings.
**Constraints**
1. $ 2 \le n \le 2 \cdot 10^5 $
2. Each edge weight $ w_i \in [1, 10^9] $
3. The graph is a tree.
**Objective**
Compute:
- $ m = \max_{e_i \in E} c(e_i) $: the maximum number of information copies hidden in any edge.
- $ k $: the number of edges achieving this maximum.
- The list of edge indices $ i $ (in increasing order) such that $ c(e_i) = m $.
**Key Insight**
For an edge $ e = (u, v) $, removing $ e $ splits the tree into two connected components of sizes $ s $ and $ n - s $.
The edge $ e $ lies on the unique path between any vertex in one component and any vertex in the other.
Thus, for every meeting at a vertex in one component, representatives from the other component must traverse $ e $.
For each such path, if $ e $ is the **unique maximum-weight edge** on that path, it receives one copy.
If there are ties for maximum weight on the path, copies are hidden on **all** such maximum-weight edges.
But note: **Each meeting at $ u $ causes every other vertex $ v $ to send a representative along the $ v \to u $ path, who hides info on the max-weight edge(s) on that path.**
So, for a fixed edge $ e $, we count the number of pairs $ (u, v) $, $ u \ne v $, such that the path from $ u $ to $ v $ includes $ e $, and $ e $ is one of the edges with maximum weight on that path.
This is equivalent to:
For each edge $ e_i $, let $ s_i $ be the size of the smaller component after removing $ e_i $. Then the number of paths crossing $ e_i $ is $ s_i \cdot (n - s_i) $.
But **only those paths where $ e_i $ is a maximum-weight edge on the path** contribute to $ c(e_i) $.
**Crucial Observation**:
If we process edges in **decreasing order of weight**, and use Union-Find to dynamically merge components, then when we process edge $ e_i $ with weight $ w_i $, **all previously processed edges have weight $ \ge w_i $**.
So, for the current edge $ e_i $, the number of paths for which $ e_i $ is a **maximum-weight edge** is exactly the number of paths crossing it: $ s_i \cdot (n - s_i) $, because **any path crossing $ e_i $ cannot have a heavier edge** (since we process in descending order, heavier edges are already merged and not on the path anymore — actually, we need to think differently).
Actually, standard solution for this problem:
The number of times an edge $ e $ with weight $ w $ is the **unique** maximum on a path is $ s \cdot (n - s) $, **only if** no other edge on those paths has weight $ \ge w $.
But the problem says: if multiple edges tie for maximum weight on a path, **each** gets a copy.
So: for a given edge $ e $, it receives a copy for **every path** that contains it **and** for which $ w_e $ is the **maximum** weight on that path.
So we can do:
- Sort edges by weight in **descending** order.
- Use DSU to maintain connected components.
- For edge $ e_i $ with weight $ w_i $, connecting components of size $ s_1 $ and $ s_2 $:
The number of paths that have $ e_i $ as a **maximum-weight edge** is $ s_1 \cdot s_2 $.
Why? Because any path from a node in $ s_1 $ to a node in $ s_2 $ must go through $ e_i $, and since we process in descending order, all other edges on these paths have weight $ \le w_i $, so $ w_i $ is the maximum. And since we are processing in descending order, we are counting exactly the paths where $ w_i $ is the **maximum** (and if there are ties, they will be counted when we process the tied edges — each edge gets its own count).
But note: if two edges have the same weight, and both lie on a path, then **both** get a copy for that path. So we must process edges of the same weight **together**.
Thus:
Group edges by weight (descending). For each distinct weight $ w $, process all edges of weight $ w $ simultaneously:
- For each such edge $ e $, temporarily ignore it, compute the sizes of the two components it would connect (using DSU with edges of strictly greater weight already merged).
- The number of paths for which this edge is a **maximum-weight edge** is $ s_1 \cdot s_2 $.
- Then merge the components.
So:
Let $ c(e_i) = s_1 \cdot s_2 $, where $ s_1, s_2 $ are sizes of components connected by $ e_i $, **after merging all edges with strictly higher weight**.
Then:
- $ m = \max c(e_i) $
- $ k = \# \{ e_i \mid c(e_i) = m \} $
- Output $ m, k $, and the sorted list of indices $ i $ where $ c(e_i) = m $
**Final Formal Statement**
**Definitions**
Let $ G = (V, E) $ be a tree with $ |V| = n $, $ |E| = n-1 $.
Let $ E = \{e_1, e_2, \dots, e_{n-1}\} $, where $ e_i = (u_i, v_i, w_i) $, and edges are indexed by input order.
For each edge $ e_i $, define:
- $ c(e_i) = $ number of unordered pairs $ \{u, v\} \subseteq V $, $ u \ne v $, such that the unique path from $ u $ to $ v $ contains $ e_i $, and $ w_i $ is the **maximum** weight among all edges on that path.
**Constraints**
1. $ 2 \le n \le 2 \cdot 10^5 $
2. $ 1 \le w_i \le 10^9 $
3. $ G $ is a tree.
**Objective**
Compute:
- $ m = \max_{1 \le i \le n-1} c(e_i) $
- $ k = \left| \left\{ i \in \{1, \dots, n-1\} \mid c(e_i) = m \right\} \right| $
- The sorted list of indices $ i $ such that $ c(e_i) = m $
**Computation Method**
Sort edges by weight in descending order, breaking ties arbitrarily.
Use DSU to maintain component sizes.
Process edges in this sorted order:
For each edge $ e_i $ with weight $ w $:
- Let $ s_1, s_2 $ be the sizes of the components containing $ u_i $ and $ v_i $ before merging.
- Set $ c(e_i) = s_1 \cdot s_2 $
- Merge the two components.
Then output $ m, k $, and sorted indices $ i $ with $ c(e_i) = m $.