/*最近在搞考试用的万能函数（因为我打的代码bug太多考试来不及qwq，好不容易写了个链表快速排序函数，就是过不了题，还找不到bug，哭辽*/

#include <iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
using namespace std;


struct sr { double a; char b[10]; };//把所有数据放在这里，以兼容wnlb函数(支持字符串成员）
int bjsr(struct sr* a, struct sr* b)//这是一个重要的比较函数，可以用于查找指定元素（ms5），需要使用这些功能时应该调整，如果不用，只要使这个函数有返回值即可
{
    if ((*(a)).a == (*(b)).a) {
        return 0;
    }
    if ((*(a)).a >(*(b)).a) {
        return 1;
    }
    if ((*(a)).a <(*(b)).a) {
        return -1;
    }
}
struct lb { struct sr sj; struct lb* next; struct lb* qmd; };//最好不要改动.如果需要空表提示，进入248行修改
void wnlb(struct lb** tou1,struct lb** wei1,struct lb**qjd1,struct lb** jd,int ms,int* fhz, struct lb** tou2, struct lb** wei2, struct lb** qjd2)
//要求tou1、wei1、qjd1、tou2、wei2、qjd2为链表指针，jd为链表指针（malloc申请lb空间），fhz为某些模式传入值、返回值变量，均传地址。ms-1尾插链接双链表节点，ms0头插链接单链表节点(可以用来搞栈，或者顶替反转链表操作），ms1尾插链接单链表节点，ms2反转链表，ms3清空链表，
// ms4计算链表元素个数，结果存在fhz中，ms5查找指定元素，要求提前将此元素存在jd中，从qjd1所在位开始搜索（需要在开始时令其为tou1），返回为指定值的jd的next到qjd1
//（可直接传入wnlb从此处继续搜索相同元素），返回fhz表示此元素位置，没有回0,注意如果想让函数自己算出每一个相同元素所在的位置，在搜索工作循环里不能修改fhz的值，它被用于记录每一次搜索完时该元素的位置
// ms6查找指定位的元素，指定位存在fhz中，求中间节点fhz为0，求倒数节点fhz为负数，返回找到的元素的sj存在jd中，返回值所在的位数存在fhz中，若没有，fhz返回0,不传回jd，千万注意储存jd初始值以免程序挂掉！！！
//ms7在指定节点（从1开始）后插入元素，头插输入0，直接尾插输入-1(双链表时才可用），节点存在jd里，插入失败返回0于fhz，指定位存在fhz里,ms8删除指定位置节点,指定位存在fhz里，直接尾删输入-1(双链表时才可用）,删除失败返回0于fhz,
//ms9对双链表快排,要求提前编好bjsr函数,
{
    struct lb* tou = *(tou1); struct lb* wei = *(wei1); struct lb* htou = *(tou2); struct lb* hwei = *(wei2); if (ms != -1 && ms != 0 && ms != 1 && tou == NULL) { return; }
    if (ms == 1||ms==0||ms==-1) 
    {
        struct lb* qjd = *(qjd1);
        struct lb* zjd = (struct lb*)malloc(sizeof(struct lb)); zjd->sj = (*(jd))->sj; zjd->qmd = NULL;// printf("%d %p\n", zjd->sj.a,zjd);
        if (tou != NULL && qjd != NULL && ms == 0) { zjd->next = tou; tou = zjd; }
        if (tou != NULL && qjd != NULL && ms == 1) { qjd->next = zjd; zjd->next = wei; qjd = zjd; }
        if (tou != NULL && qjd != NULL && ms == -1) { qjd->next = zjd; zjd->next = wei; qjd = zjd; }
        if (tou == NULL) { tou = zjd;  zjd->next = wei; qjd = zjd;}
        if (ms == -1) 
        {
            if (htou != NULL) { zjd->qmd = *(qjd1); htou = zjd; }
            if (htou == NULL) { htou = zjd; zjd->qmd = hwei; }
        }

        *(tou1) = tou; *(wei1)= wei; *(qjd1) = qjd; *(tou2) = htou; *(wei2) = hwei; return;
    }
    if (ms == 2)//(反转单链表)
    {
        if (tou != NULL)
        {
            struct lb* h2 = NULL; struct lb* h1 = tou; struct lb* h3 = NULL;
            while (h1)
            {
                if (h1->next == wei) { wei = h1; }
                //printf("e%d %d\n", h1, h1->sj.a);
                h3 = h1->next; h1->next = h2; h2 = h1;  //h1 = h3; //if (h1->next == wei) { printf("jin"); wei = h1; }
                if (h1 != NULL)
                {
                    //printf("e=p=%d %d\n", h1->sj.a, h1->next);
                } h1 = h3;
            }tou->next = h1;
            *(tou1) = wei; *(wei1) = h1;
        }return;
    }
    if (ms == 3)//删除链表
    {
        struct lb* bl = tou; struct lb* b2 = tou;
        if (tou == NULL) { printf("kongde" ); return; }
        while (bl != wei)
        {
            b2 = bl; bl = bl->next; b2->next = bl; free(b2);
        } *(tou1) = NULL; *(wei1) = NULL; *(tou2) = NULL; *(wei2) = NULL; return;
    }
    if (ms == 4||ms==5||ms==6)
    {
        int a = 0; struct lb* k = tou; if (ms == 5) { k = *(qjd1); }
        for (struct lb* i = k; i != wei; i = i->next)
        {
            if (ms == 5) 
            {
                if (bjsr(&(i->sj), &(*(jd))->sj) == 0)
                {
                    int b; if (k == tou) { b = 0; }else { b = *(fhz); }
                    a++; *(fhz) = a + b; *(qjd1) = i->next;return;
                }
            }
            if (ms == 6)//0时k是快指针，一次跳两格（k从指1到3，3到5）若总元素数为单数，k最后指向最后一个元素，i走到中间的前一个元素，让i再走一步返回，若为偶数，指向wei,i刚好走一半，可直接返回
                //负数时因为a最后加1，实际应该在2时慢指针k才启动，k要比i少走倒数的步数，所以fhz+a=-1时在1的位置，传回fhz时应该加2
            {
                if (*(fhz) == 0 && k->next == wei) { (* (jd))->sj = i->sj; *(fhz) = a + 1;  return; }
                if (*(fhz) == 0 && k!=wei && k->next!=wei){k = k->next->next;}
                if (*(fhz) == 0 && k == wei) { (*(jd))->sj = i->sj; *(fhz) = a+1;  return; }
                if (*(fhz) > 0) { if (a == *(fhz)-1) { (*(jd))->sj = i->sj; return; } }
                if (*(fhz) < 0 && *(fhz)+a >= 0) { k = k->next; }
                if (*(fhz) < 0 && i->next == wei && *(fhz)+a >= -1) { (*(jd))->sj = k->sj; *(fhz) = a + *(fhz)+2; return; }
            }
            a++;
        }if (ms == 5||ms==6) { a = 0; }*(fhz) = a; return;
    }
    if (ms == 7||ms==8)
    {
        struct lb* a = (struct lb*)malloc(sizeof(struct lb)); int b=0;
        if (ms == 7) { a->sj = (*(jd))->sj; a->next = NULL; } struct lb* c = tou;
        if (*(fhz) == 0&&ms==7)
        {
            a->next = tou; if (htou != NULL) { tou->qmd = a; a->qmd = hwei; *(wei2) = hwei; } tou = a;  *(tou1) = tou;  return;
        }
        if (*(fhz) == -1&& ms == 7)
        {
            if (htou == NULL) { printf("双链表才能直接尾插\n"); return; }
            a->qmd = htou; htou->next = a; a->next = wei; htou = a; *(tou2) = htou; *(wei1) = wei; return;
        }
        if (*(fhz) == 1 && ms == 8)
        {
            tou = c->next; if (htou != NULL) { if (tou != wei) { tou->qmd = *(wei2); }if (tou == wei) { *(tou2) = NULL; } } free(c); *(tou1) = tou; return;
        }
        if (*(fhz) == -1 && ms == 8)
        {
            if (htou == NULL) { printf("双链表才能直接尾删\n"); return; }
            struct lb* d = htou; htou = d->qmd; if (htou != hwei) { htou->next = *(wei1); }if (htou == hwei) { *(tou1) = NULL; } *(tou2) = htou; free(d); return;
        }
        for (struct lb* i = tou; i != wei; i = i->next)
        {
            b++;
            if (b == *(fhz)&&ms==7)
            {
                c = i->next; i->next = a; a->next = c; if (htou != NULL) { a->qmd = i; if (htou != i) { a->next->qmd = a; } if (htou == i) { htou = a; *(tou2) = htou; } }return;
            }
            if (b == *(fhz)-1 && ms == 8){c = i;}
            if (b == *(fhz) && ms == 8)
            {
                c->next = i->next; if (htou != NULL) { if (htou != i) { i->next->qmd = c; }if (htou == i) { *(tou2) = c; } } free(i); return;
            }
        }*(fhz) = 0;
    }
    if (ms == 9)//实验表明，如果用复制的tou参与排序并在排序中不修改*（tou1）的值，就不会改动真正的头指针，同时，将复制的tou传入函数可以正常通过递归排序
    {
        if (htou == NULL) { printf("你应该建立一个双链表\n"); return; }
        struct lb* i = tou; struct lb* j = htou; struct lb* a = tou; struct lb* b = NULL;
        if (!tou || tou->next == wei || tou == wei) {return; }
        for (i = a->next; i != wei; i = i->next)
        {
            if (i!=NULL&&i!=wei&&bjsr(&i->sj, &a->sj) < 0)
            {
                struct lb* e = (struct lb*)malloc(sizeof(struct lb));
                b = i->qmd; e->sj = i->sj;
                e->next = tou; tou->qmd = e; e->qmd = hwei; tou = e; 
                b->next = i->next; if (htou != i) { i->next->qmd = b; }
                else { htou = b; }free(i);
                i = b;
            }
        }
        if (a->next != wei&&i!=NULL) { b = a->next->qmd; }else { b = htou; }
       wnlb(&tou, &a, NULL, NULL, 9, NULL, &b, &hwei, NULL);
       wnlb(&a->next, &wei, NULL, NULL, 9, NULL, &htou, &a, NULL); *(tou1) = tou; *(tou2) = htou;
    }
    if (ms == 10)
    {
        if (*(qjd1) = *(qjd2)) { *(fhz) = 0; return; }
        for (struct lb* i = tou; i != wei; i = i->next)
        {
            if (i == *(qjd1)) { *(fhz) = -1; return; }
            if (i == *(qjd2)) { *(fhz) = 1; return; }
        }*(fhz) = -2; return;
    }
}

