样例过了，代码：

#define debug
#include <bits/stdc++.h>

using namespace std;

#define fir first
#define sec second
#define int long long 

char _c; bool _f; template < class T > inline void read ( T &x ) {
	_f = 0, x = 0;
	while ( _c = getchar (), !isdigit (_c) ){
		if ( _c == '-' ) { _f = 1; }
	}
	while ( isdigit (_c) ){
		x = x * 10 + _c - '0', _c = getchar ();
		if (_f) { x = -x; }
	}
}

const int N = 1e5 + 5;
const int B = 320;
const int BLOCK = 5000;

int n, m, block;
int a[N], pw[N][B], pw2[N][B];

struct Ask {
  int l, r, p, ans, id;
} q[N];

bool cmp ( Ask x, Ask y ) {
  if ( x.l / block == y.l / block ) {
    return ( x.l / block ) & 1 ? x.r < y.r : x.r > y.r;
  }
  return x.l / block < y.l / block;
}

bool cmp2 ( Ask x, Ask y ) {
  return x.id < y.id;
}

int fast_pow ( int b, int id, int p ) {
  return pw[id][b % block] * pw2[id][b / block] % p;
}

struct List {
  int cnt, pre, nxt;
} t[N];

int tong[N];

void ins1 ( int x, int v ) { // tong[x] - 1;
  int tmp = t[x].pre;
  t[tmp].nxt = x - 1, t[x].pre = x - 1;
  t[x - 1].cnt = v;
  t[x - 1].pre = tmp, t[x - 1].nxt = x;
}

void ins2 ( int x, int v ) { // tong[x] + 1
  int tmp = t[x].nxt;
  t[tmp].pre = x + 1, t[x].nxt = x + 1;
  t[x + 1].cnt = v;
  t[x + 1].pre = x, t[x + 1].nxt = tmp;
}

void erase ( int x ) {
  t[t[x].pre].nxt = t[x].nxt;
  t[t[x].nxt].pre = t[x].pre;
  t[x].pre = t[x].nxt = 0;
}

void add ( int x ) {
  t[tong[x]].cnt -= x;
  if ( t[tong[x]].nxt != tong[x] + 1 ) {
    // cout << tong[x] << " ";
    ins2 ( tong[x], x );
  }
  else {
    t[tong[x] + 1].cnt += x;
  }
  if ( !t[tong[x]].cnt ) {
    // cout << tong[x] << " ";
    erase ( tong[x] );
  }
  tong[x] ++;
}

void del ( int x ) {
  t[tong[x]].cnt -= x;
  if ( t[tong[x]].pre != tong[x] - 1 && tong[x] > 1 ) {
    // cout << tong[x] << " ";
    ins1 ( tong[x], x );
  }
  else {
    t[tong[x] - 1].cnt += x;
  }
  if ( !t[tong[x]].cnt ) {
    // cout << tong[x] << " ";
    erase ( tong[x] );
  }
  tong[x] --;
}

void Solve () {
  cin >> n >> m;
  for ( int i = 1; i <= n; i ++ ) {
    cin >> a[i];
  }
  int l = 1, r = 0;
  block = sqrt ( n );
  for ( int i = 1; i <= m; i ++ ) {
    cin >> q[i].l >> q[i].r >> q[i].p;
    q[i].id = i;
    pw[i][0] = 1;
    for ( int j = 1; j <= block; j ++ ) {
      pw[i][j] = pw[i][j - 1] * 2;
      pw[i][j] %= q[i].p;
    }
    int tmp = pw[i][block]; pw2[i][0] = 1;
    for ( int j = 1; j <= block; j ++ ) {
      pw2[i][j] = pw2[i][j - 1] * tmp;
      pw2[i][j] %= q[i].p;
    }
  }
  sort ( q + 1, q + 1 + m, cmp );
  for ( int i = 1; i <= m; i ++ ) {
    while ( l < q[i].l ) {
      del ( a[l] );
      l ++;
    }
    while ( l > q[i].l ) {
      l --;
      add ( a[l] );
    }
    while ( r > q[i].r ) {
      del ( a[r] );
      r --;
    }
    while ( r < q[i].r ) {
      r ++;
      add ( a[r] );
    }
    for ( int j = t[0].nxt; j; j = t[j].nxt ) {
      // cout << j << " ";
      q[i].ans += t[j].cnt * ( ( fast_pow ( q[i].r - q[i].l + 1, q[i].id, q[i].p ) - fast_pow ( q[i].r - q[i].l + 1 - j, q[i].id, q[i].p ) + q[i].p ) % q[i].p ) % q[i].p;
      q[i].ans = ( q[i].ans % q[i].p + q[i].p ) % q[i].p;
    }
    // cout << '\n';
  }
  sort ( q + 1, q + 1 + m, cmp2 );
  for ( int i = 1; i <= m; i ++ ) {
    cout << q[i].ans << '\n';
  }
}

signed main () {
#ifdef debug
	freopen ( "test.in", "r", stdin );
	freopen ( "test.out", "w", stdout );
	Solve ();
#endif
	return 0;
}

调了好久了，求调。