#include <stdio.h>
#include <stdlib.h>
// Define structure for a circular linked list node
typedef struct Node {
    int data;
    struct Node* next;
} Node;
// Function to create a new node
Node* createNode(int data){
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode){
        printf("Memory error\n");
        return NULL;
    }
newNode->data = data;
newNode->next = newNode; // Point next to itself for circular
return newNode;
}
// Function to insert a node at the end of a circular linked list
void insertNode(Node** head, int data){
    Node* newNode = createNode(data);
    if (*head == NULL){
        *head = newNode;
    } else {
        Node* temp = *head;
        while (temp->next != *head){
            temp = temp->next;
        }
    temp->next = newNode;
    newNode->next = *head;
    }
}
// Function to split the circular linked list into even and odd lists
void splitCircularList(Node* head, Node** evenHead, Node** oddHead){
    if (head == NULL) return;
Node* evenTail = NULL;
Node* oddTail = NULL;
Node*temp = head;
 do {
     if (temp->data % 2 == 0){
         if (*evenHead == NULL){
             *evenHead = temp;
             evenTail = *evenHead;         
     } else {
         evenTail->next = temp;
         evenTail = temp;
     }
     } else {
         if (*oddHead == NULL){
             *oddHead = temp;
             oddTail = *oddHead;
         } else {
             oddTail->next = temp;
             oddTail = temp;
         }
     }
     temp = temp->next;
 }while (temp != head);
 // Make lists circlar
 if (evenTail)evenTail->next = *evenHead;
 if (oddTail) oddTail->next = *oddHead;
}
// Function to print a circular linked list
void printCircularList(Node*head){
    if (head == NULL) return;
    Node* temp = head;
    do {
        printf("%d ", temp->data);
        temp = temp->next;
    }while (temp !=head);
    printf("\n");
}
// Main function to test the implementation
int main(){
    int n;
    scanf("%d" , &n);
    if (n < 0){
        printf("Invalid input\n");
        return 0;
    }
int values[n];
for (int i = 0; i < n; i++){
    scanf("%d" , &values[i]);
    if (values[i] < 0){
        printf("Invalid input\n");
        return 0;
    }
}
Node* head = NULL:
for (int i = 0; i < n; i++){
    insertNode(&head, values[i]);
}
Node* evenHead = NULL;
Node* oddHead = NULL:
splitCircularList(head, &evenHead, &oddHead);
printCircularList(evenHead);
printCircularList(oddHead);
return 0;
}
}