English · Original
Chinese · Translation
Formal · Original
Perhaps many have heard that the World Biathlon Championship has finished. Although our hero Valera was not present at this spectacular event himself and only watched it on TV, it excited him so much that he decided to enroll in a biathlon section.
Of course, biathlon as any sport, proved very difficult in practice. It takes much time and effort. Workouts, workouts, and workouts, — that's what awaited Valera on his way to great achievements in biathlon.
As for the workouts, you all probably know that every professional biathlete should ski fast and shoot precisely at the shooting range. Only in this case you can hope to be successful, because running and shooting are the two main components of biathlon. Valera has been diligent in his ski trainings, which is why he runs really fast, however, his shooting accuracy is nothing to write home about.
On a biathlon base where Valera is preparing for the competition, there is a huge rifle range with _n_ targets. Each target have shape of a circle, and **the center of each circle is located on the _Ox_ axis**. At the last training session Valera made the total of _m_ shots. To make monitoring of his own results easier for him, one rather well-known programmer (of course it is you) was commissioned to write a program that would reveal how many and which targets Valera hit. More specifically, for each target the program must print the number of **the first** successful shot (in the target), or "-1" if this was not hit. **The target is considered hit if the shot is inside the circle or on its boundary.** Valera is counting on you and perhaps, thanks to you he will one day win international competitions.
## Input
The first line of the input file contains the integer _n_ (1 ≤ _n_ ≤ 104), which is the number of targets. The next _n_ lines contain descriptions of the targets. Each target is a circle whose center is located on the _Ox_ axis. Each circle is given by its coordinate of the center _x_ ( - 2·104 ≤ _x_ ≤ 2·104) and its radius _r_ (1 ≤ _r_ ≤ 1000). **It is guaranteed that no two targets coincide, intersect or are nested into each other, but they can touch each other.**
The next line contains integer _m_ (1 ≤ _m_ ≤ 2·105), which is the number of shots. Next _m_ lines contain descriptions of the shots, which are points on the plane, given by their coordinates _x_ and _y_ ( - 2·104 ≤ _x_, _y_ ≤ 2·104).
All the numbers in the input are integers.
Targets and shots are numbered starting from one in the order of the input.
## Output
Print on the first line a single number, the number of targets hit by Valera. Print on the second line for each of the targets the number of its first hit or "-1" (without quotes) if this number does not exist. Separate numbers with spaces.
[samples]
[{"iden":"statement","content":"也许很多人听说过世界冬季两项锦标赛已经结束。虽然我们的英雄瓦莱拉本人并未亲临这一盛事，只是在电视上观看，但这一赛事让他无比兴奋，决定报名参加冬季两项训练班。\n\n当然，像任何运动一样，冬季两项在实践中非常困难。它需要大量时间和精力。训练，训练，还是训练——这就是瓦莱拉在通往冬季两项卓越成就之路上所面对的一切。\n\n至于训练，你们可能都知道，每位专业冬季两项运动员必须快速滑雪并精准射击。只有这样，你才有可能成功，因为滑雪和射击是冬季两项的两大主要组成部分。瓦莱拉在滑雪训练上非常勤奋，因此他滑得非常快，但他的射击精度却乏善可陈。\n\n在瓦莱拉备战比赛的冬季两项基地，有一个巨大的靶场，共有 #cf_span[n] 个靶子。每个靶子都是一个圆形，且每个圆的圆心都位于 #cf_span[Ox] 轴上。在最近一次训练中，瓦莱拉共进行了 #cf_span[m] 次射击。为了便于他自己监控成绩，一位相当知名的程序员（当然就是你）被委托编写一个程序，用于揭示瓦莱拉击中了多少个靶子以及具体击中了哪些靶子。更具体地说，对于每个靶子，程序必须输出首次击中该靶子的射击编号，若未击中则输出 \"-1\"。*若射击点位于圆内或圆周上，则认为该靶子被击中。* 瓦莱拉正指望你，也许在你的帮助下，他终有一天能在国际比赛中夺冠。\n\n输入文件的第一行包含整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 104])，表示靶子数量。接下来的 #cf_span[n] 行描述了每个靶子。每个靶子是一个圆心位于 #cf_span[Ox] 轴上的圆，由圆心坐标 #cf_span[x] (#cf_span[ - 2·104 ≤ x ≤ 2·104]) 和半径 #cf_span[r] (#cf_span[1 ≤ r ≤ 1000]) 给出。*保证任意两个靶子互不重合、不相交、不嵌套，但可以相切。*\n\n下一行包含整数 #cf_span[m] (#cf_span[1 ≤ m ≤ 2·105])，表示射击次数。接下来的 #cf_span[m] 行描述了每次射击，即平面上的点，由其坐标 #cf_span[x] 和 #cf_span[y] (#cf_span[ - 2·104 ≤ x, y ≤ 2·104]) 给出。\n\n输入中的所有数字均为整数。\n\n靶子和射击按输入顺序从 1 开始编号。\n\n第一行输出一个数字，表示瓦莱拉击中的靶子数量。第二行输出每个靶子的首次命中编号，若未被命中则输出 \"-1\"（不含引号）。数字之间用空格分隔。\n"},{"iden":"input","content":"输入文件的第一行包含整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 104])，表示靶子数量。接下来的 #cf_span[n] 行描述了每个靶子。每个靶子是一个圆心位于 #cf_span[Ox] 轴上的圆，由圆心坐标 #cf_span[x] (#cf_span[ - 2·104 ≤ x ≤ 2·104]) 和半径 #cf_span[r] (#cf_span[1 ≤ r ≤ 1000]) 给出。*保证任意两个靶子互不重合、不相交、不嵌套，但可以相切。* 下一行包含整数 #cf_span[m] (#cf_span[1 ≤ m ≤ 2·105])，表示射击次数。接下来的 #cf_span[m] 行描述了每次射击，即平面上的点，由其坐标 #cf_span[x] 和 #cf_span[y] (#cf_span[ - 2·104 ≤ x, y ≤ 2·104]) 给出。输入中的所有数字均为整数。靶子和射击按输入顺序从 1 开始编号。"},{"iden":"output","content":"第一行输出一个数字，表示瓦莱拉击中的靶子数量。第二行输出每个靶子的首次命中编号，若未被命中则输出 \"-1\"（不含引号）。数字之间用空格分隔。"},{"iden":"examples","content":"输入\n3\n2 1\n5 2\n10 1\n5\n0 1\n1 3\n3 0\n4 0\n4 0\n\n输出\n2\n3 3 -1\n\n输入\n3\n3 2\n7 1\n11 2\n4\n2 1\n6 0\n6 4\n11 2\n\n输出\n3\n1 2 4 "}],"time_limit":1000,"memory_limit":262144}
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of targets.
For each target $ i \in \{1, \dots, n\} $, define a circle $ C_i $ with center $ (x_i, 0) $ and radius $ r_i $, where $ x_i, r_i \in \mathbb{Z} $.
Let $ m \in \mathbb{Z}^+ $ be the number of shots.
For each shot $ j \in \{1, \dots, m\} $, define a point $ p_j = (x_j, y_j) \in \mathbb{Z}^2 $.
**Constraints**
1. $ 1 \leq n \leq 10^4 $
2. $ -2 \cdot 10^4 \leq x_i \leq 2 \cdot 10^4 $, $ 1 \leq r_i \leq 1000 $ for all $ i \in \{1, \dots, n\} $
3. $ 1 \leq m \leq 2 \cdot 10^5 $
4. $ -2 \cdot 10^4 \leq x_j, y_j \leq 2 \cdot 10^4 $ for all $ j \in \{1, \dots, m\} $
5. No two circles intersect or are nested; they may only touch.
**Objective**
For each target $ i \in \{1, \dots, n\} $, define:
$$
f(i) = \min \left\{ j \in \{1, \dots, m\} \mid (x_j - x_i)^2 + y_j^2 \leq r_i^2 \right\}
$$
If no such $ j $ exists, set $ f(i) = -1 $.
Compute:
- The count $ H = \left| \left\{ i \in \{1, \dots, n\} \mid f(i) \neq -1 \right\} \right| $
- The sequence $ (f(1), f(2), \dots, f(n)) $
Output $ H $, followed by the sequence $ f(1), f(2), \dots, f(n) $.
API Response (JSON)
{
"problem": {
"name": "C. Biathlon",
"description": {
"content": "Perhaps many have heard that the World Biathlon Championship has finished. Although our hero Valera was not present at this spectacular event himself and only watched it on TV, it excited him so much ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 1000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF84C"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Perhaps many have heard that the World Biathlon Championship has finished. Although our hero Valera was not present at this spectacular event himself and only watched it on TV, it excited him so much ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "[{\"iden\":\"statement\",\"content\":\"也许很多人听说过世界冬季两项锦标赛已经结束。虽然我们的英雄瓦莱拉本人并未亲临这一盛事，只是在电视上观看，但这一赛事让他无比兴奋，决定报名参加冬季两项训练班。\\n\\n当然，像任何运动一样，冬季两项在实践中非常困难。它需要大量时间和精力。训练，训练，还是训练——这就是瓦莱拉在通往冬季两项卓越成就之路上所面对的一切。\\n\\n至于训练，你们可...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the number of targets. \nFor each target $ i \\in \\{1, \\dots, n\\} $, define a circle $ C_i $ with center $ (x_i, 0) $ and radius $ r_i $, where $ x_i, r_...",
"is_translate": false,
"language": "Formal"
}
]
}