DSA_DSA

#include<stdio.h>
#include<stdlib.h>

#define ll long long int
// #define MAXN 1000000
// #define MAXT 500000
// #define MAXM 500000
#define MAXN 100
#define MAXT 50
#define MAXM 50

typedef struct {
    ll *array;
    ll size;
    ll capacity;
} Vector;

void Vector_init(Vector *vec) {
    vec->array = NULL;
    vec->size = 0;
    vec->capacity = 0;
}

void Vector_push_back(Vector *vec, ll value) {
    if (vec->size == vec->capacity) {
        vec->capacity = (vec->capacity == 0) ? 1 : vec->capacity * 2;
        vec->array = (ll *)realloc(vec->array, vec->capacity * sizeof(ll));
    }
    vec->array[vec->size] = value;
    vec->size++;
}

int PowerBinarySearch(ll power[MAXN+1], ll standard, int l, int r)
{
    int m = -1;
    while(l < r){
        m = ((l+r+1)/2); // why +1? I want the one who is slightly on the right
        //printf("l: %d r: %d m: %d\n", l, r, m);
        if(power[m] >= standard){
            l = m;
        }
        else{
            r = m-1;
        }
    }
    if(m == -1){
        return -1;
    }
    else{
        return r;
    }
}

void PrintStatus(int label[MAXN+1], ll power[MAXN+1], int N)
{
    printf("-------------------\n");
    printf("Format : Label(rank): power\n");
    for(int i = 1 ; i <= N ; i++){
        printf("%d(%d): %lld\n", label[i], i, power[i]);
    }
    printf("-------------------\n");
    return;
}

void PrintVector(Vector *vec){
    for(int i = 0 ; i < vec->size ; i++){
        printf("%lld ",vec->array[i]);
    }
    printf("\n");
    return;
}

void Attack(int label[MAXN+1], int rank[MAXN+1], ll power[MAXN+1], Vector* power_gains, int attack_times[MAXN+1], int attacker, int N, int M)
{
    if(attacker > N || attacker < 1){
        //printf("Attcker not found.\n");
        return;
    }

    int attacker_rank = rank[attacker];
    //printf("Attacker_rank: %d\n", attacker_rank);
    if(attacker_rank == 1){
        //printf("The top one attacks.\n");
    }
    else{
        attack_times[label[attacker_rank]]++;
        // printf("The %d-th time attack of player %d.\n", attack_times[label[attacker_rank]], label[attacker_rank]);
        // printf("Gained power : %lld\n", power[attacker_rank-1] - power[attacker_rank]);
        // printf("Pushing powergains\n");
        int attacker_label = label[attacker_rank];
        if(power_gains->size == 0){
            Vector_push_back(power_gains, power[attacker_rank-1] - power[attacker_rank]);
            // PrintVector(power_gains);
        }
        else{
            Vector_push_back(power_gains, power_gains->array[power_gains->size-1] + (power[attacker_rank-1] - power[attacker_rank]));
            // PrintVector(power_gains);
        }
        // printf("Done\n");

        rank[label[attacker_rank]]--;
        rank[label[attacker_rank-1]]++;

        power[attacker_rank] = power[attacker_rank-1];
        int temp_label = label[attacker_rank];
        label[attacker_rank] = label[attacker_rank-1];
        label[attacker_rank-1] = temp_label;
    }

    return;
}

void Reward(ll power[MAXN+1], int N)
{
    for(int i = 1 ; i <= N ; i++){
        power[i] += (N-i);
    }
    return;
}

void Query(int label[MAXN+1], ll power[MAXN+1], ll standard, int N)
{
    if(standard > power[1]){
        printf("0 0\n");
        return;
    }

    int last_rank = PowerBinarySearch(power, standard, 1, N);
    if(last_rank == -1){
        printf("0 0\n");
    }
    else{
        printf("%d %d\n", last_rank, label[last_rank]);
    }
    return;
}


void GetPowerGains(Vector* power_gains, int attack_times[MAXN+1], int target_label, int attack_tms)
{
    if(power_gains->size == 0){
        printf("0\n");
        return;
    }
    if(attack_tms >= attack_times[target_label]){ // the total gains
        printf("%lld\n", power_gains->array[power_gains->size-1]);
    }
    else{
        // printf("Size : %lld\n", power_gains->size);
        int index = attack_times[target_label] - attack_tms - 1;
        // printf("INdex: %lld\n", index);
        printf("%lld\n", power_gains->array[power_gains->size-1] - power_gains->array[index]);
    }
    return;
}

void PrintGameRecord(Vector power_gains[MAXN+1], int attack_times[MAXN+1], int N)
{
    printf("\n");
    for(int i = 1 ; i <= N ; i++){
        printf("%d ", attack_times[i]);
        // ll gained_power[MAXN+1] = {0};
        for(int j = 0 ; j < power_gains[i].size ; j++){
            if(j == 0){
                printf("%lld ", power_gains[i].array[j]);
            }
            else{
                printf("%lld ", power_gains[i].array[j] - power_gains[i].array[j-1]);
            }
        }
        printf("\n");
    }
    return;
}

int main()
{

    int N, T, M;
    scanf("%d%d%d", &N, &T, &M);

    // both index are labels
    int label[MAXN+1] = {0};
    int rank[MAXN+1] = {0};
    ll power[MAXN+1];
    label[0] = -1;
    power[0] = -1;

    Vector power_gains[MAXN+1];
    power_gains;
    int attack_times[MAXN+1] = {0};
    for(int i = 1 ; i <= N ; i++){
        label[i] = i;
        rank[i] = i;
        Vector_init(&(power_gains[i]));

        scanf("%lld", &(power[i]));
    }


    for(int i  = 0 ; i < T ; i++){
        int type;
        scanf("%d", &type);
        if(type == 1){
            int attacker;
            scanf("%d", &attacker);
            Attack(label, rank, power, &(power_gains[attacker]), attack_times, attacker, N, M);
            //PrintStatus(label, power, N);
        }
        else if(type == 2){
            Reward(power, N);
            //PrintStatus(label, power, N);
        }
        else if(type == 3){
            ll standard;
            scanf("%lld", &standard);
            Query(label, power, standard, N);
        }
        else if(type == 4){
            int target_label, attack_tms;
            scanf("%d%d", &target_label, &attack_tms);
            GetPowerGains(&(power_gains[target_label]), attack_times, target_label, attack_tms);
        }
        else{
            printf("Wrond type.\n");
            exit(1);
        }
    }
    PrintGameRecord(power_gains, attack_times, N);
    return 0;
}