{"raw_statement":[{"iden":"statement","content":"Sauville has been engulfed in a devastating war with its neighboring country, Norland, for centuries. Their border can be represented as a straight horizontal line $y = 0$, where all areas for $y < 0$ belong to Sauville and all areas for $y > 0$ belong to Norland.\n\nNorland has deployed $N$ of its artilleries at position $(x_i, y_i)$ where $y_i > 0$. In addition, Norland also has built $M$ defensive walls. Each defensive wall can be represented as a tuple $angle.l x_{j 1}, x_{j 2}, y_j angle.r$, which is a horizontal line segment spanned from $(x_{j 1}, y_j)$ to $(x_{j 2}, y_j)$, where $x_{j 1} < x_{j 2}$ and $y_j > 0$. It is known to Sauville that no Norland's artillery is located at any of its defensive walls (including its endpoints), and no two artilleries are at the same position. It is also known that no two walls (including their endpoints) are sharing a common point.\n\nSauville has decided to build a watchtower to observe any suspicious activity on any Norland's artilleries. As the cost to build one watchtower is almost astronomical for Sauville, they can only afford to build one. Thus, $Q$ position candidates $(x_k, y_k)$ where $y_k < 0$ for the watchtower have been proposed. If the watchtower is built at $(x, y)$, then all artilleries which lie on the _line-of-sight_ from $(x, y)$ can be observed (visible) by the watchtower. A position $(x_i, y_i)$ lies on the line-of-sight from $(x, y)$ if and only if the straight line connecting $(x_i, y_i)$ and $(x, y)$ does not intersect with any defensive walls (including its endpoints); in other words, there should be no point $(x ', y ')$ such that $(x ', y ')$ lies on a defensive wall and also on the line segment between $(x_i, y_i)$ and $(x, y)$. Note that an artillery does not affect the visibility of any other artilleries from the watchtower.\n\nYour task in this problem is to determine the number of Norland's artilleries which can be observed from each proposed watchtower position.\n\nInput begins with a line containing three integers: $N$ $M$ $Q$ ($1 <= N <= 40000$; $0 <= M <= 5$; $1 <= Q <= 40000$) representing the number of artilleries, the number of defensive walls, and the number of proposed watchtower positions, respectively. The next $N$ lines, each contains two integers: $x_i$ $y_i$ ($-10^6 <= x_i <= 10^6$; $0 < y_i <= 10^6$) representing the position of the $i^(t h)$ artillery for $i = 1 \\\\dots N$. The next $M$ lines, each contains three integers: $x_{j 1}$ $x_{j 2}$ $y_j$ ($-10^6 <= x_{j 1} < x_{j 2} <= 10^6$; $0 < y_j <= 10^6$) representing the position of the $j^(t h)$ defensive wall for $j = 1 \\\\dots M$. The next $Q$ lines, each contains two integers: $x_k$ $y_k$ ($-10^6 <= x_k <= 10^6$; $-10^6 <= y_k < 0$) representing a proposed position for the watchtower.\n\nFor each proposed watchtower position in the same order as input, output in a line a single integer representing the number of Norland's artilleries which can be observed from the proposed position.\n\n_Explanation for the sample input/output_\n\nThe position of all artilleries, defensive walls, and proposed watchtowers are shown in the following figure.\n\n\n\n"},{"iden":"input","content":"Input begins with a line containing three integers: $N$ $M$ $Q$ ($1 <= N <= 40000$; $0 <= M <= 5$; $1 <= Q <= 40000$) representing the number of artilleries, the number of defensive walls, and the number of proposed watchtower positions, respectively. The next $N$ lines, each contains two integers: $x_i$ $y_i$ ($-10^6 <= x_i <= 10^6$; $0 < y_i <= 10^6$) representing the position of the $i^(t h)$ artillery for $i = 1 \\\\dots N$. The next $M$ lines, each contains three integers: $x_{j 1}$ $x_{j 2}$ $y_j$ ($-10^6 <= x_{j 1} < x_{j 2} <= 10^6$; $0 < y_j <= 10^6$) representing the position of the $j^(t h)$ defensive wall for $j = 1 \\\\dots M$. The next $Q$ lines, each contains two integers: $x_k$ $y_k$ ($-10^6 <= x_k <= 10^6$; $-10^6 <= y_k < 0$) representing a proposed position for the watchtower."},{"iden":"output","content":"For each proposed watchtower position in the same order as input, output in a line a single integer representing the number of Norland's artilleries which can be observed from the proposed position."},{"iden":"note","content":"_Explanation for the sample input/output_The position of all artilleries, defensive walls, and proposed watchtowers are shown in the following figure.  The first proposed watchtower $(0, -5)$ can observe $4$ artilleries, i.e. at $(0, 2)$, $(0, 15)$, $(5, 7)$, and $(45, 10)$.  The second proposed watchtower $(5, -10)$ can observe $3$ artilleries, i.e. at $(0, 2)$, $(0, 15)$, and $(45, 10)$.  The third proposed watchtower $(20, -15)$ can observe $2$ artilleries, i.e. at $(0, 2)$ and $(45, 10)$. "}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ G = (V, E) $ be a connected undirected graph with $ n = |V| $ nodes and $ m = |E| $ edges.  \nLet $ c: V \\to \\{0, 1, 2\\} $ be the initial color function:  \n- $ c(v) = 0 $: white,  \n- $ c(v) = 1 $: red,  \n- $ c(v) = 2 $: blue.  \n\nLet $ R = \\{ v \\in V \\mid c(v) = 1 \\} $, $ B = \\{ v \\in V \\mid c(v) = 2 \\} $, $ W = \\{ v \\in V \\mid c(v) = 0 \\} $.  \nIt is given that $ R \\neq \\emptyset $.\n\n**Process**  \nAt each second, every white node $ v \\in W $ with at least one non-white neighbor is recolored to the color of the neighbor with the *minimum index* among all non-white neighbors. All updates occur simultaneously. The process terminates when $ W = \\emptyset $.\n\n**Operation**  \nBefore the process starts, we may choose a set $ S \\subseteq (R \\cup B) $ such that $ |S| \\leq 2 $, and set $ c(v) \\gets 0 $ for all $ v \\in S $ (i.e., recolor at most two non-white nodes to white).\n\n**Objective**  \nMaximize $ |R_{\\text{final}}| $, the number of red nodes after the coloring process terminates, over all valid choices of $ S $.\n\n**Constraints**  \n1. $ 1 \\leq T \\leq 1024 $  \n2. $ 1 \\leq n \\leq 10^5 $, $ n-1 \\leq m \\leq 10^5 $  \n3. $ \\sum m \\leq 5 \\times 10^6 $  \n4. Graph is connected, no self-loops or multiple edges.  \n5. At least one red node exists initially.","simple_statement":"You are given a connected undirected graph with nodes colored white (0), red (1), or blue (2).  \n\nAt each second, every white node that is adjacent to at least one non-white node becomes the same color as its lowest-indexed non-white neighbor. All changes happen at once. The process stops when no white nodes remain.  \n\nBefore starting, you can change **at most two** non-white nodes (red or blue) to white.  \n\nYour goal: Maximize the final number of red nodes.  \n\nFind the maximum possible number of red nodes after the process ends.","has_page_source":false}