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

int main()
{
    int n;
	cin >> n;
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	int S = a + b + c + d;
	int Ans = 1;
	for(int i = 2; i <= n; i++)
	{
	    cin >> a >> b >> c >> d;
	    if(a + b + c + d > S)
	    {
	        Ans++;
	    }
	}
	printf("%d\n",Ans);
	return 0;
}

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

long long ar[4];
char c1[4] = {'0', '0', '1', '1'};
char c2[4] = {'0', '1', '0', '1'};

int main() {
    int n;
    cin >> n;
    string a, b;
    cin >> a >> b;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < 4; j++){
            if(c1[j] == a[i] && c2[j] == b[i]){
                ar[j]++;
            }
        }
    }
    cout << ar[0] * ar[2] + ar[0] * ar[3] + ar[1] * ar[2] << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100000
#define rint register int
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}
int n, L, A[MAXN+5];
int main()
{
	n = rf();
	L = (int)sqrt(n);
	for(rint i = 1, o = n, j; i <= n; i += L)
		for(j = min(i+L-1,n); j >= i; A[j--] = o--);
	for(rint i = 1; i <= n; i++)
		printf("%d%c",A[i],"\n "[i<n]);
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100000
#define rint register int
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}
int Wu[4096], f[64][64][104], g[4096][104], w[16], m, n, q, E, K, B = 6, L = 63, H = 4032; char _[16];
int main()
{
	m = rf();
	n = rf();
	q = rf();
	generate(w,w+m,rf);
	E = 1<<m;
	for(rint S = 0, j; S < E; S++)
	{
		for(j = 0; j < m; j++)
			S&1<<j?:Wu[S]+=w[j];
		Wu[S] = min(Wu[S],101);
	}
	for(rint i = 1, j, S; i <= n; i++)
	{
		scanf("%s",_+1);
		for(S = 0, j = m; j; j--)
			S = S<<1|(_[j]^'0');
		for(j = 0; j < 64; j++)
			++f[(S&H)>>B][j][Wu[((j^(S&L))|H)&~-E]];
	}
	for(rint S = 0, a, b, j; S < E; S++)
	{
		for(j = 0; j < 64; j++)
			for(a = 0, b = Wu[(((j<<B)^(S&H))|L)&~-E]; b <= 100; a++, b++)
				g[S][b] += f[j][S&L][a];
		partial_sum(g[S],g[S]+101,g[S]);
	}
	for(rint i = 1, j, S; i <= q; i++)
	{
		scanf("%s",_+1);
		for(S = 0, j = m; j; j--)
			S = S<<1|(_[j]^'0');
		printf("%d\n",g[S][rf()]);
	}
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rint register int
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}
//=====Computational Geometry Definitions
struct Vec
{
	int x,y; Vec(){} Vec(int _x, int _y){x=_x,y=_y;} inline Vec operator + (Vec b){return Vec(x+b.x,y+b.y);}
	inline Vec operator - (Vec b){return Vec(x-b.x,y-b.y);} inline Vec operator - (){return Vec(-x,-y);}
	inline ll operator * (Vec b){return (ll)x*b.x+(ll)y*b.y;} inline ll operator % (Vec b){return (ll)x*b.y-(ll)b.x*y;}
	inline ll operator ~ (){return (ll)x*x+(ll)y*y;} inline bool operator < (const Vec &b)const{return x^b.x?x<b.x:y<b.y;}
	inline bool operator ==(Vec b){return x==b.x&&y==b.y;} inline bool operator !=(Vec b){return x^b.x||y^b.y;}
};	typedef Vec Pt; inline bool ToLeft(Vec a, Vec b){return b%a>0;} inline bool Para(Vec a, Vec b){return !(a%b);}
Pt LTL; inline bool cmpltl(Pt a, Pt b){a = a-LTL; b = b-LTL; return Para(a,b) ? ~a<~b : ToLeft(b,a);}
typedef vector<Pt> Poly; Poly A, B, C, D; typedef vector<ll> Str; Str T, S; int n, m; vector<int> nex;
//=====
void CH(Poly &A, Poly &R)
{
	R.push_back(Pt());
	LTL = *min_element(A.begin(),A.end());
	sort(A.begin(),A.end(),cmpltl);
	for(rint i = 0; i < (int)A.size(); i++)
	{
		for(; R.size()>2&&!ToLeft(A[i]-R.back(),R.back()-R[R.size()-2]); )
			R.pop_back();
		R.push_back(A[i]);
	}
	R[0] = R[R.size()-1];
	R.push_back(R[1]);
}
void CTOS(Poly &p, Str &s)
{
	s.push_back(0);
	for(rint i = 1; i < (int)p.size()-1; i++)
	{
		s.push_back(~(p[i]-p[i-1]));
		s.push_back((p[i]-p[i-1])%(p[i+1]-p[i]));
	}
}
void CalNex()
{
	nex.resize(m+1);
	for(rint i = 2, j = 1; i <= m; i++)
	{
		for(; j>1&&S[i]^S[j]; )
			j = nex[j-1]+1;
		j += S[i]==S[j];
		nex[i] = j-1;
	}
}
bool KMP()
{
	for(rint i = 1, j = 1; i <= n; i++)
	{
		for(; j>1&&(j>m||T[i]^S[j]); )
			j = nex[j-1]+1;
		j+=T[i]==S[j]; 
		if(j>m)
			return true;
	}
	return false;
}
int main()
{
	A.resize(rf()); B.resize(rf());
	for(rint i = 0, s = (int)A.size(); i < s; i++)
		A[i].x = rf(), A[i].y = rf();
	CH(A,C);
	CTOS(C,T);
	n = T.size()-1;
	for(rint i = 0, s = (int)B.size(); i < s; i++)
		B[i].x = rf(), B[i].y = rf();
	CH(B,D);
	CTOS(D,S);
	m = S.size()-1;
	for(rint i = 1, s = (int)T.size(); i < s; i++)
		T.push_back(T[i]);
	n <<= 1;
	CalNex();
	puts(KMP()?"YES":"NO");
	return 0;
}

