#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <math.h>
#include <string.h>

typedef struct node
{
    int data;
    int next;
    int prev;
} list;

void deploy_front(list* set, int* first, int* last, int* n, int indx, int data)
{
    set[*n].data = data;
    if (indx == -1) {
        set[*n].next = *first;
        set[*n].prev = -1;
        set[*first].prev = *n;
        *first = *n;
        if (*last == -1)
            *last = *n;
    }
    else
    {
        set[*n].next = set[indx].next;
        set[*n].prev = indx;
        set[indx].next = *n;

        if (set[*n].next != -1)
        {
            set[set[*n].next].prev = *n;
        }
        else
            *last = *n;
    }

    printf("%d\n", *n);
    *n += 1;
}

void deploy_back(list* set, int* first, int* last, int* n, int indx, int data)
{
    if (indx == -1)
    {
        set[*n].next = -1;
        set[*n].prev = *last;
        set[*last].next = *n;
        *last = *n;
        if (*first == -1)
            *first = *n;
    }
    else
    {
        set[*n].prev = set[indx].prev;
        set[*n].next = indx;
        set[indx].prev = *n;

        if (set[*n].prev != -1)
        {
            set[set[*n].prev].next = *n;
        }
        else
            *first = *n;
    }

    set[*n].data = data;
    printf("%d\n", *n);
    *n += 1;
}

void pop(list* set, int* last, int* first, int indx)
{
    printf("%d\n", set[indx].data);

    if (*last == indx)
        *last = set[indx].prev;

    if (*first == indx)
        *first = set[indx].next;

    if (set[indx].prev != -1)
        set[set[indx].prev].next = set[indx].next;

    if (set[indx].next != -1)
        set[set[indx].next].prev = set[indx].prev;

    if (set[indx].next == -1)
        *last = set[indx].prev;

    if (set[indx].prev == -1)
        *first = set[indx].next;
}


int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    int t = 0;
    scanf("%d", &t);

    for (int k = 0; k < t; k++)
    {
        int n = 0;
        int q = 0;
        int first = 0;
        int last = 0;

        scanf("%d %d %d %d", &n, &first, &last, &q);
        list* arr = (list*)malloc(sizeof(list) * (n + q) + 2);

        for (int i = 0; i < n; i++)
        {
            scanf("%d ", &arr[i].data);
            scanf("%d %d", &arr[i].next, &arr[i].prev);
        }

        for (int i = 0; i < q; i++)
        {
            int indx = 0, act_num = 0;
            scanf("%d %d", &act_num, &indx);

            if (act_num == -1)
            {
                int data = 0;
                scanf("%d", &data);
                deploy_back(arr, &first, &last, &n, indx, data);
            }

            else if (act_num == 0)
            {
                pop(arr, &last, &first, indx);
            }

            else if (act_num == 1)
            {
                int data = 0;
                scanf("%d", &data);
                deploy_front(arr, &first, &last, &n, indx, data);
            }
        }
        printf("===\n");

        while (first != -1)
        {
            printf("%d\n", arr[first].data);
            first = arr[first].next;
        }

        printf("===\n");
    }

    return 0;
}