#define MaxSize 50
typedef struct {
    int data[MaxSize];  // 存放数据元素
    int length;          // 当前长度
} SqList;

int GetElem(SqList L, int i) {
    return L.data[i-1];  // 位序从1开始，数组下标从0开始
}

int LocateElem(SqList L, int e) {
    for (int i = 0; i < L.length; i++)
        if (L.data[i] == e) return i + 1;  // 返回位序
    return 0;
}

bool ListInsert(SqList *L, int i, int e) {
    if (i < 1 || i > L->length + 1) return false;  // 位置合法性
    if (L->length >= MaxSize) return false;          // 表满
    for (int j = L->length; j >= i; j--)
        L->data[j] = L->data[j-1];  // 从后往前逐个后移
    L->data[i-1] = e;               // 放入新元素
    L->length++;
    return true;
}

bool ListDelete(SqList *L, int i, int *e) {
    if (i < 1 || i > L->length) return false;
    *e = L->data[i-1];               // 取出被删元素
    for (int j = i; j < L->length; j++)
        L->data[j-1] = L->data[j];  // 从前往后逐个前移
    L->length--;
    return true;
}

typedef struct LNode {
    int data;              // 数据域
    struct LNode *next;    // 指针域
} LNode, *LinkList;

bool ListInsert(LinkList L, int i, int e) {
    LNode *p = L;           // p 指向头结点
    int j = 0;              // j 记录当前位序
    // 找到第 i-1 个结点
    while (p && j < i - 1) {
        p = p->next;
        j++;
    }
    if (!p || j > i - 1) return false;  // i 不合法
    // 插入新结点
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;  // ① 先连后（s 指向 p 的后继）
    p->next = s;         // ② 再连前（p 指向 s）
    return true;
}

bool ListDelete(LinkList L, int i, int *e) {
    LNode *p = L;
    int j = 0;
    while (p->next && j < i - 1) {  // 注意是 p->next
        p = p->next; j++;
    }
    if (!(p->next) || j > i - 1) return false;
    LNode *q = p->next;     // q 指向待删结点
    *e = q->data;            // 取出数据
    p->next = q->next;       // 绕过 q
    free(q);                 // 释放 q
    return true;
}

LinkList HeadInsert(LinkList L) {
    LNode *s; int x;
    L = (LinkList)malloc(sizeof(LNode));  // 创建头结点
    L->next = NULL;
    scanf("%d", &x);
    while (x != 9999) {                   // 9999 为结束标志
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;   // s 指向原第一个结点
        L->next = s;          // 头结点指向 s
        scanf("%d", &x);
    }
    return L;
}

LinkList TailInsert(LinkList L) {
    LNode *s, *r; int x;
    L = (LinkList)malloc(sizeof(LNode));
    r = L;                              // r 始终指向尾结点
    scanf("%d", &x);
    while (x != 9999) {
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;         // 尾结点指向新结点
        r = s;                // r 更新为新的尾结点
        scanf("%d", &x);
    }
    r->next = NULL;           // 尾结点指针置空
    return L;
}

LNode *LocateElem(LinkList L, int e) {
    LNode *p = L->next;      // 从第一个数据结点开始
    while (p && p->data != e)
        p = p->next;
    return p;                 // 找到返回结点指针，没找到返回 NULL
}

int Length(LinkList L) {
    int len = 0;
    LNode *p = L->next;
    while (p) { len++; p = p->next; }
    return len;
}

typedef struct DNode {
    int data;
    struct DNode *prior, *next;  // 前驱和后继指针
} DNode, *DLinkList;

s->next = p->next;       // ① s 的后继指向 p 的后继
p->next->prior = s;      // ② p 的后继的前驱指向 s（若非尾结点）
s->prior = p;            // ③ s 的前驱指向 p
p->next = s;             // ④ p 的后继指向 s

p->next = q->next;
if (q->next != NULL)       // 若 q 不是最后一个结点
    q->next->prior = p;
free(q);

// 将表 B 接到表 A 后面
s = B->next->next;       // B 的第一个数据结点
B->next = A->next;       // B 的尾指向 A 的头
A->next = s;             // A 的尾指向 B 的第一个数据结点