#pragma comment(linker, "/STACK:512000000")
#define _CRT_SECURE_NO_WARNINGS
//#include "testlib.h"
#include <bits/stdc++.h>
using namespace std;

#define all(a) a.begin(), a.end()
using li = long long;
using ld = long double;
void solve(bool);
void precalc();
clock_t start;
int main() {
#ifdef AIM
  freopen("/home/alexandero/CLionProjects/ACM/input.txt", "r", stdin);
//freopen("/home/alexandero/CLionProjects/ACM/output.txt", "w", stdout);
//freopen("out.txt", "w", stdout);
#else
  //freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#endif
  start = clock();
  int t = 1;
#ifndef AIM
  cout.sync_with_stdio(0);
  cin.tie(0);
#endif
  cout.precision(20);
  cout << fixed;
//cin >> t;
  precalc();
  while (t--) {
    solve(true);
  }
  cout.flush();

#ifdef AIM1
  while (true) {
solve(false);
}
#endif

#ifdef AIM
  cerr << "\n\n time: " << (clock() - start) / 1.0 / CLOCKS_PER_SEC << "\n\n";
#endif
  return 0;
}

//BE CAREFUL: IS INT REALLY INT?

template<typename T>
T binpow(T q, T w, T mod) {
  if (!w)
    return 1 % mod;
  if (w & 1)
    return q * 1LL * binpow(q, w - 1, mod) % mod;
  return binpow(q * 1LL * q % mod, w / 2, mod);
}

template<typename T>
T gcd(T q, T w) {
  while (w) {
    q %= w;
    swap(q, w);
  }
  return q;
}
template<typename T>
T lcm(T q, T w) {
  return q / gcd(q, w) * w;
}

