{"raw_statement":[{"iden":"statement","content":"To help Luigi get rid of the spooky scary ghosts in the mansion, E. Gadd has created a new gadget, the Ghost Zapper '85. This gadget is able to automatically zap any ghost any distance away from it. The only catch is that zapping a ghost $x$ meters of distance away from the zapper consumes $x^2$ Watt-hours of energy. In addition, a zapper can zap as many ghost as necessary, but the energy requirements add up; zapping two ghosts, one distance $x$ away from the zapper and the other distance $z$ away, will consume $x^2 + z^2$ Watt-hours of energy in total. \n\nTo test this out, E. Gadd will mount a Zapper unit on top of every light fixture in a very long hallway. Using another gadget, he has also determined the location of every ghost along the hallway. Calculate the amount of energy needed to zap every ghost in the hallway, mod $10^9 + 7$.\n\nTwo integers, $1 <= n <= 10^5$, and $1 <= m <= 10^5$, separated by spaces on the first line.\n\n$n$ denotes the number of zappers mounted, and $m$ denotes the number of ghosts in the hallway.\n\n$n$ lines each containing an integer $0 <= z_i <= 10^7$ where $z_i$ represents the location of the $i$th zapper, and location is defined as meters away from the start of the hallway.\n\n$m$ lines each containing an integer $0 <= x_j <= 10^7$ where $x_j$ represents the location of the $j$th ghost.\n\nThe total energy required to zap every ghost in the hallway, mod $10^9 + 7$.\n\nIn example 1, there are four zappers, at locations 4, 1, 11, and 7. The first ghost at location 2 can be zapped by the zapper at location 1, costing 1 Wh. The second ghost at location 9 can be zapped by the zapper at location 7 or the one at location 11, either costing 4 Wh. The third ghost at 6 can be zapped by the zapper at 7, costing 1 Wh. The fourth ghost at 15 can be zapped by the zapper at 11, costing 16 Wh. This yields a total of 22 Wh for all ghosts.\n\nIn example 2, The first ghost can be zapped by zapper 2 yielding a cost of $(7 -5)^2 = 4$. The second ghost can be zapped by zapper 2 yielding a cost of $(5 -0)^2 = 25$. The third ghost can be zapped by zapper 2 with a cost of $(5 -5)^2 = 0$. The fourth ghost can be zapped by zapper 1, yielding a cost of $(100 -10)^2 = 8100$. The total adds up to $8129$ Wh of energy. \n\n"},{"iden":"input","content":"Two integers, $1 <= n <= 10^5$, and $1 <= m <= 10^5$, separated by spaces on the first line.$n$ denotes the number of zappers mounted, and $m$ denotes the number of ghosts in the hallway.$n$ lines each containing an integer $0 <= z_i <= 10^7$ where $z_i$ represents the location of the $i$th zapper, and location is defined as meters away from the start of the hallway.$m$ lines each containing an integer $0 <= x_j <= 10^7$ where $x_j$ represents the location of the $j$th ghost."},{"iden":"output","content":"The total energy required to zap every ghost in the hallway, mod $10^9 + 7$."},{"iden":"examples","content":"Input4 4\n4\n1\n11\n7\n2\n9\n6\n15\nOutput22\nInput2 4\n10\n5\n7\n0\n5\n100\nOutput8129\n"},{"iden":"note","content":"In example 1, there are four zappers, at locations 4, 1, 11, and 7. The first ghost at location 2 can be zapped by the zapper at location 1, costing 1 Wh. The second ghost at location 9 can be zapped by the zapper at location 7 or the one at location 11, either costing 4 Wh. The third ghost at 6 can be zapped by the zapper at 7, costing 1 Wh. The fourth ghost at 15 can be zapped by the zapper at 11, costing 16 Wh. This yields a total of 22 Wh for all ghosts.In example 2, The first ghost can be zapped by zapper 2 yielding a cost of $(7 -5)^2 = 4$. The second ghost can be zapped by zapper 2 yielding a cost of $(5 -0)^2 = 25$. The third ghost can be zapped by zapper 2 with a cost of $(5 -5)^2 = 0$. The fourth ghost can be zapped by zapper 1, yielding a cost of $(100 -10)^2 = 8100$. The total adds up to $8129$ Wh of energy. "}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z} $ be the number of zappers and ghosts, respectively.  \nLet $ Z = \\{z_1, z_2, \\dots, z_n\\} \\subset \\mathbb{Z}_{\\geq 0} $ be the set of zapper locations.  \nLet $ X = \\{x_1, x_2, \\dots, x_m\\} \\subset \\mathbb{Z}_{\\geq 0} $ be the set of ghost locations.  \n\n**Constraints**  \n1. $ 1 \\leq n, m \\leq 10^5 $  \n2. $ 0 \\leq z_i, x_j \\leq 10^7 $ for all $ i \\in \\{1, \\dots, n\\}, j \\in \\{1, \\dots, m\\} $  \n\n**Objective**  \nFor each ghost at location $ x_j $, let $ d_j = \\min_{z \\in Z} |x_j - z| $.  \nCompute the total energy:  \n$$\nE = \\sum_{j=1}^{m} d_j^2 \\mod (10^9 + 7)\n$$","simple_statement":"For each ghost, find the closest zapper and sum the squared distances, mod $10^9 + 7$.","has_page_source":false}