#define MaxSize 50
typedef struct {
    int data;
    int next;  // 下一个元素的数组下标（不是指针）
} SLinkList[MaxSize];

void Reverse(LinkList L) {
    LNode *p = L->next, *q;
    L->next = NULL;
    while (p) {
        q = p->next;
        p->next = L->next;  // 头插
        L->next = p;
        p = q;
    }
}

// p 先走 k 步，然后 p、q 一起走，p 到末尾时 q 就是倒数第 k 个
LNode *FindKth(LinkList L, int k) {
    LNode *p = L->next, *q = L->next;
    for (int i = 0; i < k; i++) p = p->next;
    while (p) { p = p->next; q = q->next; }
    return q;
}

// slow 走一步，fast 走两步，fast 到末尾时 slow 在中间
LNode *FindMid(LinkList L) {
    LNode *slow = L->next, *fast = L->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

bool HasCycle(LinkList L) {
    LNode *slow = L->next, *fast = L->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;  // 相遇则有环
    }
    return false;
}

#define MaxSize 50
typedef struct {
    int data[MaxSize];
    int top;  // 栈顶指针，指向当前栈顶元素的位置
} SqStack;

bool Push(SqStack *S, int x) {
    if (S->top == MaxSize - 1) return false;  // 栈满
    S->data[++S->top] = x;  // 先 top++ 再赋值
    return true;
}

bool Pop(SqStack *S, int *x) {
    if (S->top == -1) return false;  // 栈空
    *x = S->data[S->top--];  // 先取值再 top--
    return true;
}

typedef struct {
    int data[MaxSize];
    int top1;  // 栈1栈顶（从 -1 开始）
    int top2;  // 栈2栈顶（从 MaxSize 开始）
} ShStack;

typedef struct StackNode {
    int data;
    struct StackNode *next;
} StackNode, *LinkStack;

#define MaxSize 50
typedef struct {
    int data[MaxSize];
    int front, rear;  // 队头和队尾指针
} SqQueue;

bool EnQueue(SqQueue *Q, int x) {
    if ((Q->rear + 1) % MaxSize == Q->front) return false;  // 队满
    Q->data[Q->rear] = x;
    Q->rear = (Q->rear + 1) % MaxSize;
    return true;
}

bool DeQueue(SqQueue *Q, int *x) {
    if (Q->front == Q->rear) return false;  // 队空
    *x = Q->data[Q->front];
    Q->front = (Q->front + 1) % MaxSize;
    return true;
}

typedef struct QNode {
    int data;
    struct QNode *next;
} QNode;

typedef struct {
    QNode *front, *rear;  // 队头和队尾指针
} LinkQueue;

bool DeQueue(LinkQueue *Q, int *x) {
    if (Q->front == Q->rear) return false;
    QNode *p = Q->front->next;
    *x = p->data;
    Q->front->next = p->next;
    if (Q->rear == p)  // 若删的是最后一个元素
        Q->rear = Q->front;
    free(p);
    return true;
}

void Convert(int n, int base) {
    SqStack S; InitStack(&S);
    while (n) {
        Push(&S, n % base);
        n /= base;
    }
    while (!StackEmpty(S)) {
        Pop(&S, &n);
        printf("%d", n);
    }
}

typedef struct {
    int i, j;   // 行号、列号
    int value;  // 值
} Triple;

typedef struct {
    Triple data[MaxSize];
    int rows, cols, nums;  // 行数、列数、非零元素个数
} TSMatrix;

int Index(SString S, SString T) {
    int i = 1, j = 1;  // S 和 T 的下标从 1 开始
    while (i <= S.length && j <= T.length) {
        if (S.ch[i] == T.ch[j]) {
            i++; j++;  // 匹配则继续比较下一个
        } else {
            i = i - j + 2;  // 主串指针回退到本趟开始的下一个位置
            j = 1;           // 模式串指针归 1
        }
    }
    if (j > T.length) return i - T.length;  // 匹配成功
    return 0;  // 匹配失败
}

void GetNext(char *T, int *next) {
    int i = 1, j = 0;
    next[1] = 0;
    while (i < T[0]) {  // T[0] 存储串长度
        if (j == 0 || T[i] == T[j]) {
            i++; j++;
            next[i] = j;
        } else {
            j = next[j];  // j 回退
        }
    }
}

