为了揭开他们人生经历的奥秘，Nasa 和 Tsukasa 计划在地球航天器的帮助下飞往月球。在计算和模拟航天器的飞行轨道时，他们假设地球位于宇宙中的 $(0, 0)$，月球位于 $(1000, 1000)$。

尽管整个旅程漫长而艰辛，但得益于先进的航空航天技术，宇宙中除地球和月球外，所有整数坐标点上都有空间站。因此，他们可以在漫长的旅途中在这些空间站休息，并更换其他航天器。

每个空间站都有 $n$ 种全新的航天器，第 $i$ 种航天器可以携带 $d_i$ 单位的燃料，并且为了降低成本，总是朝着月球方向飞行。更准确地说，使用第 $i$ 种航天器，他们可以从 $(x, y)$ 航行到 $(x + dx, y + dy)$，其中 $dx$ 和 $dy$ 是非负整数，且满足 $0 < dx^2 + dy^2 \le d_i^2$。

在旅途中，他们可以选择是否在某些空间站着陆休息。请注意，如果他们选择在某个空间站休息，当他们再次出发时，将更换为该空间站内的一种新航天器。

然而，最近有 $m$ 个空间站因维护而关闭，他们无法在这些关闭的空间站停留。此外，这些关闭空间站内的航天器也无法使用。出于对这一问题的担忧，Nasa 很担心他们是否能成功到达月球。

因此，他们寻求你的帮助。你需要帮助他们计算飞往月球的不同路径数量。由于答案可能非常大，你只需要输出答案对 $998\,244\,353$ 取模的结果。注意，如果存在一个阶段，使得他们选择了两种不同的航天器或飞向了两个不同的空间站，则认为这两种方式是不同的。

输入格式

第一行包含两个整数 $n$ ($1 \le n \le 1000$) 和 $m$ ($0 \le m \le 1000$)，分别表示每个空间站的航天器种类数和宇宙中关闭的空间站数量。

第二行包含 $n$ 个整数 $d_1, d_2, \dots, d_n$ ($1 \le d_i \le 1000$)，表示每种航天器可以携带的燃料单位。

接下来的 $m$ 行，每行包含两个整数 $x$ 和 $y$ ($0 \le x, y \le 1000$)，表示位于 $(x, y)$ 的空间站已关闭。保证给定的 $m$ 个位置与地球和月球的位置不同，且两两互不相同。

输出格式

输出飞往月球的不同路径数量，对 $998\,244\,353$ 取模。

样例

样例输入 1

1 0
1

样例输出 1

472799582

样例输入 2

1 1
1
500 500

样例输出 2

447362327

样例输入 3

1 0
2

样例输出 3

277036758

说明

对于第一个样例，答案是 $\binom{2000}{1000}$。

对于第二个样例，答案是 $\binom{2000}{1000} - \binom{1000}{500}^2$。

注意 $\binom{n}{k}$ 是二项式系数，表示从 $n$ 个元素的集合中选取 $k$ 个元素构成的子集数量。