template <typename T>
void make_unique(vector<T>& vec) {
  sort(all(vec));
  vec.erase(unique(all(vec)), vec.end());
}

template<typename T>
void relax_min(T& cur, T val) {
  cur = min(cur, val);
}

template<typename T>
void relax_max(T& cur, T val) {
  cur = max(cur, val);
}

void precalc() {

}

#define int li
//const li mod = 1000000007;
//using ull = unsigned long long;

struct Point {
  int x, y;
  Point() {}
  Point(int x, int y) : x(x), y(y) {}
  Point operator - (const Point& ot) const {
    return Point(x - ot.x, y - ot.y);
  }
  int operator * (const Point& ot) const {
    return x * ot.y - y * ot.x;
  }
  void scan() {
    cin >> x >> y;
  }
  bool operator < (const Point& ot) const {
    return make_pair(x, y) < make_pair(ot.x, ot.y);
  }
  int sqr_len() const {
    return x * x + y * y;
  }
  long double get_len() const {
    return sqrtl(sqr_len());
  }
  int operator % (const Point& ot) const {
    return x * ot.x + y * ot.y;
  }
};

struct Polygon {
  vector<Point> hull;
  Polygon(int n) {
    vector<Point> points(n);
    for (int i = 0; i < n; ++i) {
      points[i].scan();
    }
    sort(all(points));
    vector<Point> up, down;
    for (auto& pt : points) {
      while (up.size() > 1 && (up[up.size() - 2] - up.back()) * (pt - up.back()) >= 0) {
        up.pop_back();
      }
      up.push_back(pt);
      while (down.size() > 1 && (down[down.size() - 2] - down.back()) * (pt - down.back()) <= 0) {
        down.pop_back();
      }
      down.push_back(pt);
    }
    hull = up;
    for (int i = (int)down.size() - 2; i > 0; --i) {
      hull.push_back(down[i]);
    }
  }
  int sqr_len(int pos) const {
    return (hull[(pos + 1) % hull.size()] - hull[pos]).sqr_len();
  }
  int size() const {
    return (int)hull.size();
  }
  long double get_angle(int pos) const {
    auto a = hull[(pos + 1) % hull.size()] - hull[pos], b = hull[(pos + hull.size() - 1) % hull.size()] - hull[pos];
    long double co = (a % b) / a.get_len() / b.get_len();
    return co;
  }
};

void solve(bool read) {
  vector<Polygon> polys;
  int n[2];
  cin >> n[0] >> n[1];
  for (int i = 0; i < 2; ++i) {
    polys.emplace_back(n[i]);
  }
  if (polys[0].size() != polys[1].size()) {
    cout << "NO\n";
    return;
  }
  vector<long double> all_lens;
  int m = polys[0].size();
  for (int i = 0; i < m; ++i) {
    all_lens.push_back(polys[0].sqr_len(i));
    all_lens.push_back(polys[0].get_angle(i));
  }
  all_lens.push_back(-1);
  for (int j = 0; j < 2; ++j) {
    for (int i = 0; i < m; ++i) {
      all_lens.push_back(polys[1].sqr_len(i));
      all_lens.push_back(polys[1].get_angle(i));
    }
  }
  /*for (int x : all_lens) {
    cout << x << " ";
  }
  cout << "\n";*/
  vector<int> p(all_lens.size());
  for (int i = 1; i < p.size(); ++i) {
    int j = p[i - 1];
    while (j > 0 && all_lens[i] != all_lens[j]) {
      j = p[j - 1];
    }
    if (all_lens[i] == all_lens[j]) {
      ++j;
    }
    p[i] = j;
    if (p[i] == 2 * m) {
      cout << "YES\n";
      return;
    }
  }
  cout << "NO\n";

}

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define uint unsigned int
#define rint register int
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}
bitset<100000032> _b; int n; uint A, B, C, D, Ans;
inline uint f(int p){
    return((A*p+B)*p+C)*p+D;
}
inline int cnt(int p, int n){
    int r=0;
    for(;n/=p;r+=n);
    return r;
}
inline auto b(int i)->decltype(_b[0]){
    return _b[(i&1)&&(i%6!=3)?i/6<<1|((i%6)>1):0];
}
inline auto b2(int i)->decltype(_b[0]){
    return _b[i/6<<1|1];
}
inline auto b3(int i)->decltype(_b[0]){
    return _b[i/6<<1];
}