int KMP(char *S, char *T, int *next) {
    int i = 1, j = 1;
    while (i <= S[0] && j <= T[0]) {
        if (j == 0 || S[i] == T[j]) {
            i++; j++;  // 匹配或 j 回退到 0 时，都前进
        } else {
            j = next[j];  // 主串 i 不动，模式串 j 回退
        }
    }
    if (j > T[0]) return i - T[0];  // 匹配成功
    return 0;
}

void GetNextval(char *T, int *nextval) {
    int i = 1, j = 0;
    nextval[1] = 0;
    while (i < T[0]) {
        if (j == 0 || T[i] == T[j]) {
            i++; j++;
            if (T[i] != T[j]) nextval[i] = j;
            else nextval[i] = nextval[j];  // 关键改进
        } else {
            j = nextval[j];
        }
    }
}

typedef struct BiTNode {
    int data;
    struct BiTNode *lchild, *rchild;  // 左右孩子指针
} BiTNode, *BiTree;

typedef struct BiTNode {
    int data;
    struct BiTNode *lchild, *rchild, *parent;
} BiTNode, *BiTree;

void PreOrder(BiTree T) {
    if (T) {
        visit(T);                  // 访问根
        PreOrder(T->lchild);       // 遍历左子树
        PreOrder(T->rchild);       // 遍历右子树
    }
}

void InOrder(BiTree T) {
    if (T) {
        InOrder(T->lchild);        // 遍历左子树
        visit(T);                  // 访问根
        InOrder(T->rchild);        // 遍历右子树
    }
}

void PostOrder(BiTree T) {
    if (T) {
        PostOrder(T->lchild);      // 遍历左子树
        PostOrder(T->rchild);      // 遍历右子树
        visit(T);                  // 访问根
    }
}

void LevelOrder(BiTree T) {
    Queue Q;
    InitQueue(&Q);
    EnQueue(&Q, T);
    while (!IsEmpty(Q)) {
        DeQueue(&Q, &p);
        visit(p);
        if (p->lchild) EnQueue(&Q, p->lchild);
        if (p->rchild) EnQueue(&Q, p->rchild);
    }
}

void InOrder2(BiTree T) {
    SqStack S; InitStack(&S);
    BiTree p = T;
    while (p || !StackEmpty(S)) {
        if (p) {
            Push(&S, p);          // 入栈
            p = p->lchild;        // 一路向左
        } else {
            Pop(&S, &p);          // 出栈
            visit(p);              // 访问
            p = p->rchild;        // 转向右子树
        }
    }
}

typedef struct ThreadNode {
    int data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag;  // 0: 指向孩子  1: 指向前驱/后继（线索）
} ThreadNode, *ThreadTree;

ThreadNode *pre = NULL;  // 全局变量，指向前驱

void InThread(ThreadTree T) {
    if (T) {
        InThread(T->lchild);           // 线索化左子树
        // 处理当前结点
        if (!T->lchild) {              // 左子树为空
            T->ltag = 1;               // 标记为线索
            T->lchild = pre;           // 指向前驱
        }
        if (pre && !pre->rchild) {     // 前驱的右子树为空
            pre->rtag = 1;             // 标记为线索
            pre->rchild = T;           // 前驱指向当前（后继）
        }
        pre = T;                       // 更新前驱
        InThread(T->rchild);           // 线索化右子树
    }
}

// 找中序下的第一个结点（最左下）
ThreadNode *FirstNode(ThreadNode *p) {
    while (p->ltag == 0) p = p->lchild;
    return p;
}

// 找中序下的后继
ThreadNode *NextNode(ThreadNode *p) {
    if (p->rtag == 1) return p->rchild;  // 有线索直接用
    return FirstNode(p->rchild);          // 否则找右子树的最左
}

// 遍历
void InOrderThread(ThreadTree T) {
    for (ThreadNode *p = FirstNode(T); p; p = NextNode(p))
        visit(p);
}

typedef struct {
    int data;
    int parent;  // 父结点下标，-1 表示无父结点
} PTNode;

typedef struct {
    PTNode nodes[MaxSize];
    int n;  // 结点数
} PTree;

