#include <stdio.h>
#include <stdlib.h>
#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];
int toplace[MAX_N + 5];

long long int mymax(long long int a, long long int b) {
  return a > b ? a : b;
}

int mymin(int a, int b) {
  return a < b ? a : b;
}

void shuffle(int *v, int n) {
  int i;
  for (i = n - 1; i > 0; i--) {
    int j = rand() % (i+1);
    int tmp = v[i];
    v[i] = v[j];
    v[j] = tmp;
  }
}

void end(int type)
{
  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;
  int i;
  for (i = l; i <= r; i++)
    ct = mymax(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;
  int i;
  for (i = l; i <= r; i++)
    resp = mymax(resp, (long long int)(arrB[i]) + ((long long int)(K) * (long long int)(arrA[i])));

  K = mymin(K, r - l + 1);
  int sz = 0;
  for (i = l; i <= r; i++)
    toplace[sz++] = i;
  shuffle(toplace, sz);

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

  return resp;
}

int main()
{
  int i;
  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 (i = 0; i < N; i++) {
    arrB[i] = 0;
    scanf("%d", &arrA[i]);
  }

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

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

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

  return 0;
}