int main()
{
    n = rf();
    A = rf();
    B = rf();
    C = rf();
    D = rf();
    _b[0] = 1;
    Ans = cnt(2,n)*f(2)+cnt(3,n)*f(3);
    for(rint i = 5, j, z, c, w; i <= n; i += 4){
        if(!b2(i))
        {
            Ans += cnt(i,n)*f(i);
            if(i <= 20000){
                w = i + i;
                c = w % 6;
                z = (i * i) % 6;
                if(c == 0){
                    if(z == 1){
                        for(j = i * i; j <= n; j += w){
                            b3(j) = 1;
                        }
                    }else if(z == 5){
                        for(j = i * i; j <= n; j += w){
                            b2(j) = 1;
                        }
                    }
                }else if(c == 2){
                    if(z == 1){
                        for(j = i * i; j <= n; j += w){
                            b3(j) = 1;
                            j += w + w;
                            if(j <= n){
                                b2(j) = 1;
                            }
                        }
                    }else if(z == 5){
                        for(j = i * i; j <= n; j += w + w){
                            b2(j) = 1;
                            j += w;
                            if(j <= n){
                                b3(j) = 1;
                            }
                        }
                    }
                }else if(c == 4){
                    if(z == 1){
                        for(j = i * i; j <= n; j += w + w){
                            b3(j) = 1;
                            j += w;
                            if(j <= n){
                                b2(j) = 1;
                            }
                        }
                    }else if(z == 5){
                        for(j = i * i; j <= n; j += w){
                            b2(j) = 1;
                            j += w + w;
                            if(j <= n){
                                b3(j) = 1;
                            }
                        }
                    }
                }
            }
        }
        i += 2;
        if(i <= n && !b3(i))
        {
            Ans += cnt(i,n)*f(i);
            if(i <= 20000){
                w = i + i;
                c = w % 6;
                z = (i * i) % 6;
                if(c == 0){
                    if(z == 1){
                        for(j = i * i; j <= n; j += w){
                            b3(j) = 1;
                        }
                    }else if(z == 5){
                        for(j = i * i; j <= n; j += w){
                            b2(j) = 1;
                        }
                    }
                }else if(c == 2){
                    if(z == 1){
                        for(j = i * i; j <= n; j += w){
                            b3(j) = 1;
                            j += w + w;
                            if(j <= n){
                                b2(j) = 1;
                            }
                        }
                    }else if(z == 5){
                        for(j = i * i; j <= n; j += w + w){
                            b2(j) = 1;
                            j += w;
                            if(j <= n){
                                b3(j) = 1;
                            }
                        }
                    }
                }else if(c == 4){
                    if(z == 1){
                        for(j = i * i; j <= n; j += w + w){
                            b3(j) = 1;
                            j += w;
                            if(j <= n){
                                b2(j) = 1;
                            }
                        }
                    }else if(z == 5){
                        for(j = i * i; j <= n; j += w){
                            b2(j) = 1;
                            j += w + w;
                            if(j <= n){
                                b3(j) = 1;
                            }
                        }
                    }
                }
            }
        }
    }
    printf("%u\n",Ans);
    return 0;
}

#include <bits/stdc++.h>

using namespace std;
typedef unsigned int ll;
const ll maxn=4e8;
const ll maxp=sqrt(maxn)+10;
ll f[4][maxp],g[4][maxp];
ll n,m,A,B,C,D,ans,res,tmp,rt;

