#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt")

#include <bits/stdc++.h>
using namespace std;

#define _f(i, a, b) for (int i = a; i <= b; ++i)
#define _d(i, a, b) for (int i = a; i >= b; --i)
using pii = pair<int, int>;
using ll = long long;
#define fi first
#define se second

static constexpr int N = 1e5 + 5, S = 370, Q = 5e5 + 5, V = 1e5;

int n, q, a[N], ans[Q], ind, buc[S][S], s, bl[N], num, L[S], R[S], sum[S][S], tmp[S];

struct ask { int m, x, y, id, v; };

vector<ask> p[N];

auto px = [](int x) { return x - L[bl[x]] + 1; };

auto query = [](int x, int y) {
	if(x > y) return 0;
	if(bl[x] == bl[y])
		return sum[bl[y]][px(y)] - sum[bl[y]][px(x) - 1];
	int ret = tmp[bl[y] - 1] - tmp[bl[x]];
	ret += sum[bl[x]][s] - sum[bl[x]][px(x) - 1];
	ret += sum[bl[y]][px(y)];
	return ret;
} ;

void solve() {
  cin >> n >> q, s = sqrt(V), num = (V / s) + !!(V % s);
  _f(i, 1, n) cin >> a[i];
  _f(i, 1, num) L[i] = R[i - 1] + 1, R[i] = R[i - 1] + s; R[num] = V;
  _f(i, 1, num) _f(j, L[i], R[i]) bl[j] = i;
  _f(i, 1, q) {
    int l, r, x, y, m; cin >> l >> r >> x >> y >> m;
    x %= m, y %= m;
    if(x > y) {
  	  p[l - 1].emplace_back((ask){m, m - x, m - y - 1, i, -1});
      p[r].emplace_back((ask){m, m - x, m - y - 1, i, 1});
    } else if(x < y) {
      p[l - 1].emplace_back((ask){m, 0, m - y - 1, i, -1});
      p[r].emplace_back((ask){m, 0, m - y - 1, i, 1});
      p[l - 1].emplace_back((ask){m, m - x, m - 1, i, -1});
      p[r].emplace_back((ask){m, m - x, m - 1, i, 1});
    }
  }
  _f(pos, 1, n) {
    _f(i, 1, s) buc[i][a[pos] % i]++;
     int _p = bl[a[pos]];
		_f(i, px(a[pos]), s) sum[_p][i]++;
		_f(i, _p, num) tmp[i]++;
		for(auto it : p[pos]) {
			int ret = 0;
			if(it.m <= s) {
				_f(i, it.x, it.y) ret += buc[it.m][i];
			} else {
				int l = 0, r = it.m - 1;
				while(233) {
					if(l > V) break;
					ret += query(min(l + it.x, V), min(l + it.y, V));
					l += it.m, r += it.m;
				}
			}
			ans[it.id] += it.v * ret;
		}
  }
	_f(i, 1, q) cout << ans[i] << '\n';
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	solve();
	return 0;
}

// powered by zzzcr.