{"raw_statement":[{"iden":"statement","content":"_... Why don't you come to the planetarium?_\n\n_The beautiful twinkling of eternity that will never fade, no matter what._\n\n_All the stars in the sky are waiting for you..._\n\n \n\n A planetarium, it was once where people went to soothe their hearts by gazing at a starry sky. \n\nAnd Yumemi, a planetarium guide who has been waiting for a visitor for a long time, is looking up at the stars.\n\nStars in the sky can be defined by their brightness, denoted by $S = {b_1, b_2, \\\\\\\\cdots, b_n}$.\n\nYumemi 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\\}$$\n\nBut 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:\n\nAt the beginning, there is no star in the sky, so $S = {}$ initially.\n\nAs time goes by, because she is not as good at calculation as before, the task will be given to you.\n\n*Note that the sequence is given in a modified way.*\n\nTo avoid huge input, we use Linear Congruential Method to generate input data, and your solution should be *on-line*.\n\nThe 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. \n\nYou 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$ .\n\nTo 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).\n\nIn the first second, $S = {b_1} = {3}$, so $A_1 = f (1, 1) \" \"\"mod\"\" \"998244353 = 3$. \n\nIt can be inferred that $b_2 = (2 A_1 + 1) \" \"\"mod\"\" \"13 = 7$.\n\nIn 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$.\n\nIt can be inferred that $b_3 = (2 A_2 + 1) \" \"\"mod\"\" \"13 = 1$.\n\nKeep calculating, and you will get $A_3 = 16, b_4 = 7, A_4 = 26, b_5 = 1, A_5 = 31$.\n\nSo you should output $A_1 bigoplus A_2 bigoplus A_3 bigoplus A_4 bigoplus A_5 = 27$.\n\n"},{"iden":"input","content":"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$ ."},{"iden":"output","content":"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)."},{"iden":"note","content":"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$."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ G = (V, E) $ be a tree with $ n $ vertices and $ n-1 $ edges.  \nLet $ 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).  \n\nFor 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 $.  \n\nLet $ c(e_i) $ denote the number of information copies hidden in edge $ e_i $ across all meetings.\n\n**Constraints**  \n1. $ 2 \\le n \\le 2 \\cdot 10^5 $  \n2. Each edge weight $ w_i \\in [1, 10^9] $  \n3. The graph is a tree.\n\n**Objective**  \nCompute:  \n- $ m = \\max_{e_i \\in E} c(e_i) $: the maximum number of information copies hidden in any edge.  \n- $ k $: the number of edges achieving this maximum.  \n- The list of edge indices $ i $ (in increasing order) such that $ c(e_i) = m $.\n\n**Key Insight**  \nFor an edge $ e = (u, v) $, removing $ e $ splits the tree into two connected components of sizes $ s $ and $ n - s $.  \nThe edge $ e $ lies on the unique path between any vertex in one component and any vertex in the other.  \nThus, for every meeting at a vertex in one component, representatives from the other component must traverse $ e $.  \nFor each such path, if $ e $ is the **unique maximum-weight edge** on that path, it receives one copy.  \nIf there are ties for maximum weight on the path, copies are hidden on **all** such maximum-weight edges.  \n\nBut 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.**  \n\nSo, 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.  \n\nThis is equivalent to:  \nFor 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) $.  \nBut **only those paths where $ e_i $ is a maximum-weight edge on the path** contribute to $ c(e_i) $.  \n\n**Crucial Observation**:  \nIf 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 $**.  \nSo, 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).\n\nActually, standard solution for this problem:  \nThe 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 $.  \n\nBut the problem says: if multiple edges tie for maximum weight on a path, **each** gets a copy.  \n\nSo: 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.  \n\nSo we can do:  \n- Sort edges by weight in **descending** order.  \n- Use DSU to maintain connected components.  \n- For edge $ e_i $ with weight $ w_i $, connecting components of size $ s_1 $ and $ s_2 $:  \n  The number of paths that have $ e_i $ as a **maximum-weight edge** is $ s_1 \\cdot s_2 $.  \n  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).  \n\nBut 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**.  \n\nThus:  \nGroup edges by weight (descending). For each distinct weight $ w $, process all edges of weight $ w $ simultaneously:  \n- 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).  \n- The number of paths for which this edge is a **maximum-weight edge** is $ s_1 \\cdot s_2 $.  \n- Then merge the components.  \n\nSo:  \nLet $ 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**.  \n\nThen:  \n- $ m = \\max c(e_i) $  \n- $ k = \\# \\{ e_i \\mid c(e_i) = m \\} $  \n- Output $ m, k $, and the sorted list of indices $ i $ where $ c(e_i) = m $\n\n**Final Formal Statement**\n\n**Definitions**  \nLet $ G = (V, E) $ be a tree with $ |V| = n $, $ |E| = n-1 $.  \nLet $ 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.  \n\nFor each edge $ e_i $, define:  \n- $ 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.\n\n**Constraints**  \n1. $ 2 \\le n \\le 2 \\cdot 10^5 $  \n2. $ 1 \\le w_i \\le 10^9 $  \n3. $ G $ is a tree.\n\n**Objective**  \nCompute:  \n- $ m = \\max_{1 \\le i \\le n-1} c(e_i) $  \n- $ k = \\left| \\left\\{ i \\in \\{1, \\dots, n-1\\} \\mid c(e_i) = m \\right\\} \\right| $  \n- The sorted list of indices $ i $ such that $ c(e_i) = m $\n\n**Computation Method**  \nSort edges by weight in descending order, breaking ties arbitrarily.  \nUse DSU to maintain component sizes.  \nProcess edges in this sorted order:  \nFor each edge $ e_i $ with weight $ w $:  \n- Let $ s_1, s_2 $ be the sizes of the components containing $ u_i $ and $ v_i $ before merging.  \n- Set $ c(e_i) = s_1 \\cdot s_2 $  \n- Merge the two components.\n\nThen output $ m, k $, and sorted indices $ i $ with $ c(e_i) = m $.","simple_statement":"You are given a tree with n nodes and n-1 edges. Each edge has a security level.  \n\nFor each node u, a meeting is held at u. All other nodes send a representative to u via the shortest path (only one path in a tree). On the way back, each representative hides a copy of the meeting info on the edge with the **highest security level** on their path from u back to their home node. If multiple edges have the same highest security, info is hidden on **all** of them.  \n\nYou need to find:  \n1. The **maximum number of info copies** hidden on any single edge.  \n2. How many edges have this maximum number.  \n3. The **indices** (1-based, as input order) of those edges, sorted in increasing order.","has_page_source":false}