typedef struct CSNode {
    int data;
    struct CSNode *firstchild;    // 第一个孩子
    struct CSNode *nextsibling;   // 下一个兄弟
} CSNode, *CSTree;

#define MaxVertexNum 100
typedef struct {
    char vex[MaxVertexNum];              // 顶点表
    int edge[MaxVertexNum][MaxVertexNum]; // 邻接矩阵
    int vexnum, arcnum;                  // 顶点数、边数
} MGraph;

typedef struct ArcNode {
    int adjvex;              // 邻接点下标
    int weight;              // 边的权值（网图用）
    struct ArcNode *next;    // 指向下一条边
} ArcNode;

typedef struct {
    char data;               // 顶点数据
    ArcNode *first;          // 第一条边
} VNode, AdjList[MaxVertexNum];

typedef struct {
    AdjList vertices;
    int vexnum, arcnum;
} ALGraph;

bool visited[MaxVertexNum];

void BFS(Graph G, int v) {
    visit(v);
    visited[v] = true;
    EnQueue(Q, v);
    while (!IsEmpty(Q)) {
        DeQueue(Q, &v);
        for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) {
            if (!visited[w]) {
                visit(w);
                visited[w] = true;
                EnQueue(Q, w);
            }
        }
    }
}

// 处理非连通图
void BFSTraverse(Graph G) {
    for (int i = 0; i < G.vexnum; i++) visited[i] = false;
    for (int i = 0; i < G.vexnum; i++)
        if (!visited[i]) BFS(G, i);  // 对每个连通分量调用 BFS
}

void DFS(Graph G, int v) {
    visit(v);
    visited[v] = true;
    for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) {
        if (!visited[w])
            DFS(G, w);
    }
}

void DFSTraverse(Graph G) {
    for (int i = 0; i < G.vexnum; i++) visited[i] = false;
    for (int i = 0; i < G.vexnum; i++)
        if (!visited[i]) DFS(G, i);
}

void Floyd(MGraph *G) {
    for (int k = 0; k < G->vexnum; k++)        // 中间点
        for (int i = 0; i < G->vexnum; i++)     // 起点
            for (int j = 0; j < G->vexnum; j++) // 终点
                if (G->edge[i][k] + G->edge[k][j] < G->edge[i][j])
                    G->edge[i][j] = G->edge[i][k] + G->edge[k][j];
}

int SeqSearch(int A[], int n, int key) {
    for (int i = 0; i < n; i++)
        if (A[i] == key) return i;
    return -1;
}

int SeqSearch_Sentinel(int A[], int n, int key) {
    A[0] = key;  // 哨兵
    int i = n;
    while (A[i] != key) i--;
    return i;  // 返回 0 表示失败
}

int BinarySearch(int A[], int n, int key) {
    int low = 0, high = n - 1, mid;
    while (low <= high) {
        mid = (low + high) / 2;
        if (A[mid] == key) return mid;
        else if (A[mid] > key) high = mid - 1;
        else low = mid + 1;
    }
    return -1;
}

BSTNode *BST_Search(BiTree T, int key) {
    while (T && T->data != key) {
        if (key < T->data) T = T->lchild;
        else T = T->rchild;
    }
    return T;
}

BSTNode *BST_Search_Recursive(BiTree T, int key) {
    if (!T || T->data == key) return T;
    if (key < T->data) return BST_Search_Recursive(T->lchild, key);
    else return BST_Search_Recursive(T->rchild, key);
}

bool BST_Insert(BiTree *T, int key) {
    if (!(*T)) {
        *T = (BiTree)malloc(sizeof(BiTNode));
        (*T)->data = key;
        (*T)->lchild = (*T)->rchild = NULL;
        return true;
    }
    if (key == (*T)->data) return false;  // 已存在
    if (key < (*T)->data) return BST_Insert(&(*T)->lchild, key);
    else return BST_Insert(&(*T)->rchild, key);
}

void InsertSort(int A[], int n) {
    int i, j, temp;
    for (i = 1; i < n; i++) {  // 从第二个元素开始
        if (A[i] < A[i-1]) {
            temp = A[i];
            for (j = i - 1; j >= 0 && A[j] > temp; j--)
                A[j+1] = A[j];  // 后移
            A[j+1] = temp;       // 插入
        }
    }
}

