{"raw_statement":[{"iden":"statement","content":"Chi is a little kid that goes to a middle school in London, Ontario. He is in a band, and they are planning on performing this weekend. There are $N$ members in this band, and each one is categorized by the id of the instrument that they play, represented by a number $V$, and their ability level represented by a number $P$. \n\nThe enjoyment of a performance depends on the order in which people play, and their ability levels. The playing order goes as follows: *the order of people presenting has to be in the order of their instrument's id, from smallest to largest*, and in case of ties any order of the people with the same instrument is valid. If two people in a row are playing the same instrument, the enjoyment level doesn't change. If two people in a row have different instruments, the enjoyment increases by the absolute diference of their ability levels, because people like to see very different kinds of performances even if the ability level decreases.\n\nChi wants to have the best performance ever, and he asked your help with this task. He wants to know what is the highest enjoyment of the performance, given an optimal ordering.\n\nThe first line will have an integer $N$ $(1 <= N <= 10^6)$. $N$ lines will follow. The $i$-th line will contain two integers $V_i$ $(1 <= V_i <= 10^9)$ and $P_i$ $(0 <= P_i <= 10^9)$ each, representing the $i$-th person's instrument id and ability level respectively. \n\nPrint a single number, representing the highest enjoyment possible of the performance, given an optimal ordering of the players.\n\n"},{"iden":"input","content":"The first line will have an integer $N$ $(1 <= N <= 10^6)$. $N$ lines will follow. The $i$-th line will contain two integers $V_i$ $(1 <= V_i <= 10^9)$ and $P_i$ $(0 <= P_i <= 10^9)$ each, representing the $i$-th person's instrument id and ability level respectively. "},{"iden":"output","content":"Print a single number, representing the highest enjoyment possible of the performance, given an optimal ordering of the players."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ denote the number of boxes and number of operations, respectively.  \nLet $ B = (B_1, B_2, \\dots, B_n) $ be a tuple of multisets, where $ B_i $ contains integers written on paper strips in box $ i $.  \n\nFor an operation of type 1 (by _wang9897_):  \n- Given $ x_i \\in \\{1, \\dots, 9\\} $, $ l_i, r_i \\in \\mathbb{Z} $, $ c_i \\in \\mathbb{Z}_{\\ge 0} $,  \n- For each $ k \\in \\{1, 2, \\dots, r_i - l_i + 1\\} $:  \n  - Let $ d_k = \\overline{\\underbrace{x_i x_i \\dots x_i}_{c_i + k \\text{ digits}}} = x_i \\cdot \\frac{10^{c_i + k} - 1}{9} $,  \n  - Add $ d_k $ to $ B_{l_i + k - 1} $.  \n\nFor an operation of type 2 (by _qkoqhh_):  \n- Given $ l_i, r_i \\in \\mathbb{Z} $,  \n- Let $ S = \\bigcup_{j = l_i}^{r_i} B_j $ be the multiset of all paper strips in boxes $ l_i $ to $ r_i $,  \n- Let $ |S| $ be the total number of strips in this range.  \n\n**Constraints**  \n1. $ 1 \\le n \\le 10^4 $, $ 1 \\le m \\le 10^5 $  \n2. $ 1 \\le l_i \\le r_i \\le n $  \n3. $ 1 \\le x_i \\le 9 $, $ 0 \\le c_i \\le 10^9 $  \n4. All arithmetic is modulo $ M = 1000000007 $  \n\n**Objective**  \nFor each type-2 operation:  \n- If $ |S| = 0 $, output $ 0 $.  \n- Else, compute the expectation:  \n  $$\n  E = \\frac{1}{|S|} \\sum_{v \\in S} v \\mod M\n  $$  \n  Output $ E \\equiv \\left( \\sum_{v \\in S} v \\right) \\cdot |S|^{-1} \\mod M $,  \n  where $ |S|^{-1} $ is the modular multiplicative inverse of $ |S| $ modulo $ M $.","simple_statement":"You are given n boxes in a line. Two types of operations:\n\n1. **Type 1 (Master _wang9897_)**: Choose digit x (1–9), range [l, r], and count c.  \n   For each k from 1 to (r - l + 1), put a number with (c + k) digits, all equal to x, into box (l + k - 1).  \n   Example: x=5, c=1, l=1, r=3 → put \"55\" in box 1, \"555\" in box 2, \"5555\" in box 3.\n\n2. **Type 2 (Master _qkoqhh_)**: Choose range [l, r]. Randomly pick one paper strip from any box in [l, r].  \n   All strips have equal chance. Output the **expected value** of the picked number, modulo 1000000007.  \n   If no strips exist, output 0.\n\nYou must handle multiple test cases until EOF.","has_page_source":false}