ll p1(ll x){
    ll y=x+1; if (x%2==0) x/=2; else y/=2;
    return x*y;
}
ll p2(ll x){
    long long y=x+1,z=x*2+1;
    if (x%2==0) x/=2; else y/=2;
    if (z%3==0) z/=3; else if (x%3==0) x/=3; else y/=3;
    return (ll)x*y*z;
}
ll p3(ll x){
    ll y=p1(x);
    return y*y;
}
bool is_prime(ll x){
    for (ll i=2;i*i<=x;i++) if (x%i==0) return false;
    return true;
}

ll solve(ll n)
{
    ll i,j,rt,o[4];
    for (m=1;m*m<=n;m++) {
        f[0][m]=(n/m-1);
        f[1][m]=(p1(n/m)-1)*C;
        f[2][m]=(p2(n/m)-1)*B;
        f[3][m]=(p3(n/m)-1)*A;
    }
    for (i=1;i<=m;i++) {
        g[0][i]=(i-1);
        g[1][i]=(p1(i)-1)*C;
        g[2][i]=(p2(i)-1)*B;
        g[3][i]=(p3(i)-1)*A;
    }
    for (i=2;i<=m;i++) {
        if (g[0][i]==g[0][i-1]) continue;
        o[0]=1; for (int w=1;w<4;w++) o[w]=o[w-1]*i;
        for (j=1;j<=min(m-1,n/i/i);j++)
            for (int w=0;w<4;w++)
                if (i*j<m) f[w][j]-=o[w]*(f[w][i*j]-g[w][i-1]);
                else f[w][j]-=o[w]*(g[w][n/i/j]-g[w][i-1]);
        for (j=m;j>=i*i;j--)
            for (int w=0;w<4;w++)
                g[w][j]-=o[w]*(g[w][j/i]-g[w][i-1]);
    }
    for (int i=1;i<=m+1;i++) f[0][i]*=D,g[0][i]*=D;
    rt=0;
    for (ll i=1;n/i>m;i++) {
        for (int w=0;w<4;w++) rt+=(f[w][i]-g[w][m]);
        //cout<<"H"<<rt<<endl;
    }
    return rt;
}