void BinaryInsertSort(int A[], int n) {
    int i, j, temp, low, high, mid;
    for (i = 1; i < n; i++) {
        temp = A[i];
        low = 0; high = i - 1;
        // 折半查找插入位置
        while (low <= high) {
            mid = (low + high) / 2;
            if (A[mid] > temp) high = mid - 1;
            else low = mid + 1;
        }
        // 移动元素
        for (j = i - 1; j >= high + 1; j--)
            A[j+1] = A[j];
        A[high+1] = temp;
    }
}

void ShellSort(int A[], int n) {
    int dk, i, j, temp;
    for (dk = n/2; dk >= 1; dk /= 2) {      // 增量序列
        for (i = dk; i < n; i++) {            // 从第 dk 个开始
            if (A[i] < A[i - dk]) {
                temp = A[i];
                for (j = i - dk; j >= 0 && A[j] > temp; j -= dk)
                    A[j + dk] = A[j];
                A[j + dk] = temp;
            }
        }
    }
}

void BubbleSort(int A[], int n) {
    for (int i = 0; i < n - 1; i++) {
        bool flag = false;  // 本趟是否有交换
        for (int j = n - 1; j > i; j--) {  // 从后往前
            if (A[j-1] > A[j]) {
                swap(A[j-1], A[j]);
                flag = true;
            }
        }
        if (!flag) break;  // 无交换说明已有序
    }
}

int Partition(int A[], int low, int high) {
    int pivot = A[low];  // 选第一个元素为基准
    while (low < high) {
        while (low < high && A[high] >= pivot) high--;
        A[low] = A[high];          // 比 pivot 小的移到左边
        while (low < high && A[low] <= pivot) low++;
        A[high] = A[low];          // 比 pivot 大的移到右边
    }
    A[low] = pivot;  // pivot 放到最终位置
    return low;
}

void QuickSort(int A[], int low, int high) {
    if (low < high) {
        int pivotpos = Partition(A, low, high);
        QuickSort(A, low, pivotpos - 1);    // 排左半部分
        QuickSort(A, pivotpos + 1, high);   // 排右半部分
    }
}

void SelectSort(int A[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++)
            if (A[j] < A[min]) min = j;
        if (min != i) swap(A[i], A[min]);
    }
}

void HeadAdjust(int A[], int k, int len) {
    A[0] = A[k];  // 暂存根
    for (int i = 2*k; i <= len; i *= 2) {  // 沿较大的孩子向下
        if (i < len && A[i] < A[i+1])      // 右孩子更大
            i++;
        if (A[0] >= A[i]) break;            // 根已最大
        A[k] = A[i]; k = i;                // 孩子上移
    }
    A[k] = A[0];
}

void BuildMaxHeap(int A[], int len) {
    for (int i = len/2; i >= 1; i--)
        HeadAdjust(A, i, len);
}

void HeapSort(int A[], int len) {
    BuildMaxHeap(A, len);              // 建堆
    for (int i = len; i > 1; i--) {
        swap(A[1], A[i]);              // 堆顶（最大）移到末尾
        HeadAdjust(A, 1, i-1);         // 对前 i-1 个元素重新调整
    }
}

void HeapInsert(int A[], int k) {
    int i = k;
    A[0] = A[i];
    while (i > 1 && A[i/2] < A[0]) {
        A[i] = A[i/2];
        i = i / 2;
    }
    A[i] = A[0];
}

int *B;  // 辅助数组

void Merge(int A[], int low, int mid, int high) {
    for (int k = low; k <= high; k++) B[k] = A[k];  // 复制到辅助数组
    int i = low, j = mid + 1, k = low;
    while (i <= mid && j <= high) {
        if (B[i] <= B[j]) A[k++] = B[i++];  // 取较小的
        else A[k++] = B[j++];
    }
    while (i <= mid) A[k++] = B[i++];  // 左边剩余
    while (j <= high) A[k++] = B[j++]; // 右边剩余
}

void MergeSort(int A[], int low, int high) {
    if (low < high) {
        int mid = (low + high) / 2;
        MergeSort(A, low, mid);        // 排左半
        MergeSort(A, mid + 1, high);   // 排右半
        Merge(A, low, mid, high);      // 合并
    }
}