#include<stdio.h>
#include<stdlib.h>
#include "function.h"
Node* head;
int list[500005][2];
int cmp(const void* a, const void* b){
int* aa = (int*)a,* bb = (int*)b;
if(aa[0] > bb[0]) return 1;
else if(aa[0] == bb[0] && aa[1] > bb[1]) return 1;
return -1;
}
Node* createNode(Node* next, Node* pre, int n){
Node* new = (Node*)malloc(sizeof(Node));
new->age = list[n-1][0];
new->number = n;
new->next = next, new->prev = pre;
next->prev = new, pre->next = new;
return new;
}
Node* createList(int n){
Node* hhead = (Node*)malloc(sizeof(Node)),* tmp;
hhead->prev = hhead->next = hhead, hhead->number = 1;
for(int i=0; i<n; i++){
scanf("%d", &list[i][0]);
list[i][1] = i+1;
}
hhead->age = list[0][0];
tmp = hhead;
for(int i=2; i<=n; i++) tmp = createNode(hhead, tmp, i);
qsort(list, n, 2*sizeof(int), cmp);
while(hhead->age != list[0][0]) hhead = hhead->next;
// for(int i = 0; i < n; i ++){
// printf("%d ", hhead -> age);
// hhead = hhead -> next;
// }
// puts("");
return hhead;
}
Node* solve(int n, int m){
Node* node,* des;
Node** nodes = (Node**)calloc(n+1, sizeof(Node*));
int a, k, num;
char dir;
// node = head;
// for(int i=1; i<=n; i++){
// nodes[node->number] = node;
// node = node->next;
// }
node = head;
while(node->number != 1) node = node->next;
for(int i=1; i<=n; i++){
nodes[i] = node;
node = node->next;
}
for(int i=0; i<m; i++){
scanf("%d %d %c", &a, &k, &dir);
k = k % (n-1);
num = list[a-1][1];
node = nodes[num];
node->prev->next = node->next;
node->next->prev = node->prev;
des = node;
if(dir == 'R'){
while(k--) des = des->next;
des->next->prev = node, node->next = des->next;
node->prev = des, des->next = node;
}
else if(dir == 'L'){
while(k--) des = des->prev;
des->prev->next = node, node->prev = des->prev;
node->next = des, des->prev = node;
}
// node = head;
// for(int i = 0; i < n; i ++){
// printf("%d ", node -> age);
// node = node -> next;
// }
// puts("");
}
return head;
}