#include <stdio.h>
#include <vector>
#include <algorithm>
#include "avaliador.h"

int correto = 0;
int N, I, maxK, Q;
int contador;
int arrA[MAX_N + 5];
int arrB[MAX_N + 5];
int arrl[MAX_I + 5];
int arrr[MAX_I + 5];

void end(int type = 0)
{
  if (correto)
    printf("Correto!\n");
  else
  {
    if (type == 0)
      printf("Incorreto, excedeste o numero de chamadas por intervalo, %d/%d\n", contador, Q);
    else if (type == 1)
      printf("Incorreto, resposta a um intervalo incorreta...\n");
    else if (type == 2)
      printf("Incorreto, chamada invalida (valor de K excedido ou limites de intervalo invalidos)...\n");
    else
      printf("Incorreto, input invalido...\n");
  }
  exit(0);
}

void contar() {
  if (contador > Q) {
    end(0);
  }

  contador = 0;
}

long long int get(int* arr, int l, int r) {
  long long int ct = 0;
  for (int i = l; i <= r; i++)
    ct = max(ct, (long long int)arr[i]);
  return ct;
}

long long int maxFormigas(int l, int r, int K) {
  if (K < 0 || K > maxK || l > r || l < 0 || l >= N || r < 0 || r >= N) {
    end(2);
  }

  contador++;
  long long int resp = 0;
  for (int i = l; i <= r; i++)
    resp = max(resp, (long long int)(arrB[i]) + ((long long int)(K) * (long long int)(arrA[i])));

  K = min(K, r - l + 1);
  vector<int> toplace;
  for (int i = l; i <= r; i++)
    toplace.push_back(i);
  random_shuffle(toplace.begin(), toplace.end());

  for (int i = 0; i < K; i++)
    arrB[toplace[i]]++;

  return resp;
}

int main()
{
  scanf("%d %d %d %d", &N, &I, &maxK, &Q);

  if (N < 1 || N > MAX_N)
    end(5);

  if (I < 1 || I > MAX_I)
    end(5);

  for (int i = 0; i < N; i++) {
    arrB[i] = 0;
    scanf("%d", &arrA[i]);
  }

  for (int i = 0; i < I; i++)
    scanf("%d %d", &arrl[i], &arrr[i]);

  srand(1111);
  
  contador = 0;
  iniciar(N, I, maxK, Q);
  contar();

  for (int i = 0; i < I; i++) {
    if (get(arrA, arrl[i], arrr[i]) != pergunta(arrl[i], arrr[i])) {
      end(1);
    }
    contar();
  }
  
  correto = 1;
  end();

  return 0;
}