int main()
{
    //freopen("input.txt","r",stdin);
    ll n; cin >> n >> A >> B >> C >> D;
    ans=solve(n);
    for (ll i=2;i<=m;i++){
        if (is_prime(i)){
            res=A*i*i*i+B*i*i+C*i+D; tmp=n;
            while (tmp){
                ans+=res*(tmp/i);
                tmp/=i;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

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

const int MAX = 1e5 + 10;

bool black[MAX]; // is it vertex black now
vector<int> vec[MAX]; // main edges
bool old_black[MAX]; // to remember the tree before block

const int MAX_BLOCK_SIZE = 600;

int t[MAX], v[MAX]; // queries

bool used[MAX]; // is in mini-tree
vector<pair<pair<int, int>, int> > v2[MAX]; // mini-tree edges (son, number of white vertices, dist)
int push[MAX]; // push of the i-th vertex in mini-tree
bool clear[MAX]; // do we need to clear first

void dfs_1(int pos, int prev = -1, int white = 0, int dist = 0){
    if(used[pos]){
        if(prev != -1){
            v2[prev].push_back(make_pair(make_pair(pos, white), dist));
        }
        for(int a : vec[pos]){
            dfs_1(a, pos, 0, 0);
        }
    }else{
        if(!black[pos]){
            white++;
        }
        for(int a : vec[pos]){
            dfs_1(a, prev, white, dist + 1);
        }
    }
}

void make_1(int pos){
    if(!black[pos]){
        black[pos] = true;
        return;
    }
    push[pos]++;
    for(auto a : v2[pos]){
        if(a.first.second + 1 <= push[pos]){
            make_1(a.first.first);
        }
    }
}

void make_2(int pos){
    black[pos] = false;
    push[pos] = 0;
    clear[pos] = true;
    for(auto &a : v2[pos]){
        a.first.second = a.second;
        make_2(a.first.first);
    }
}

void dfs_2(int pos, int p = 0, bool cl = false){
    if(used[pos]){
        p = push[pos];
        cl |= clear[pos];
    }else{
        black[pos] = old_black[pos];
        if(cl){
            black[pos] = false;
        }
        if(!black[pos] && p){
            black[pos] = true;
            p--;
        }
    }
    for(int a : vec[pos]){
        dfs_2(a, p, cl);
    }
}

int main(){
    ios_base::sync_with_stdio();
    cin.tie(0);
    cout.tie(0);
    int n, q;
    cin >> n >> q;
    for(int i = 2; i <= n; i++){
        int a;
        cin >> a;
        vec[a].push_back(i);
    }
    for(int i = 1; i <= q; i++){
        cin >> t[i] >> v[i];
    }
    int root = 1;
    for(int i = 1; i <= q; i += MAX_BLOCK_SIZE){
        for(int j = 1; j <= n; j++){
            used[j] = false;
            v2[j].clear();
            old_black[j] = black[j];
            push[j] = 0;
            clear[j] = false;
        }
        for(int j = 0; j < MAX_BLOCK_SIZE && i + j <= q; j++){
            used[v[i + j]] = true;
        }
        dfs_1(root);
        for(int j = 0; j < MAX_BLOCK_SIZE && i + j <= q; j++){
            int t = ::t[i + j];
            int v = ::v[i + j];
            if(t == 1){
                make_1(v);
            }else if(t == 2){
                make_2(v);
            }else{
                cout << (black[v] ? "black" : "white") << "\n";
            }
        }
        dfs_2(root);
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
#define MAXN 200000
#define MOD 998244353
#define rint register int
inline int rf(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}
int n, m, q, B, C, T, fac[MAXN+5], efac[MAXN+5], Ans[MAXN+5], A[MAXN+5], t[MAXN+5], c[MAXN+5];
int mp[MAXN+5], rv[480], h[480][100032], _init[MAXN+5], d[105][100032]; bitset<100032> b[480];
typedef pair<int,int> pii; pii S[MAXN+5]; struct QU{int u,l,r,k,i;}Q[MAXN+5];
inline bool cmpi(const QU &a, const QU &b)
{
	return a.i<b.i;
}
inline bool cmpm(const QU &a, const QU &b)
{
	return a.u^b.u?a.u<b.u:a.u&1?a.r<b.r:a.r>b.r;
}
//fastpow
inline int fxp(int s, int n=MOD-2){int a=1;for(;n;n&1?a=1ll*a*s%MOD:0,s=1ll*s*s%MOD,n>>=1);return a;}
inline void Init(int k)
{
	if(_init[k]) return;
	_init[k] = ++C;
	int *D = d[C], s = 1ll*m*k%MOD;
	D[0] = 1;
	for(rint i = 1; i <= n; i++)
		D[i] = 1ll*D[i-1]*(s+i)%MOD;
}
inline int dxp(int a, int b)
{
	return 1ll*fac[a]*efac[a-b]%MOD;
}
inline int DXP(int k, int l)
{
	return d[_init[k]][l];	
}
void insert(int x)
{
	--h[t[x]][c[x]++];
	++h[t[x]][c[x]];
	S[++T] = pii(t[x],c[x]);
}
void erase(int x)
{
	--h[t[x]][c[x]--];
	++h[t[x]][c[x]];
	S[++T] = pii(t[x],c[x]);
}
inline int calc(int k)
{
	int _ = T; T = 0;
	for(rint i = 1; i <= _; i++)
		if(!b[S[i].first][S[i].second]&&h[S[i].first][S[i].second])
			S[++T] = S[i], b[S[i].first][S[i].second] = 1;
	int Ans = 1;
	for(rint i = 1; i <= T; i++)
	{
		b[S[i].first][S[i].second] = 0;
		Ans = 1ll*Ans*fxp(dxp(rv[S[i].first]+k,S[i].second),h[S[i].first][S[i].second])%MOD;
	}
	return Ans;
}
int main()
{
	n = MAXN;
	for(rint i = fac[0] = 1; i <= n; i++)
		fac[i] = 1ll*i*fac[i-1]%MOD;
	efac[n] = fxp(fac[n]);
	for(rint i = n; i; i--)
		efac[i-1] = 1ll*i*efac[i]%MOD;
	n = rf();
	m = rf();
	q = rf();
	B = n/sqrt(q*2/3)+1;
	for(rint i = 1; i <= n; i++)
		++t[A[i]=rf()];
	for(rint i = 1, c = 0; i <= n; i++)
		mp[t[A[i]]]?:rv[mp[t[A[i]]]=++c]=t[A[i]];
	for(rint i = 1; i <= m; i++)
		t[i] = mp[t[i]];
	for(rint i = 1, l, r, k; i <= q; i++)
	{
		l = rf();
		r = rf();
		k = rf();
		Init(k);
		Q[i] = {~-l/B,l,r,k,i};
	}
	sort(Q+1,Q+q+1,cmpm);
	for(rint i = 1; i <= n; i++)
		++h[t[A[i]]][0];
	for(rint i = 1, l = 1, r = 0; i <= q; i++)
	{
		for(; l > Q[i].l; insert(A[--l]));
		for(; r < Q[i].r; insert(A[++r]));
		for(; l < Q[i].l; erase(A[l++]));
		for(; r > Q[i].r; erase(A[r--]));
		Ans[Q[i].i] = calc(Q[i].k);
	}
	sort(Q+1,Q+q+1,cmpi);
	for(rint i = 1; i <= q; i++)
		printf("%d\n",1ll*DXP(Q[i].k,n-(Q[i].r-Q[i].l+1))*Ans[i]%MOD);
	return 0;
}

#pragma comment(linker, "/STACK:512000000")
#include <bits/stdc++.h>
using namespace std;

#define all(a) a.begin(), a.end()
typedef long long li;
typedef long double ld;
void solve(__attribute__((unused)) bool);
void precalc();
clock_t start;
#define FILENAME ""

int main() {
#ifdef AIM
    string s = FILENAME;
//    assert(!s.empty());
    freopen("/home/alexandero/ClionProjects/cryptozoology/input.txt", "r", stdin);
  //freopen("/home/alexandero/ClionProjects/cryptozoology/output.txt", "w", stdout);
#else
//    freopen(FILENAME ".in", "r", stdin);
//    freopen(FILENAME ".out", "w", stdout);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    start = clock();
    int t = 1;
#ifndef AIM
    cout.sync_with_stdio(0);
    cin.tie(0);
#endif
  precalc();
    cout.precision(10);
    cout << fixed;
    //cin >> t;
    int testNum = 1;
    while (t--) {
        //cout << "Case #" << testNum++ << ": ";
        solve(true);
    }
    cout.flush();
#ifdef AIM1
    while (true) {
      solve(false);
  }
#endif

#ifdef AIM
    cout.flush();
    auto end = clock();

    usleep(10000);
    print_stats(end - start);
    usleep(10000);
#endif

    return 0;
}

template<typename T>
T binpow(T q, T w, T mod) {
    if (!w)
        return 1 % mod;
    if (w & 1)
        return q * 1LL * binpow(q, w - 1, mod) % mod;
    return binpow(q * 1LL * q % mod, w / 2, mod);
}

template<typename T>
T gcd(T q, T w) {
    while (w) {
        q %= w;
        swap(q, w);
    }
    return q;
}
template<typename T>
T lcm(T q, T w) {
    return q / gcd(q, w) * w;
}

template <typename T>
void make_unique(vector<T>& a) {
    sort(all(a));
    a.erase(unique(all(a)), a.end());
}

template<typename T>
void relax_min(T& cur, T val) {
    cur = min(cur, val);
}

template<typename T>
void relax_max(T& cur, T val) {
    cur = max(cur, val);
}

void precalc() {
}

#define int li
const int mod = 998244353;

struct Query {
  int l, r, id;
};

vector<int> res;
vector<int> a;
int n;

int TIMER = 0;
const int C = 200500;
int used[C];
int cur_cnt[C];
int rev[C];
map<int, vector<int>> down;
vector<int> init;

void kill(vector<Query>& all_q, int block_size, int k) {
  vector<vector<Query>> by_block(n / block_size + 1);
  for (auto& cur_q : all_q) {
    by_block[cur_q.l / block_size].push_back(cur_q);
  }
  for (int i = 0; i < by_block.size(); ++i) {
    ++TIMER;
    auto& q = by_block[i];
    sort(all(q), [&] (const Query& o1, const Query& o2) {
      return o1.r < o2.r;
    });
    int cur_l = min(n, (i + 1) * block_size);
    int cur_r = cur_l;
    int cur_prod = 1;

    auto add_item = [&] (int val) {
      if (used[val] != TIMER) {
        used[val] = TIMER;
        cur_cnt[val] = 0;
      }
      int cur_k = k + init[val];
      ++cur_cnt[val];
        cur_prod = cur_prod * (cur_k - cur_cnt[val] + 1) % mod;
    };
    auto remove_item = [&] (int val) {
      int cur_k = k + init[val];
        cur_prod = cur_prod * rev[cur_k - cur_cnt[val] + 1] % mod;
      --cur_cnt[val];
    };

    for (auto& cur_q : q) {
      while (cur_r < cur_q.r) {
        add_item(a[cur_r++]);
      }
      while (cur_l > cur_q.l) {
        add_item(a[--cur_l]);
      }
      while (cur_r > cur_q.r) {
        remove_item(a[--cur_r]);
      }
      while (cur_l < cur_q.l) {
        remove_item(a[cur_l++]);
      }
        res[cur_q.id] = cur_prod * down[k][n - cur_q.r + cur_q.l] % mod;
    }
  }
}

void solve(__attribute__((unused)) bool read) {
  for (int i = 1; i < C; ++i) {
    rev[i] = binpow(i, mod - 2, mod);
  }
  int m, Q;
  //read = false;
  if (read) {
    cin >> n >> m >> Q;
  } else {
    n = 50000;
    m = 100000;
    Q = 50000;
  }
  a.resize(n);
  init.assign(m, 0);
  for (int i = 0; i < n; ++i) {
    if (read) {
      cin >> a[i];
      --a[i];
    } else {
      a[i] = rand() % m;
    }
    ++init[a[i]];
  }
  map<int, vector<Query>> q;
  for (int i = 0; i < Q; ++i) {
    int l, r, k;
    if (read) {
      cin >> l >> r >> k;
    } else {
      do {
        l = rand() % n + 1;
        r = rand() % n + 1;
      } while (l > r);
      k = rand() % 100;
    }
    --l;
    q[k].push_back({l, r, i});
    down[k] = vector<int>();
  }
  res.assign(Q, 0);
  for (auto& item : down) {
    int init_val = (item.first * m) % mod;
    auto& vec = item.second;
    vec.assign(n + 1, 1);
    for (int i = 1; i < vec.size(); ++i) {
      vec[i] = vec[i - 1] * (init_val + i) % mod;
    }
  }
  for (auto& item : q) {
    int k = item.first;
    auto& cur_q = item.second;
    int block_size = std::max((int)(n / sqrt((int)cur_q.size())), 1LL);
    kill(cur_q, block_size, k);
  }

  for (int i = 0; i < Q; ++i) {
    cout << res[i] << "\n";
  }

}