Para resolver este problema trazaremos las rectas (imaginariamente) desde todos los puntos que pueden existir en la cuadrícula hacia el origen. Dichas rectas, además de pasar siempre por el origen, la coordenada $(x_2 = 0, y_2 = 0)$, también deberán pasar por el punto $(x_1 = x, y_2 = y)$ donde $0 ≤ x, y ≤ N$. Recordemos la ecuación de la recta: $(x_2 - x_1) / (y_2 - y_1) + b$, por tanto para nuestras rectas la ecuación se reducirá a $x / y$.

Podemos ver que algo sucede con los puntos que no son visibles, y es que la recta que los une puede ser expresada por un múltiplo de la recta de uno que si es visible. El caso más sencillo: tomando el punto visible $(1, 1)$ y el punto no visible $(3, 3)$, tenemos que las coordenadas del punto no visible es tan solo $(3 * 1) / (3 * 1)$, la forma para identificar esto es obtener el MCD de $x$ y $y$, mientras que para el punto visible $MCD(x, y) = 1$, para el no visible $MCD(x, y) > 1$.

Ahora solo hay que obtener todos los puntos dentro de nuestra cuadrícula cuyo MCD sea igual a 1 para cada consulta que nos hagan. Esto es sencillo pero es un gasto inecesario de recursos, por lo que lo mejor es realizar un precálculo partiendo de que para $N = 0$ la respuesta es $0$ y para $N = 1$ la respuesta es $3$. Otro punto a considerar es que podemos solo calcular la mitad de los puntos ya que los puntos son simétricos.

a[0] = 0;
a[1] = 3;
for(int x = 2; x <= 1000; x++){
 int sum = 0;
 for(int y = 1; y < x; y++){
  if(mcd(x,y) == 1) sum++;
 }
 a[x] = a[x-1] + 2 * sum;
}

Entrada:	Representación:	Explicación:
5 4 1 2 3 2 4 5 4 5		Las aristas rojas nos indican que la suricata 3 creó un camino hacia el cuarto 2, mientras que la suricata 2 creó un camino hacia el cuarto 1. Las aristas azules nos indican que la suricata 3 creó un camino hacia el cuarto 2, mientras que la suricata 1 también creó un camino hacia el cuarto 2 y así sucesivamente.

// Join function
void join(int i, int j){
 int pi = root(i);
 int pj = root(j);
 E[pi] += 1; // Siempre sumar una arista a nuestra componente
 if(pi != pj){
  G[pj] = G[pi];
  V[pi] += V[pj];
  E[pi] += E[pj];
 }
}

// Root function
int root(int n){
 if(G[n] != n) 
  G[n] = root(G[n]);
 return G[n];
}

var res := 1
foreach i in K
 if E[i] = V[i]
  res := res * 2
 elsif E[i] = V[i] - 1
  res := res * N
 else
  res := 0
end foreach
print res mod 1000000007

• $B1$ := Sumatoria de todos los $b = a_x - a_y$ tal que $x > y$ y $b > 0$
• $B2$ := Sumatoria de todos los $b = a_x - a_y$ tal que $x > y$ y $b < 0$

• Para el paso 4 tenemos: $B1 = (3 -0) + (3 - 1) + (3 - 2) = 6$ y $B2 = 0$ lo cual nos da el valor de $6$
• Para el paso 8 tenemos: $B1 = (3 - 0) + (3 - 1)+  (3 - 2) + (3 - 1) + (3 - 2) = 9$ y $B2 = (3 - 5) = - 2$, por lo tanto tenemos $B1 - B2 = 11$

void precalc(){
 int t = 0;
 for(int step = 0; step < n; step++){
  int ans = 0;
  for(int i = step-1; i >= 0; i--){
   t = (s[step] - '0') - (s[i] - '0');
   if(t == 0){
    ans += A[i];
    A[step] = ans;
    break;
   }
   ans += abs(t);
   A[step] = ans;
  }
 }
}

int main(){
 scanf("%d%d",&n,&m);
 scanf("%s",s);
 precalc();
 while(m--){
  scanf("%d",&q);
  printf("%d\n", A[q-1]);
 }
 return 0;
}