美丽的区间

题目描述

Orange最近迷上了完全平方数，即这个数开根号之后是一个正整数，换句话说，Orange喜欢满足以下条件的一类数 $x$:

现在有一段长度为 $n$ 的整数序列，Orange定义一个区间为美丽的区间，当且仅当这个区间内的所有数之和为一个完全平方数。同时，每个数被Orange定义了一个美丽值，即序列中所有美丽的区间，包含这个数的美丽的区间的个数。换句话说，即当前位置被多少个美丽的区间覆盖。

现在Orange会给你 $Q$ 次询问，每次询问一个位置的美丽值，你需要回答出这个值。

输入格式

输入共包含 $Q + 2$ 行，第一行为 $n(n \leq 2 \times 10^3); Q(Q\leq 3 \times 10^5)$，第二行共包含 $n$ 个整数 $a_i(a_i \leq 10^5)$。接下来 $Q$ 行，每行一个整数 $p(1 \leq n \leq n)$，表示Orange的询问位置。

输出格式

共有 $Q$ 行，每行一个输出，表示Orange询问的答案。

样例 #1

样例输入 #1

5 2
1 2 3 4 5
2
4

样例输出 #1

1
3

提示

对于第二次询问，位置4一共被3个美丽区间所覆盖，即$[4;5];[2;3;4];[4]$。