int main()
{
    {
        int fhz; struct lb* k1 = NULL; struct lb* l1 = NULL; struct lb* qjd1 = NULL;
        struct lb* k = NULL; struct lb* l = NULL; struct lb* m = (struct lb*)malloc(sizeof(struct lb)); struct lb* qjd = NULL;
        int fhznb; struct lb* k1nb = NULL; struct lb* l1nb = NULL; struct lb* qjd1nb = NULL;
        struct lb* knb = NULL; struct lb* lnb = NULL; struct lb* mnb = (struct lb*)malloc(sizeof(struct lb)); struct lb* qjdnb = NULL;
        int a = 0; int b = 0,c=0;
        scanf("%d", &c);
        for(int x=0;x<c;x++)
        {
            scanf("%d", &b); int d[1000];
            for (int y = 0; y < b; y++)
            {
                scanf("%d", &d[y]);
            }
            for (int y = 0; y < b; y++)
            {
                if (d[y] == 0) {cin>> m->sj.a;wnlb(&k, &l, &qjd, &m, -1, &fhz, &k1, &l1, &qjd1); }
                if (d[y] == 1) { cin>> mnb->sj.a; wnlb(&knb, &lnb, &qjdnb, &mnb, -1, &fhznb, &k1nb, &l1nb, &qjd1nb);
                }
            } wnlb(&k, &l, &qjd, &m, 9, &fhz, &k1, &l1, &qjd1);// wnlb(&knb, &lnb, &qjdnb, &mnb, 9, &fhznb, &k1nb, &l1nb, &qjd1nb);
            for (struct lb* i = k; i != l; i = i->next)//从链表tou开始遍历示例
            {
                //if (j != a - 1) 
                { cout<<i->sj.a<<" "; }
               // else { printf("%g", i->sj.a); }
                
            }if(k!=NULL){printf("\n");}
            for (struct lb* i = knb; i != lnb; i = i->next)//从链表tou开始遍历示例
            {
                //if (j != a - 1) 
                {  cout<<i->sj.a<<" "; }
                // else { printf("%g", i->sj.a); }

            }if(knb!=NULL){printf("\n");}
        }
    }
    return 0;
}