{"problem":{"name":"K. K-pop","description":{"content":"Clodes is a student that is crazy about K-pop like no other person in the world. He has a grandma who loves him a lot and wishes to reward him for his outstanding grades and performance on his studies","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10202K"},"statements":[{"statement_type":"Markdown","content":"Clodes is a student that is crazy about K-pop like no other person in the world. He has a grandma who loves him a lot and wishes to reward him for his outstanding grades and performance on his studies. To do so, his grandma decided to give him a gift: she will pay for him and his friends to attend a K-pop event, that is going to happen in another city.\n\nClodes, then, while planning his trip, was looking through a total of $N$ different cities, when he found $M$ available flights connecting two cities, where the $i$-th of them leaves from city $u_i$, lands at city $v_i$, costs $P_i$ taokeis (the currency of Clodes' country) and has $A_i$ available seats on the plane. Clodes doesn't want to be apart of his friends, therefore, all of his friends must go on the same flight as him. Therefore, Clodes seeks a sequence of flights starting at $O$, the city he lives in, and ends at $D$, the city where the K-pop event wil happen. Every flight of this sequence must have room for all his friends.\n\nThere is one more thing. Clodes loves number theory. Even more than his friends do. Because of that, he decided that he wants to take a prime number of friends on the trip with him, including himself on that count, because Clodes considers himself his friend.\n\nBut life is not easy, specially for Clodes, since he chose to do his graduation on Computer Engineering, instead of Computer Science. He is full of exams this week and needs to study, thus, he doesn't have any more time available to plan his trip and wants your help. He wants you to calculate the minimum amount of money his grandma needs to spend in order to get him and his friends to the event, where the total number of people (Clodes and his friends) is the highest prime possible.\n\nTo help you with your difficult task, Clodes decided to formalize the problem before going to study:\n\n_Warning: large input, it is recommended to use fast I/O._\n\nThe first line of input contains four integers $N$, $M$, $O$ and $D$ ($2 <= N <= 10^5$, $0 <= m <= 5 dot.op 10^5$, $1 <= O, D <= N$, $O != D$), being, respectively: the number of cities, the number of available flights, the city Clodes lives in and the city on which the event will hapen.\n\nThen, $M$ lines follow, where the $i$-th of them contains four integers $u_i$, $v_i$, $A_i$, $P_i$ ($1 <= u_i, v_i <= N$, $u_i != v_i$, $1 <= A_i, P_i <= 5 dot.op 10^6$), representing, respectively, the city of departure, the city of arrival, the number of available seats and the cost of the ticket (in Taokeis) of the $i$-th flight.\n\nYour program must output two integers: the number $V$ of friends Clodes will take with him on his trip, and the total value $T$ his grandma will pay so that this trip can happen.\n\n## Input\n\n_Warning: large input, it is recommended to use fast I/O._The first line of input contains four integers $N$, $M$, $O$ and $D$ ($2 <= N <= 10^5$, $0 <= m <= 5 dot.op 10^5$, $1 <= O, D <= N$, $O != D$), being, respectively: the number of cities, the number of available flights, the city Clodes lives in and the city on which the event will hapen.Then, $M$ lines follow, where the $i$-th of them contains four integers $u_i$, $v_i$, $A_i$, $P_i$ ($1 <= u_i, v_i <= N$, $u_i != v_i$, $1 <= A_i, P_i <= 5 dot.op 10^6$), representing, respectively, the city of departure, the city of arrival, the number of available seats and the cost of the ticket (in Taokeis) of the $i$-th flight.\n\n## Output\n\nYour program must output two integers: the number $V$ of friends Clodes will take with him on his trip, and the total value $T$ his grandma will pay so that this trip can happen.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T = (V, E) $ be a trie with $ V = \\{0, 1, \\dots, n\\} $, root $ 0 $, and directed edges $ E \\subseteq V \\times V \\times \\Sigma $, where $ \\Sigma $ is the set of lowercase letters. Each edge $ (u, v, c) \\in E $ satisfies $ u < v $ and for each $ u $, all outgoing edges from $ u $ have distinct characters.  \n\nLet $ S \\in \\Sigma^m $ be a string of length $ m $. For any substring $ S[l..r] = c_l c_{l+1} \\dots c_r $, define a matching process starting at node $ 0 $:  \n- For $ i = l $ to $ r $:  \n  - If there exists an edge $ (u, v, c_i) $ from current node $ u $, traverse it to $ v $.  \n  - Otherwise, increment $ \\text{CFail} $ by 1 and remain at $ u $.  \n\nLet $ \\text{Dest}(S[l..r]) \\in V $ be the final node after processing $ S[l..r] $.  \nLet $ \\text{CFail}(S[l..r]) \\in \\mathbb{Z}_{\\geq 0} $ be the total number of failed transitions.  \n\n**Constraints**  \n1. $ 1 \\leq T \\leq 1000 $  \n2. For each test case: $ 1 \\leq n, m, q \\leq 10^5 $  \n3. Total sum of $ n $, $ m $, $ q $ across all test cases $ \\leq 10^6 $  \n4. For each node $ i \\in \\{1, \\dots, n\\} $: parent $ f_i \\in \\{0, \\dots, i-1\\} $, edge character $ c_i \\in \\Sigma $  \n5. For each query: $ 1 \\leq l \\leq r \\leq m $  \n\n**Objective**  \nFor each query $ (l, r) $, compute:  \n$$\n(\\text{CFail}(S[l..r]), \\text{Dest}(S[l..r]))\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10202K","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}