Vous adorez le bowling : tous les week-ends, vous faites quelques parties avec vos amis. Ce week-end, vous décidez d'organiser un petit tournoi chez vous, et de parier sur le score qu'atteindra chacun des participants. Vous pouvez regarder les joueurs lorsqu'ils lancent la boule, et prévoir la trajectoire de celle-ci, mais de là où vous êtes, il est difficile de déterminer sans erreur combien de quilles la boule fait tomber à l'autre bout de la salle. Vous décidez donc d'écrire un programme qui le calcule pour chaque boule.

Toutes les boules sont envoyées bien parallèlement aux bords de la piste, et leurs trajectoires ne sont pas perturbées par les quilles. De plus, il se trouve que ces joueurs utilisent des quilles spéciales qui ne peuvent pas se faire tomber mutuellement. La partie de bowling se passe chez vous, dans une salle que vous avez spécialement aménagée. Il n'y a pas de machine pour remettre les quilles en place, donc entre chaque lancer, les quilles tombées ne sont pas remplacées. De plus, la salle ne dispose pas de pistes bien séparées, donc les quilles sont partagées par tous les joueurs.

On vous donne les abscisses initiales de Q quilles dans un repère dont l'origine est le coin bas gauche de la salle. On vous décrit également chacun des N lancers par l'abscisse du centre de la boule et son rayon (chacun a une boule adaptée à sa force). Vous devez, pour chaque lancer, déterminer le nombre de quilles qui tombent. Si une quille se trouve sur le chemin de la boule, même au bord, elle tombe.

• 2 <= L <= 1 000 000, où L est la largeur de la piste.
• 1 <= Q <= 100 000, où Q est le nombre de quilles placées au départ.
• 1 <= N <= 100 000, où N est le nombre de boules lancées.
• 0 < X_i < L, où X_i est l'abscisse de la quille i.
• 1 <= R_j, avec 2R_j <= L, où R_j est le rayon de la j^ème boule lancée.
• R_j <= B_j <= L - R_j, où B_j l'abscisse du centre de la j^ème boule lancée.

De plus, dans 40% des tests, on a L <= 10 000, Q <= 1 000 et N <= 1 000.

• La première ligne de l'entrée contient deux entiers : la largeur L de la piste, et le nombre Q de quilles au départ.
• La deuxième ligne contient Q entiers séparés par des espaces : les abscisses X_i des quilles, dans l'ordre croissant. Plusieurs quilles peuvent avoir la même abscisse.
• La troisième ligne contient un entier : le nombre N de boules lancées
• Les N lignes suivantes décrivent les boules lancées, dans l'ordre. Chaque ligne contient deux entiers séparés par un espace : le rayon R_j de la boule, et l'abscisse B_j de son centre

Squelette de code C++ :

#include <cstdio>

int main()
{
   int largeur, nbQuilles, nbBoules;
   scanf("%d%d", &largeur, &nbQuilles);
   for (int quille = 0; quille < nbQuilles; quille++)
   {
      int xQuille;
      scanf("%d", &xQuille);
		...
   }
   scanf("%d", &nbBoules);
   for (int boule = 0; boule < nbBoules; boule++)
   {
      int rBoule, xBoule;
      scanf("%d%d", &rBoule, &xBoule);
      int nbQuillesTouches = ...;
      printf("%d\n", nbQuillesTouches);
   }
}

open Printf
let scan_int () = Scanf.scanf " %d" (fun x -> x)
let scan_2int () = Scanf.scanf " %d %d" (fun x y -> x,y)

let larguer = scan_int() 
let nb_quilles = scan_int()
let quilles = Array.init nb_quilles (fun _ -> scan_int())
let nb_boules = scan_int() 
let boules = Array.init nb_boules (fun _ -> scan_2int())

(* Le tableau quilles contient les abscisses des quilles,
   et le tableau boules contient des paires de la forme
   (rayon_boule, abscisse_boule) décrivant chaque boule. *)

let _ =
   (* pour chaque boule, faire : *)
      let nbQuillesTouchees = ... in
      printf "%d\n" nbQuillesTouchees