/**********************************************************************
* Section : 15
* Machine No. : N
* Roll No. : 19CS100XY
* Name : Aritra Hazra
* Assignment No : LT-1-EVEN-A
* Description : Delete Set of Intervals from Existing Set of Intervals
**********************************************************************/

#include <stdio.h>

#define MAX 100000

int main()
{
    int n, m, t, i, j;
    int existLeftInterval[MAX], existRightInterval[MAX];
    int newLeftInterval[MAX], newRightInterval[MAX];
    int finalLeftInterval[MAX], finalRightInterval[MAX];
    
    // scanning existing interval information from user
    printf("Enter Number of Existing Intervals: ");
    scanf("%d", &n);
    printf("Enter %d Existing Intervals:\n", n);
    for (i=0; i<n; i++) {
        printf("\tEnter Interval-%d: ", i+1);
        scanf("%d", &existLeftInterval[i]);
        scanf("%d", &existRightInterval[i]);
    }
    // scanning new (to be deleted) interval information from user
    printf("\nEnter Number of New Intervals: ");
    scanf("%d", &m);
    printf("Enter %d New Intervals to Delete:\n", m);
    for (i=0; i<m; i++) {
        printf("\tDelete Interval-%d: ", i+1);
        scanf("%d", &newLeftInterval[i]);
        scanf("%d", &newRightInterval[i]);
    }

    // printing existing interval information
    printf("\n++ Existing Intervals:");
    for (i=0; i<n; i++) {
        printf(" [ %d, %d ];", existLeftInterval[i], existRightInterval[i]);
    }
    // printing deleting interval information
    printf("\n++ Deleting Intervals:");
    for (i=0; i<m; i++) {
        printf(" [ %d, %d ];", newLeftInterval[i], newRightInterval[i]);
    }
    
    for(i=0,j=0,t=0; (i<n)&&(j<m); ) {
        // inserting all existing intervals that ends before the start of the first new interval
        if (existRightInterval[i] < newLeftInterval[j]){
            finalLeftInterval[t] = existLeftInterval[i];
            finalRightInterval[t] = existRightInterval[i];
            t++; i++;
        }
        // ignoring all new intervals that ends before the start of the first existing interval
        else if (newRightInterval[j] < existLeftInterval[i]) {
            j++;
        }
        // when new interval overlaps with current existing interval
        else {
            // start of the new interval is before or equal-with the start of the existing interval
            if (newLeftInterval[j] <= existLeftInterval[i]) {
                // end of the new interval is before the end of the existing interval
                if (newRightInterval[j] < existRightInterval[i]) {
                    finalLeftInterval[t] = newRightInterval[j];
                    // next deleted interval starts before the end of current existing interval
                    if ((j<m-1) && (newLeftInterval[j+1] < existRightInterval[i])) {
                        finalRightInterval[t] = newLeftInterval[j+1];
                        j++; t++;
                        if(existRightInterval[i] < newRightInterval[j]) // consider next existing interval
                            i++;
                    }
                    // next deleted interval starts after the end of current existing interval
                    else {
                        finalRightInterval[t] = existRightInterval[i];
                        i++; j++; t++;
                    }
                }
                // end of the new interval is after the end of the existing interval
                else {
                    // next existing interval starts before the end of current deleting interval
                    if ((i<n-1) && (existLeftInterval[i+1] < newRightInterval[j])) {
                        i++;
                    }
                    // next existing interval starts after the end of current deleting interval
                    else {
                        j++; i++;
                    }
                }
            }
            // start of the new interval is somewhere in-between (after the start of) the current existing interval
            else {
                finalLeftInterval[t] = existLeftInterval[i];
                finalRightInterval[t] = newLeftInterval[j];
                if(finalLeftInterval[t] > finalRightInterval[t-1]) // allow only valid existing intervals
                    t++;
                // end of the new interval is before the end of the existing interval
                if (newRightInterval[j] < existRightInterval[i]) {
                    // next deleted interval starts before the end of current existing interval
                    if ((j<m-1) && (newLeftInterval[j+1] < existRightInterval[i])) {
                        finalLeftInterval[t] = newRightInterval[j];
                        finalRightInterval[t] = newLeftInterval[j+1];
                        t++; j++;
                    }
                    // next deleted interval starts after the end of current existing interval
                    else {
                        finalLeftInterval[t] = newRightInterval[j];
                        finalRightInterval[t] = existRightInterval[i];
                        t++; i++; j++;
                    }
                }
                // end of the new interval is after the end of the existing interval
                else {
                    // next existing interval starts before the end of current deleting interval
                    if ((i<n-1) && (existLeftInterval[i+1] < newRightInterval[j])) {
                        i++;
                    }
                    // next existing interval starts after the end of current deleting interval
                    else {
                        j++; i++;
                    }
                }
            }
        }
    }
    // inserting all remaining existing intervals
    while (i < n) {
        finalLeftInterval[t] = existLeftInterval[i];
        finalRightInterval[t] = existRightInterval[i];
        i++; t++;
    }

    // printing updated interval information after insertion
    printf("\n++ Final Intervals:");
    for (i=0; i<t; i++) {
        printf(" [ %d, %d ];", finalLeftInterval[i], finalRightInterval[i]);
    }
    if(t==0) printf(" NIL");
    printf("\n");

    return 0;
}