#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

// Function to perform Counting Sort based on digit place (1s, 10s, 100s, etc.)
void countSort(int arr[], int n, int exponent) {
    std::vector<int> count(n,0);
    for(int i=0;i<n;i++){
        count[(arr[i]/exponent)%10]++;
    }
    
    for(int i=1;i<n;i++){
        count[i] = count[i] + count[i-1];
    }
     std::vector<int> ans(n,0);

    for(int i=n-1;i>=0;i--){
        int index = --count[(arr[i]/exponent)%10];
        ans[index] = arr[i]; 
    }
    for(int i=0;i<n;i++){
        arr[i] = ans[i];
    }
}

// Function to perform Radix Sort on the array.
void radixSort(int arr[], int n) {
    int maxNumber  = arr[0];
    for(int i=1;i<n;i++){
        if(maxNumber<arr[i]){
            maxNumber= arr[i];
        }
    }
    maxNumber = int(log10(maxNumber) + 1);
    int exponent = 1;
    for(int i=0;i<maxNumber;i++){
        countSort(arr,n,exponent);
        exponent = exponent*10;
    }
}

// Function to initiate the Radix Sort process.
void processRadixSort(int arr[], int n) {
    if(n>1){
        radixSort(arr,n);
    }
}

void displayArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

// Function to dynamically allocate an array and fill it with random values.
void fillDynamicArrayWithRandomValues(int** arr, int* n) {
    cout << "Enter the size of the array: ";
    cin >> *n;
    *arr = new int[*n];
    srand(time(0)); // Seed for random number generation
    for (int i = 0; i < *n; i++) {
        (*arr)[i] = rand() % 1000; // Fill with random numbers between 0 and 999
    }
}

int main() {
    int* arr;
    int n;
    fillDynamicArrayWithRandomValues(&arr, &n);
    cout << "Unsorted array: ";
    displayArray(arr, n);
    processRadixSort(arr, n);
    cout << "Sorted array: ";
    displayArray(arr, n);
    delete[] arr; // Deallocate dynamically allocated memory
    return 0;
}

#include <iostream>
using namespace std;

// Function to partition the array and return the pivot index.
int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int swapIndex = low-1;
    for(int currentIndex = low ; currentIndex<high; currentIndex++){
        if(arr[currentIndex] <= pivot){
            swapIndex++;
            std::swap(arr[swapIndex] ,arr[currentIndex]);
        }
    }
    std::swap(arr[swapIndex+1] ,arr[high]);
    return swapIndex+1;
}

void displayArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}
// Function to recursively sort the array using Quick Sort.
void quickSort(int arr[], int low, int high) {
    if(low<high){
        int pivotIndex = partition(arr,low,high);
        quickSort(arr,low,pivotIndex-1);
        quickSort(arr,pivotIndex+1,high);
    }
}

// Function to initiate the Quick Sort process.
void processQuickSort(int arr[], int n) {
    if(n>1){
        quickSort(arr,0,n-1);
    }
}


// Function to dynamically allocate an array and fill it with random values.
void fillDynamicArrayWithRandomValues(int** arr, int* n) {
    cout << "Enter the size of the array: ";
    cin >> *n;
    *arr = new int[*n];
    srand(time(0)); // Seed for random number generation
    for (int i = 0; i < *n; i++) {
        (*arr)[i] = rand() % 1000; // Fill with random numbers between 0 and 999
    }
}

int main() {
    int* arr;
    int n;
    fillDynamicArrayWithRandomValues(&arr, &n);
    cout << "Unsorted array: ";
    displayArray(arr, n);
    processQuickSort(arr, n);
    cout << "Sorted array: ";
    displayArray(arr, n);
    delete[] arr; // Deallocate dynamically allocated memory
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

// Function to merge two sorted halves of the array into a single sorted array.
void merge(int arr[], int left, int mid, int right) {
    int n= left+ (right-left)/2;
    vector<int> tempArray;
    int start = left;
    int start2= mid+1;
    if(arr[mid]<=arr[start2]){
        return;
    }
    while(start<=mid && start2<=right){
        if(arr[start]<=arr[start2]){
            tempArray.push_back(arr[start]);
            start++;
        }else{
            tempArray.push_back(arr[start2]);
            start2++;
        }
    }

    while (start <= mid) {
        tempArray.push_back(arr[start]);
        start++;
    }

    while (start2 <= right) {
        tempArray.push_back(arr[start2]);
        start2++;
    }
    for(int i=left;i<=right;i++){
        arr[i] = tempArray[i-left];
    }
}

// Function to recursively divide the array and merge the sorted halves.
void mergeSort(int arr[], int left, int right) {
    if (left >= right)
        return;

    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

// Function to initiate the merge sort process.
void processMergeSort(int arr[], int n) {
    if(n>1){
        mergeSort(arr,0,n-1);
    }
}

void displayArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

// Function to dynamically allocate an array and fill it with random values.
void fillDynamicArrayWithRandomValues(int** arr, int* n) {
    cout << "Enter the size of the array: ";
    cin >> *n;
    *arr = new int[*n];
    srand(time(0)); // Seed for random number generation
    for (int i = 0; i < *n; i++) {
        (*arr)[i] = rand() % 1000; // Fill with random numbers between 0 and 999
    }
}

int main() {
    int* arr;
    int n;
    fillDynamicArrayWithRandomValues(&arr, &n);
    cout << "Unsorted array: ";
    displayArray(arr, n);
    processMergeSort(arr, n);
    cout << "Sorted array: ";
    displayArray(arr, n);
    delete[] arr; // Deallocate dynamically allocated memory
    return 0;
}

#include <iostream>
#include <cstdlib> // for rand() and srand()
#include <ctime> // for time()

using namespace std;

// Function to merge two sorted sub-arrays in place.
void inPlaceMerge(int arr[], int left, int mid, int right) {
    int start2= mid+1;
    if(arr[mid]<=arr[start2]){
        return;
    }

    while(left<=mid && start2<=right){
        if(arr[left]<=arr[start2]){
            left++;
        }else{
            int swpaData = arr[start2];
            int index = start2;
             while (index != left) {
                arr[index] = arr[index - 1];
                index--;
            }
            arr[left] = swpaData;
            left++;
            mid++;
            start2++;
        }
    }
}

// Function to recursively sort the array using Merge Sort.
void inPlaceMergeSort(int arr[], int left, int right) {
   if(left<right){
        int middle = left + (right - left )/ 2;
 
        // Sort first and second halves
        inPlaceMergeSort(arr, left, middle);
        inPlaceMergeSort(arr, middle + 1, right);
 
        inPlaceMerge(arr, left, middle, right);
   }
}

// Function to initiate the Merge Sort process.
void processInPlaceMergeSort(int arr[], int n) {
    if (n > 1) {
        inPlaceMergeSort(arr, 0, n - 1);
    }
}

void displayArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

// Function to dynamically allocate an array and fill it with random values.
void fillDynamicArrayWithRandomValues(int** arr, int* n) {
    cout << "Enter the size of the array: ";
    cin >> *n;
    *arr = new int[*n];
    srand(time(0)); // Seed for random number generation
    for (int i = 0; i < *n; i++) {
        (*arr)[i] = rand() % 1000; // Fill with random numbers between 0 and 999
    }
}

int main() {
    int* arr;
    int n;
    fillDynamicArrayWithRandomValues(&arr, &n);
    cout << "Unsorted array: ";
    displayArray(arr, n);
    processInPlaceMergeSort(arr, n);
    cout << "Sorted array: ";
    displayArray(arr, n);
    delete[] arr; // Deallocate dynamically allocated memory
    return 0;
}

#include <iostream>
using namespace std;

// Function to sort the array using insertion sort algorithm.
void processSelectionSort(int arr[], int n) {
  
  for (int i = 0 ;i<n;i++){
    int minIndex=i;
     for (int j = i ;j<n;j++){
        if(arr[j]<arr[minIndex]){
           minIndex = j;
        }
    }
    std::swap(arr[i],arr[minIndex]);
  }
}

void displayArray(int arr[], int n) {
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << endl;
}

// Function to dynamically allocate an array and fill it with random values.
void fillDynamicArrayWithRandomValues(int** arr, int* n) {
    cout << "Enter the size of the array: ";
    cin >> *n;
    *arr = new int[*n];
    srand(time(0)); // Seed for random number generation
    for (int i = 0; i < *n; i++) {
        (*arr)[i] = rand() % 1000; // Fill with random numbers between 0 and 999
    }
}

int main() {
    int* arr;
    int n;
    fillDynamicArrayWithRandomValues(&arr, &n);
    cout << "Unsorted array: ";
    displayArray(arr, n);
    processSelectionSort(arr, n);
    cout << "Sorted array: ";
    displayArray(arr, n);
    delete[] arr; // Deallocate dynamically allocated memory
    return 0;
}

#include <iostream>
using namespace std;

// Function to sort the array using insertion sort algorithm.
void processInsertionSort(int arr[], int n) {
  
   for(int j=1;j<n;j++){
    int key= arr[j];
    int i=j-1;
        while(i>=0 && arr[i]>key){
            arr[i+1] = arr[i];
            i--;
        }
        arr[i+1] = key;
    }
  
}

void displayArray(int arr[], int n) {
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << endl;
}

// Function to dynamically allocate an array and fill it with random values.
void fillDynamicArrayWithRandomValues(int** arr, int* n) {
    cout << "Enter the size of the array: ";
    cin >> *n;
    *arr = new int[*n];
    srand(time(0)); // Seed for random number generation
    for (int i = 0; i < *n; i++) {
        (*arr)[i] = rand() % 1000; // Fill with random numbers between 0 and 999
    }
}

int main() {
    int* arr;
    int n;
    fillDynamicArrayWithRandomValues(&arr, &n);
    cout << "Unsorted array: ";
    displayArray(arr, n);
    processInsertionSort(arr, n);
    cout << "Sorted array: ";
    displayArray(arr, n);
    delete[] arr; // Deallocate dynamically allocated memory
    return 0;
}

#include <iostream>
using namespace std;

// Function to sort the array using bubble sort algorithm.
void processBubbleSort(int arr[], int n) {
  // Your code here
  int length =n;
  bool swapped = true;
  while(swapped){
    swapped = false;
    for (int i=0 ; i<length-1 ; i++){
        if(arr[i] > arr[i+1]){
            swapped = true;
            int largeElement = arr[i];
            arr[i] = arr[i+1];
            arr[i+1] = largeElement;
        }
    }
    length = length-1;
  }
}

void displayArray(int arr[], int n) {
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << endl;
}

// Function to dynamically allocate an array and fill it with random values.
void fillDynamicArrayWithRandomValues(int** arr, int* n) {
    cout << "Enter the size of the array: ";
    cin >> *n;
    *arr = new int[*n];
    srand(time(0)); // Seed for random number generation
    for (int i = 0; i < *n; i++) {
        (*arr)[i] = rand() % 1000; // Fill with random numbers between 0 and 999
    }
}

int main() {
    int* arr;
    int n;
    fillDynamicArrayWithRandomValues(&arr, &n);
    cout << "Unsorted array: ";
    displayArray(arr, n);
    processBubbleSort(arr, n);
    cout << "Sorted array: ";
    displayArray(arr, n);
    delete[] arr; // Deallocate dynamically allocated memory
    return 0;
}

struct Node {
    int key, value, cnt;
    Node *next; 
    Node *prev;
    Node(int _key, int _value) {
        key = _key;
        value = _value; 
        cnt = 1; 
    }
}; 
struct List {
    int size; 
    Node *head; 
    Node *tail; 
    List() {
        head = new Node(0, 0); 
        tail = new Node(0,0); 
        head->next = tail;
        tail->prev = head; 
        size = 0;
    }
    
    void addFront(Node *node) {
        Node* temp = head->next;
        node->next = temp;
        node->prev = head;
        head->next = node;
        temp->prev = node;
        size++; 
    }
    
    void removeNode(Node* delnode) {
        Node* delprev = delnode->prev;
        Node* delnext = delnode->next;
        delprev->next = delnext;
        delnext->prev = delprev;
        size--; 
    }
    
    
    
};
class LFUCache {
    map<int, Node*> keyNode; 
    map<int, List*> freqListMap; 
    int maxSizeCache;
    int minFreq; 
    int curSize; 
public:
    LFUCache(int capacity) {
        maxSizeCache = capacity; 
        minFreq = 0;
        curSize = 0; 
    }
    void updateFreqListMap(Node *node) {
        keyNode.erase(node->key); 
        freqListMap[node->cnt]->removeNode(node); 
        if(node->cnt == minFreq && freqListMap[node->cnt]->size == 0) {
            minFreq++; 
        }
        
        List* nextHigherFreqList = new List();
        if(freqListMap.find(node->cnt + 1) != freqListMap.end()) {
            nextHigherFreqList = freqListMap[node->cnt + 1];
        } 
        node->cnt += 1; 
        nextHigherFreqList->addFront(node); 
        freqListMap[node->cnt] = nextHigherFreqList; 
        keyNode[node->key] = node;
    }
    
    int get(int key) {
        if(keyNode.find(key) != keyNode.end()) {
            Node* node = keyNode[key]; 
            int val = node->value; 
            updateFreqListMap(node); 
            return val; 
        }
        return -1; 
    }
    
    void put(int key, int value) {
        if (maxSizeCache == 0) {
            return;
        }
        if(keyNode.find(key) != keyNode.end()) {
            Node* node = keyNode[key]; 
            node->value = value; 
            updateFreqListMap(node); 
        }
        else {
            if(curSize == maxSizeCache) {
                List* list = freqListMap[minFreq]; 
                keyNode.erase(list->tail->prev->key); 
                freqListMap[minFreq]->removeNode(list->tail->prev);
                curSize--; 
            }
            curSize++; 
            // new value has to be added who is not there previously 
            minFreq = 1; 
            List* listFreq = new List(); 
            if(freqListMap.find(minFreq) != freqListMap.end()) {
                listFreq = freqListMap[minFreq]; 
            }
            Node* node = new Node(key, value); 
            listFreq->addFront(node);
            keyNode[key] = node; 
            freqListMap[minFreq] = listFreq; 
        }
    }
};

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache* obj = new LFUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

#include <bits/stdc++.h>
using namespace std;

// Movie class
class Movie
{
public:
    int id;
    string title;

    Movie(int id, string title) : id(id), title(title) {}
};

// Theater class
class Theater
{
public:
    int id;
    string name;
    vector<Movie *> movies;
    map<int, int> availableSeats;

    Theater(int id, string name) : id(id), name(name) {}

    // Add a movie to the theater
    void addMovie(Movie *movie, int seatCount)
    {
        movies.push_back(movie);
        availableSeats[movie->id] = seatCount;
    }

    // Display the list of movies playing in this theater
    void displayMovies()
    {
        cout << "Movies playing in theater: " << name << endl;
        for (auto &movie : movies)
        {
            cout << "Movie ID: " << movie->id << ", Title: " << movie->title << endl;
        }
    }

    // Check if seats are available
    bool hasAvailableSeats(Movie *movie)
    {
        return availableSeats[movie->id] > 0;
    }

    // Book a seat
    void bookSeat(Movie *movie)
    {
        if (hasAvailableSeats(movie))
        {
            availableSeats[movie->id]--;
            cout << "Booking successful! Seats remaining: " << availableSeats[movie->id] << endl;
        }
        else
        {
            cout << "No seats available!" << endl;
        }
    }
};

// BookingSystem class
class BookingSystem
{
public:
    vector<Theater *> theaters;

    // Add a theater to the system
    void addTheater(Theater *theater)
    {
        theaters.push_back(theater);
    }

    // Display all theaters
    void displayTheaters()
    {
        cout << "Available theaters:\n";
        for (auto &theater : theaters)
        {
            cout << "Theater ID: " << theater->id << ", Name: " << theater->name << endl;
        }
    }

    // View movies in a selected theater
    void viewMoviesInTheater(int theaterId)
    {
        for (auto &theater : theaters)
        {
            if (theater->id == theaterId)
            {
                theater->displayMovies();
                return;
            }
        }
        cout << "Theater not found!" << endl;
    }

    // Book tickets for a movie
    void bookTicket(int theaterId, int movieId)
    {
        for (auto &theater : theaters)
        {
            if (theater->id == theaterId)
            {
                for (auto &movie : theater->movies)
                {
                    if (movie->id == movieId)
                    {
                        if (theater->hasAvailableSeats(movie))
                        {
                            theater->bookSeat(movie);
                            return;
                        }
                        else
                        {
                            cout << "No seats available for this movie!" << endl;
                            return;
                        }
                    }
                }
                cout << "Movie not found in this theater!" << endl;
                return;
            }
        }
        cout << "Theater not found!" << endl;
    }
};

// Main function for demonstration
int main()
{
    BookingSystem system;

    // Create movies
    Movie *movie1 = new Movie(1, "Avengers");
    Movie *movie2 = new Movie(2, "Inception");

    // Create theaters and add movies
    Theater *theater1 = new Theater(1, "PVR Cinemas");
    Theater *theater2 = new Theater(2, "INOX");
    theater1->addMovie(movie1, 10);
    theater1->addMovie(movie2, 10);
    theater2->addMovie(movie2, 10);

    // Add theaters to booking system
    system.addTheater(theater1);
    system.addTheater(theater2);

    // Display theaters
    system.displayTheaters();

    // View movies in theater 1
    system.viewMoviesInTheater(1);

    // Book a ticket for Avengers in PVR Cinemas
    system.bookTicket(1, 1);

    // Attempt to book again
    system.bookTicket(1, 1);

    return 0;
}

#include <bits/stdc++.h>
#include <chrono>
#include <thread>
using namespace std;

class Payment
{
public:
    virtual double calculateCost(double hours) = 0;
};

class CarPayment : public Payment
{
public:
    double calculateCost(double hours) { return hours * 2; }
};

class BikePayment : public Payment
{
public:
    double calculateCost(double hours) { return hours * 1; }
};

class Vehicle
{
protected:
    Payment *payment;
    chrono::time_point<chrono::system_clock> parkedTime;

public:
    virtual string getType() = 0;
    virtual double calculateCost(double hours)
    {
        return payment->calculateCost(hours);
    }

    void setParkedTime()
    {
        parkedTime = chrono::system_clock::now();
    }

    chrono::time_point<chrono::system_clock> getParkedTime()
    {
        return parkedTime;
    }
};

class Car : public Vehicle
{
public:
    Car() { payment = new CarPayment(); }
    string getType() { return "Car"; }
};

class Bike : public Vehicle
{
public:
    Bike() { payment = new BikePayment(); }
    string getType() { return "Bike"; }
};

class ParkingLot
{
private:
    vector<vector<vector<Vehicle *>>> spots;
    int floors;
    int rows;
    int spotsPerRow;

public:
    ParkingLot(int floors, int rows, int spotsPerRow)
    {
        this->floors = floors;
        this->rows = rows;
        this->spotsPerRow = spotsPerRow;
        spots.resize(floors);
        for (int i = 0; i < floors; i++)
        {
            spots[i].resize(rows);
            for (int j = 0; j < rows; j++)
            {
                spots[i][j].resize(spotsPerRow);
            }
        }
    }

    bool park(Vehicle *v, int floor, int row, int spot)
    {
        if (spots[floor][row][spot] == nullptr)
        {
            spots[floor][row][spot] = v;
            cout << v->getType() << " parked successfully at floor " << floor << ", row " << row << ", spot " << spot << "." << endl;
            return true;
        }
        else
        {
            cout << "Spot already occupied." << endl;
            return false;
        }
    }

    bool leave(Vehicle *v)
    {
        for (int i = 0; i < floors; i++)
        {
            for (int j = 0; j < rows; j++)
            {
                for (int k = 0; k < spotsPerRow; k++)
                {
                    if (spots[i][j][k] == v)
                    {
                        double hours = calculateHoursParked(spots[i][j][k]);
                        double cost = spots[i][j][k]->calculateCost(hours);
                        spots[i][j][k] = nullptr;
                        cout << v->getType() << " left successfully. Total cost: " << cost << " " << hours * 1e8 << endl;
                        return true;
                    }
                }
            }
        }
        cout << v->getType() << " not found." << endl;
        return false;
    }

    int availableSpots(int floor)
    {
        int count = 0;
        for (int i = 0; i < rows; i++)
        {
            for (int j = 0; j < spotsPerRow; j++)
            {
                if (spots[floor][i][j] == nullptr)
                {
                    count++;
                }
            }
        }
        return count;
    }

    double calculateHoursParked(Vehicle *v)
    {
        for (int i = 0; i < floors; i++)
        {
            for (int j = 0; j < rows; j++)
            {
                for (int k = 0; k < spotsPerRow; k++)
                {
                    if (spots[i][j][k] == v)
                    {
                        // get the current time
                        auto now = chrono::system_clock::now();
                        // get the time the vehicle was parked
                        auto parkedTime = spots[i][j][k]->getParkedTime();
                        // calculate the difference in hours
                        chrono::duration<double> duration = now - parkedTime; // Difference in seconds
                        double hours = duration.count() / 3600;               // Convert seconds to hours
                        return hours;
                    }
                }
            }
        }
        return 0;
    }
};

int main()
{
    ParkingLot lot(3, 10, 20);
    Car car1, car2;
    Bike bike1, bike2;

    car1.setParkedTime();
    lot.park(&car1, 0, 0, 0);
    car2.setParkedTime();
    lot.park(&car2, 0, 0, 1);
    bike1.setParkedTime();
    lot.park(&bike1, 0, 0, 2);

    cout << "Available spots on floor 0: " << lot.availableSpots(0) << endl;
    _sleep(500);
    lot.leave(&car1);
    lot.leave(&bike2);

    cout << "Available spots on floor 0: " << lot.availableSpots(0) << endl;

    return 0;
}

struct Queue {
    stack<int> s1, s2;
 
    // Enqueue an item to the queue
    void enQueue(int x)
    {
        // Push item into the first stack
        s1.push(x);
    }
 
    // Dequeue an item from the queue
    int deQueue()
    {
        // if both stacks are empty
        if (s1.empty() && s2.empty()) {
            return -1;
        }
 
        // if s2 is empty, move
        // elements from s1
        if (s2.empty()) {
            while (!s1.empty()) {
                s2.push(s1.top());
                s1.pop();
            }
        }
 
        // return the top item from s2
        int x = s2.top();
        s2.pop();
        return x;
    }
};

struct Queue {
    stack<int> s;
 
    // Enqueue an item to the queue
    void enQueue(int x)
    {
        s.push(x);
    }
 
    // Dequeue an item from the queue
    int deQueue()
    {
        if (s.empty()) {
            return -1;
        }
 
        // pop an item from the stack
        int x = s.top();
        s.pop();
 
        // if stack becomes empty, return
        // the popped item
        if (s.empty())
            return x;
 
        // recursive call
        int item = deQueue();
 
        // push popped item back to the stack
        s.push(x);
 
        // return the result of deQueue() call
        return item;
    }
};

class TwoStacks
{
    vector<int> elements;
    int ptr1, ptr2, capacity;

    TwoStacks(int capacity)
    {
        for(int i=0; i < capacity; i++)
        {
            elements.push_back(-1);
        }
        ptr1 = 0;
        ptr2 = capacity-1;
        this->capacity = capacity;
    }

    bool push1(int value)
    {
        if(ptr1 <= ptr2)
        {
            elements[ptr1] = value;
            ptr1++;
        }
        else 
        {
            return false;
        }
    }

    bool push2(int value)
    {
        if(ptr1 <= ptr2)
        {
            elements[ptr2] = value;
            ptr2--;
        }
        else 
        {
            return false;
        }
    }

    int pop1()
    {
        if(ptr1-1 < 0)
        {
            return -1;
        }
        ptr1--;
        return elements[ptr1];
    }

    int pop2()
    {
        if(ptr2+1 >= capacity)
        {
            return -1;
        }
        ptr2++;
        return elements[ptr2];
    }    

};

class DLL
{
public:
    DLL *next;
    DLL *prev;
    int _value;
    int _key;

    DLL(int _key, int _value)
    {
        this->_key = _key;
        this->_value = _value;
        next = NULL;
        prev = NULL;
    }
};

class LRU
{
public:
    DLL *head;
    DLL *tail;
    int capacity;
    map<int, DLL *> location;

    LRU(int capacity)
    {
        this->capacity = capacity;
        head = new DLL(-1, -1);
        tail = new DLL(-1, -1);
        head->next = tail;
        tail->prev = head;
    }

    void deleteNode(int key)
    {
        DLL *cur = location[key];
        DLL *prev_node = cur->prev;
        DLL *next_node = cur->next;

        prev_node->next = next_node;
        next_node->prev = prev_node;
        location.erase(key);
    }

    void addNode(int key, int value)
    {
        DLL *new_node = new DLL(key, value);
        DLL *next_node = head->next;

        head->next = new_node;
        new_node->prev = head;
        new_node->next = next_node;
        next_node->prev = new_node;
        location[key] = new_node;
    }

    void putInCache(int key, int value)
    {
        // value is not already in cache
        if (location.find(key) == location.end())
        {
            addNode(key, value);
            if (location.size() > capacity)
            {
                deleteNode(tail->prev->_key);
            }
        }
        else
        {
            deleteNode(key);
            addNode(key, value);
        }
    }

    int getData(int key)
    {
        if (location.find(key) != location.end())
        {
            int val = location[key]->_value;
            deleteNode(key);
            addNode(key, val);
            return val;
        }
        return -1;
    }
};

#include <bits/stdc++.h>

using namespace std;

class Piece
{
private:
    virtual bool AreSquaresLegal(int srcRow, int srcCol, int destRow, int destCol, Piece *GameBoard[8][8]) = 0;
    char mPieceColor;

public:
    Piece(char PieceColor) : mPieceColor(PieceColor) {}
    ~Piece() {}
    virtual char GetPiece() = 0;
    char GetColor()
    {
        return mPieceColor;
    }
    bool IsLegalMove(int srcRow, int srcCol, int destRow, int destCol, Piece *GameBoard[8][8])
    {
        Piece *destPiece = GameBoard[destRow][destCol];
        if ((destPiece == 0) || (mPieceColor != destPiece->GetColor()))
        {
            return AreSquaresLegal(srcRow, srcCol, destRow, destCol, GameBoard);
        }
        return false;
    }
};



class PawnPiece : public Piece
{
public:
    PawnPiece(char PieceColor) : Piece(PieceColor) {}
    ~PawnPiece() {}

private:
    virtual char GetPiece()
    {
        return 'P';
    }
    bool AreSquaresLegal(int srcRow, int srcCol, int destRow, int destCol, Piece *GameBoard[8][8])
    {
        Piece *destPiece = GameBoard[destRow][destCol];
        if (destPiece == 0)
        {
            // Destination square is unoccupied
            if (srcCol == destCol)
            {
                if (GetColor() == 'W')
                {
                    if (destRow == srcRow + 1)
                    {
                        return true;
                    }
                }
                else
                {
                    if (destRow == srcRow - 1)
                    {
                        return true;
                    }
                }
            }
        }
        else
        {
            // Dest holds piece of opposite color
            if ((srcCol == destCol + 1) || (srcCol == destCol - 1))
            {
                if (GetColor() == 'W')
                {
                    if (destRow == srcRow + 1)
                    {
                        return true;
                    }
                }
                else
                {
                    if (destRow == srcRow - 1)
                    {
                        return true;
                    }
                }
            }
        }
        return false;
    }
};



class KnightPiece : public Piece
{
public:
    KnightPiece(char PieceColor) : Piece(PieceColor) {}
    ~KnightPiece() {}

private:
    virtual char GetPiece()
    {
        return 'N';
    }
    bool AreSquaresLegal(int srcRow, int srcCol, int destRow, int destCol, Piece *GameBoard[8][8])
    {
        // Destination square is unoccupied or occupied by opposite color
        if ((srcCol == destCol + 1) || (srcCol == destCol - 1))
        {
            if ((srcRow == destRow + 2) || (srcRow == destRow - 2))
            {
                return true;
            }
        }
        if ((srcCol == destCol + 2) || (srcCol == destCol - 2))
        {
            if ((srcRow == destRow + 1) || (srcRow == destRow - 1))
            {
                return true;
            }
        }
        return false;
    }
};



class BishopPiece : public Piece
{
public:
    BishopPiece(char PieceColor) : Piece(PieceColor) {}
    ~BishopPiece() {}

private:
    virtual char GetPiece()
    {
        return 'B';
    }
    bool AreSquaresLegal(int srcRow, int srcCol, int destRow, int destCol, Piece *GameBoard[8][8])
    {
        if ((destCol - srcCol == destRow - srcRow) || (destCol - srcCol == srcRow - destRow))
        {
            // Make sure that all invervening squares are empty
            int iRowOffset = (destRow - srcRow > 0) ? 1 : -1;
            int iColOffset = (destCol - srcCol > 0) ? 1 : -1;
            int iCheckRow;
            int iCheckCol;
            for (iCheckRow = srcRow + iRowOffset, iCheckCol = srcCol + iColOffset;
                 iCheckRow != destRow;
                 iCheckRow = iCheckRow + iRowOffset, iCheckCol = iCheckCol + iColOffset)
            {
                if (GameBoard[iCheckRow][iCheckCol] != 0)
                {
                    return false;
                }
            }
            return true;
        }
        return false;
    }
};



class RookPiece : public Piece
{
public:
    RookPiece(char PieceColor) : Piece(PieceColor) {}
    ~RookPiece() {}

private:
    virtual char GetPiece()
    {
        return 'R';
    }
    bool AreSquaresLegal(int srcRow, int srcCol, int destRow, int destCol, Piece *GameBoard[8][8])
    {
        if (srcRow == destRow)
        {
            // Make sure that all invervening squares are empty
            int iColOffset = (destCol - srcCol > 0) ? 1 : -1;
            for (int iCheckCol = srcCol + iColOffset; iCheckCol != destCol; iCheckCol = iCheckCol + iColOffset)
            {
                if (GameBoard[srcRow][iCheckCol] != 0)
                {
                    return false;
                }
            }
            return true;
        }
        else if (destCol == srcCol)
        {
            // Make sure that all invervening squares are empty
            int iRowOffset = (destRow - srcRow > 0) ? 1 : -1;
            for (int iCheckRow = srcRow + iRowOffset; iCheckRow != destRow; iCheckRow = iCheckRow + iRowOffset)
            {
                if (GameBoard[iCheckRow][srcCol] != 0)
                {
                    return false;
                }
            }
            return true;
        }
        return false;
    }
};



class QueenPiece : public Piece
{
public:
    QueenPiece(char PieceColor) : Piece(PieceColor) {}
    ~QueenPiece() {}

private:
    virtual char GetPiece()
    {
        return 'Q';
    }
    bool AreSquaresLegal(int srcRow, int srcCol, int destRow, int destCol, Piece *GameBoard[8][8])
    {
        if (srcRow == destRow)
        {
            // Make sure that all invervening squares are empty
            int iColOffset = (destCol - srcCol > 0) ? 1 : -1;
            for (int iCheckCol = srcCol + iColOffset; iCheckCol != destCol; iCheckCol = iCheckCol + iColOffset)
            {
                if (GameBoard[srcRow][iCheckCol] != 0)
                {
                    return false;
                }
            }
            return true;
        }
        else if (destCol == srcCol)
        {
            // Make sure that all invervening squares are empty
            int iRowOffset = (destRow - srcRow > 0) ? 1 : -1;
            for (int iCheckRow = srcRow + iRowOffset; iCheckRow != destRow; iCheckRow = iCheckRow + iRowOffset)
            {
                if (GameBoard[iCheckRow][srcCol] != 0)
                {
                    return false;
                }
            }
            return true;
        }
        else if ((destCol - srcCol == destRow - srcRow) || (destCol - srcCol == srcRow - destRow))
        {
            // Make sure that all invervening squares are empty
            int iRowOffset = (destRow - srcRow > 0) ? 1 : -1;
            int iColOffset = (destCol - srcCol > 0) ? 1 : -1;
            int iCheckRow;
            int iCheckCol;
            for (iCheckRow = srcRow + iRowOffset, iCheckCol = srcCol + iColOffset;
                 iCheckRow != destRow;
                 iCheckRow = iCheckRow + iRowOffset, iCheckCol = iCheckCol + iColOffset)
            {
                if (GameBoard[iCheckRow][iCheckCol] != 0)
                {
                    return false;
                }
            }
            return true;
        }
        return false;
    }
};



class KingPiece : public Piece
{
public:
    KingPiece(char PieceColor) : Piece(PieceColor) {}
    ~KingPiece() {}

private:
    virtual char GetPiece()
    {
        return 'K';
    }
    bool AreSquaresLegal(int srcRow, int srcCol, int destRow, int destCol, Piece *GameBoard[8][8])
    {
        int iRowDelta = destRow - srcRow;
        int iColDelta = destCol - srcCol;
        if (((iRowDelta >= -1) && (iRowDelta <= 1)) &&
            ((iColDelta >= -1) && (iColDelta <= 1)))
        {
            return true;
        }
        return false;
    }
};



class ChessBoard
{
public:
    Piece *MainGameBoard[8][8];
    ChessBoard()
    {
        for (int iRow = 0; iRow < 8; ++iRow)
        {
            for (int iCol = 0; iCol < 8; ++iCol)
            {
                MainGameBoard[iRow][iCol] = 0;
            }
        }
        // Allocate and place black pieces
        for (int iCol = 0; iCol < 8; ++iCol)
        {
            MainGameBoard[6][iCol] = new PawnPiece('B');
        }
        MainGameBoard[7][0] = new RookPiece('B');
        MainGameBoard[7][1] = new KnightPiece('B');
        MainGameBoard[7][2] = new BishopPiece('B');
        MainGameBoard[7][3] = new KingPiece('B');
        MainGameBoard[7][4] = new QueenPiece('B');
        MainGameBoard[7][5] = new BishopPiece('B');
        MainGameBoard[7][6] = new KnightPiece('B');
        MainGameBoard[7][7] = new RookPiece('B');
        // Allocate and place white pieces
        for (int iCol = 0; iCol < 8; ++iCol)
        {
            MainGameBoard[1][iCol] = new PawnPiece('W');
        }
        MainGameBoard[0][0] = new RookPiece('W');
        MainGameBoard[0][1] = new KnightPiece('W');
        MainGameBoard[0][2] = new BishopPiece('W');
        MainGameBoard[0][3] = new KingPiece('W');
        MainGameBoard[0][4] = new QueenPiece('W');
        MainGameBoard[0][5] = new BishopPiece('W');
        MainGameBoard[0][6] = new KnightPiece('W');
        MainGameBoard[0][7] = new RookPiece('W');
    }
    ~ChessBoard()
    {
        for (int iRow = 0; iRow < 8; ++iRow)
        {
            for (int iCol = 0; iCol < 8; ++iCol)
            {
                delete MainGameBoard[iRow][iCol];
                MainGameBoard[iRow][iCol] = 0;
            }
        }
    }

    void Print()
    {
        const int kiSquareWidth = 4;
        const int kiSquareHeight = 3;
        for (int iRow = 0; iRow < 8 * kiSquareHeight; ++iRow)
        {
            int iSquareRow = iRow / kiSquareHeight;
            // Print side border with numbering
            if (iRow % 3 == 1)
            {
                cout << '-' << (char)('1' + 7 - iSquareRow) << '-';
            }
            else
            {
                cout << "---";
            }
            // Print the chess board
            for (int iCol = 0; iCol < 8 * kiSquareWidth; ++iCol)
            {
                int iSquareCol = iCol / kiSquareWidth;
                if (((iRow % 3) == 1) && ((iCol % 4) == 1 || (iCol % 4) == 2) && MainGameBoard[7 - iSquareRow][iSquareCol] != 0)
                {
                    if ((iCol % 4) == 1)
                    {
                        cout << MainGameBoard[7 - iSquareRow][iSquareCol]->GetColor();
                    }
                    else
                    {
                        cout << MainGameBoard[7 - iSquareRow][iSquareCol]->GetPiece();
                    }
                }
                else
                {
                    if ((iSquareRow + iSquareCol) % 2 == 1)
                    {
                        cout << '*';
                    }
                    else
                    {
                        cout << ' ';
                    }
                }
            }
            cout << endl;
        }
        // Print the bottom border with numbers
        for (int iRow = 0; iRow < kiSquareHeight; ++iRow)
        {
            if (iRow % 3 == 1)
            {
                cout << "---";
                for (int iCol = 0; iCol < 8 * kiSquareWidth; ++iCol)
                {
                    int iSquareCol = iCol / kiSquareWidth;
                    if ((iCol % 4) == 1)
                    {
                        cout << (iSquareCol + 1);
                    }
                    else
                    {
                        cout << '-';
                    }
                }
                cout << endl;
            }
            else
            {
                for (int iCol = 1; iCol < 9 * kiSquareWidth; ++iCol)
                {
                    cout << '-';
                }
                cout << endl;
            }
        }
    }

    bool IsInCheck(char PieceColor)
    {
        // Find the king
        int iKingRow;
        int iKingCol;
        for (int iRow = 0; iRow < 8; ++iRow)
        {
            for (int iCol = 0; iCol < 8; ++iCol)
            {
                if (MainGameBoard[iRow][iCol] != 0)
                {
                    if (MainGameBoard[iRow][iCol]->GetColor() == PieceColor)
                    {
                        if (MainGameBoard[iRow][iCol]->GetPiece() == 'K')
                        {
                            iKingRow = iRow;
                            iKingCol = iCol;
                        }
                    }
                }
            }
        }
        // Run through the opponent's pieces and see if any can take the king
        for (int iRow = 0; iRow < 8; ++iRow)
        {
            for (int iCol = 0; iCol < 8; ++iCol)
            {
                if (MainGameBoard[iRow][iCol] != 0)
                {
                    if (MainGameBoard[iRow][iCol]->GetColor() != PieceColor)
                    {
                        if (MainGameBoard[iRow][iCol]->IsLegalMove(iRow, iCol, iKingRow, iKingCol, MainGameBoard))
                        {
                            return true;
                        }
                    }
                }
            }
        }

        return false;
    }

    bool CanMove(char PieceColor)
    {
        // Run through all pieces
        for (int iRow = 0; iRow < 8; ++iRow)
        {
            for (int iCol = 0; iCol < 8; ++iCol)
            {
                if (MainGameBoard[iRow][iCol] != 0)
                {
                    // If it is a piece of the current player, see if it has a legal move
                    if (MainGameBoard[iRow][iCol]->GetColor() == PieceColor)
                    {
                        for (int iMoveRow = 0; iMoveRow < 8; ++iMoveRow)
                        {
                            for (int iMoveCol = 0; iMoveCol < 8; ++iMoveCol)
                            {
                                if (MainGameBoard[iRow][iCol]->IsLegalMove(iRow, iCol, iMoveRow, iMoveCol, MainGameBoard))
                                {
                                    // Make move and check whether king is in check
                                    Piece *tempPiece = MainGameBoard[iMoveRow][iMoveCol];
                                    MainGameBoard[iMoveRow][iMoveCol] = MainGameBoard[iRow][iCol];
                                    MainGameBoard[iRow][iCol] = 0;
                                    bool moreMoves = !IsInCheck(PieceColor);
                                    // Undo the move
                                    MainGameBoard[iRow][iCol] = MainGameBoard[iMoveRow][iMoveCol];
                                    MainGameBoard[iMoveRow][iMoveCol] = tempPiece;
                                    if (moreMoves)
                                    {
                                        return true;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        return false;
    }
};



class Game
{
private:
    ChessBoard board;
    char currentPlayer;

public:
    Game() : currentPlayer('W') {}
    ~Game() {}

    void Start()
    {
        do
        {
            GetNextMove(board.MainGameBoard);
            changeTurn();
        } while (!IsGameOver());
        board.Print();
    }

    void GetNextMove(Piece *GameBoard[8][8])
    {
        bool isValidMove = false;
        do
        {
            system("clear");
            board.Print();

            // Get input and convert to coordinates
            cout << currentPlayer << "'s Move: ";
            int startMove;
            cin >> startMove;
            int startRow = (startMove / 10) - 1;
            int startCol = (startMove % 10) - 1;

            cout << "To: ";
            int endMove;
            cin >> endMove;
            int iEndRow = (endMove / 10) - 1;
            int iEndCol = (endMove % 10) - 1;

            // Check that the indices are in range
            // and that the source and destination are different
            if ((startRow >= 0 && startRow <= 7) &&
                (startCol >= 0 && startCol <= 7) &&
                (iEndRow >= 0 && iEndRow <= 7) &&
                (iEndCol >= 0 && iEndCol <= 7))
            {
                // Additional checks in here
                Piece *currentPiece = GameBoard[startRow][startCol];
                // Check that the piece is the correct color
                if ((currentPiece != nullptr) && (currentPiece->GetColor() == currentPlayer))
                {
                    // Check that the destination is a valid destination
                    if (currentPiece->IsLegalMove(startRow, startCol, iEndRow, iEndCol, GameBoard))
                    {
                        // Make the move
                        Piece *tempPiece = GameBoard[iEndRow][iEndCol];
                        GameBoard[iEndRow][iEndCol] = GameBoard[startRow][startCol];
                        GameBoard[startRow][startCol] = 0;
                        // Make sure that the current player is not in check
                        if (!board.IsInCheck(currentPlayer))
                        {
                            delete tempPiece;
                            isValidMove = true;
                        }
                        else
                        { // Undo the last move
                            GameBoard[startRow][startCol] = GameBoard[iEndRow][iEndCol];
                            GameBoard[iEndRow][iEndCol] = tempPiece;
                        }
                    }
                }
            }
            if (!isValidMove)
            {
                cout << "Invalid Move!" << endl;
            }
        } while (!isValidMove);
    }

    void changeTurn()
    {
        currentPlayer = (currentPlayer == 'W') ? 'B' : 'W';
    }

    bool IsGameOver()
    {
        // Check that the current player can move
        // If not, we have a stalemate or checkmate
        bool moreMoves(false);
        moreMoves = board.CanMove(currentPlayer);
        if (!moreMoves)
        {
            if (board.IsInCheck(currentPlayer))
            {
                changeTurn();
                std::cout << "Checkmate, " << currentPlayer << " Wins!" << std::endl;
            }
            else
            {
                std::cout << "Draw!" << std::endl;
            }
        }
        return !moreMoves;
    }
};

int main()
{
    Game game;
    game.Start();
    return 0;
}

// Problem Statement
// I own a parking lot that can hold up to 'n' cars at any given point in time. Each slot is given a number starting at 1 increasing with increasing distance from the entry point in steps of one. I want to create an automated ticketing system that allows my customers to use my parking lot without human intervention.

// When a car enters my parking lot, I want to have a ticket issued to the driver. The ticket issuing process includes us documenting the registration number (number plate) and the colour of the car and allocating an available parking slot to the car before actually handing over a ticket to the driver (we assume that our customers are nice enough to always park in the slots allocated to them). The customer should be allocated a parking slot which is nearest to the entry. At the exit the customer returns the ticket which then marks the slot they were using as being available.

// Due to government regulation, the system should provide me with the ability to find out:

// Registration numbers of all cars of a particular colour.
// Slot number in which a car with a given registration number is parked.
// Slot numbers of all slots where a car of a particular colour is parked.



#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define FOR(i, n) for (long long int i = 0; i < n; i++)
using namespace std;

class Vehicle
{
public:
    int colour, reg_number;
    Vehicle(int colour, int reg_number)
    {
        this->colour = colour;
        this->reg_number = reg_number;
    }
};

class Ticket
{
public:
    int colour, reg_number, slot_number;
    Ticket(int colour, int reg_number, int slot_number)
    {
        this->colour = colour;
        this->reg_number = reg_number;
        this->slot_number = slot_number;
    }
};

class ParkingLot
{
    set<int> available_slots;
    map<int, set<int>> reg_by_color;
    map<int, int> slot_by_reg;

public:
    ParkingLot(int n)
    {
        for (int i = 1; i <= n; i++)
        {
            available_slots.insert(i);
        }
    }

    void get_available_slots()
    {
        if(available_slots.size() == 0)
        {
            cout<<"No available slots for parking."<<endl;
            return;
        }
        cout << "Available slots are : ";
        for (auto itr = available_slots.begin(); itr != available_slots.end(); itr++)
        {
            cout << (*itr) << " ";
        }
        cout << endl;
    }

    Ticket take_slot(Vehicle vehicle)
    {
        if (available_slots.size() == 0)
        {
            cout << "No available slots" << endl;
            return Ticket(-1, -1, -1);
        }
        else
        {
            int taken_slot = (*available_slots.begin());
            reg_by_color[vehicle.colour].insert(vehicle.reg_number);
            slot_by_reg[vehicle.reg_number] = taken_slot;
            available_slots.erase(taken_slot);

            cout << "Slot : " << taken_slot << " is occupied." << endl;

            return Ticket(vehicle.colour, vehicle.reg_number, taken_slot);
        }
    }

    void get_reg_by_colour(int colour)
    {
        cout << "Reg number of Cars with " << colour << " are : ";
        for (auto itr = reg_by_color[colour].begin(); itr != reg_by_color[colour].end(); itr++)
        {
            cout << (*itr) << " ";
        }
        cout << endl;
    }

    void getSlot_by_reg(int reg_number)
    {
        if (slot_by_reg.find(reg_number) == slot_by_reg.end())
        {
            cout << "No Cars with " << reg_number << " exists in parking." << endl;
        }
    }

    void get_slot_by_colour(int colour)
    {
        cout << "Slot number of Cars with " << colour << " are : ";
        for (auto itr = reg_by_color[colour].begin(); itr != reg_by_color[colour].end(); itr++)
        {
            cout << slot_by_reg[(*itr)] << " ";
        }
        cout << endl;
    }

    void leave_slot(Ticket ticket)
    {
        available_slots.insert(ticket.slot_number);
        reg_by_color[ticket.colour].erase(ticket.reg_number);
        slot_by_reg.erase(ticket.reg_number);
        cout << "Car with Reg. number " << ticket.reg_number << " left." << endl;
    }
};

int main()
{
    ParkingLot parking_lot(3);
    parking_lot.get_available_slots();

    Vehicle vehicle1(1, 123);
    Ticket ticket1 = parking_lot.take_slot(vehicle1);
    Vehicle vehicle2(1, 223);
    Ticket ticket2 = parking_lot.take_slot(vehicle2);
    parking_lot.get_available_slots();
    parking_lot.get_reg_by_colour(1);
    Vehicle vehicle3(2, 125);
    Vehicle vehicle4(2, 135);

    Ticket ticket3 = parking_lot.take_slot(vehicle3);
    Ticket ticket4 = parking_lot.take_slot(vehicle4);

    parking_lot.leave_slot(ticket1);
    ticket4 = parking_lot.take_slot(vehicle3);
    parking_lot.get_available_slots();

    return 0;
}

#include <bits/stdc++.h>
#define INF 10000000000
#define ll long long int
#define pb push_back
#define mp make_pair
#define FOR(i, n) for (long long int i = 0; i < n; i++)
#define FORR(i, a, b) for (int i = a; i < b; i++)
// think about a question calmly, don't get panic to solve A fast
// if after 10 mins you are unable to think anything see dashboard
using namespace std;

void djk_fun(vector<vector<vector<int>>> &adj, int src, vector<int> &dis)
{
    priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq;
    dis[src] = 0;
    pq.push({{0, src}});

    while (pq.size() > 0)
    {
        vector<int> vr = pq.top();
        pq.pop();

        int nod = vr[1];
        for (int i = 0; i < adj[nod].size(); i++)
        {
            int neg = adj[nod][i][0], wt = adj[nod][i][1];
            if (dis[nod] + wt < dis[neg])
            {
                dis[neg] = dis[nod] + wt;
                pq.push({dis[neg], neg});
            }
        }
    }
}

int short_path(vector<vector<vector<int>>> &adj, vector<vector<int>> &nh, int st, int en, int n)
{
    int m = nh.size(), ans = INT_MAX;
    // apply shortest path on src and dest
    vector<int> dis_src(n + 1, 1e9);
    vector<int> dis_dst(n + 1, 1e9);

    djk_fun(adj, st, dis_src);
    djk_fun(adj, en, dis_dst);

    for (int i = 0; i < m; i++)
    {
        int n1 = nh[i][0], n2 = nh[i][1], wt = nh[i][2];
        ans = min({ans, dis_src[n1] + wt + dis_dst[n2], dis_src[n2] + wt + dis_dst[n1]});
    }
    ans = min(ans, dis_src[en]);

    if(ans > 1e9)
    {
        return -1;
    }
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    ll n, m, st, en;
    cin >> n >> m;

    vector<vector<vector<int>>> adj(n + 1, vector<vector<int>>());
    vector<vector<int>> nh;

    // construct graph using state highways
    for (int i = 0; i < m; i++)
    {
        int u, v, st, nt;
        cin >> u >> v >> st >> nt;

        nh.pb({u, v, nt});
        adj[u].pb({v, st});
        adj[v].pb({u, st});
    }
    cin >> st >> en;

    cout << short_path(adj, nh, st, en, n) << endl;
    return 0;
}

enum string_code {
    eFred,
    eBarney,
    eWilma,
    eBetty,
    ...
};

string_code hashit (std::string const& inString) {
    if (inString == "Fred") return eFred;
    if (inString == "Barney") return eBarney;
    ...
}

void foo() {
    switch (hashit(stringValue)) {
    case eFred:
        ...
    case eBarney:
        ...
    }
}

using i64 = long long;
template<class T>
constexpr T power(T a, i64 b) {
	T res = 1;
	for (; b; b /= 2, a *= a) {
		if (b % 2) {
			res *= a;
		}
	}
	return res;
}

constexpr i64 mul(i64 a, i64 b, i64 p) {
	i64 res = a * b - i64(1.L * a * b / p) * p;
	res %= p;
	if (res < 0) {
		res += p;
	}
	return res;
}
template<i64 P>
struct MLong {
	i64 x;
	constexpr MLong() : x{} {}
	constexpr MLong(i64 x) : x{norm(x % getMod())} {}

	static i64 Mod;
	constexpr static i64 getMod() {
		if (P > 0) {
			return P;
		} else {
			return Mod;
		}
	}
	constexpr static void setMod(i64 Mod_) {
		Mod = Mod_;
	}
	constexpr i64 norm(i64 x) const {
		if (x < 0) {
			x += getMod();
		}
		if (x >= getMod()) {
			x -= getMod();
		}
		return x;
	}
	constexpr i64 val() const {
		return x;
	}
	explicit constexpr operator i64() const {
		return x;
	}
	constexpr MLong operator-() const {
		MLong res;
		res.x = norm(getMod() - x);
		return res;
	}
	constexpr MLong inv() const {
		assert(x != 0);
		return power(*this, getMod() - 2);
	}
	constexpr MLong &operator*=(MLong rhs) & {
		x = mul(x, rhs.x, getMod());
		return *this;
	}
	constexpr MLong &operator+=(MLong rhs) & {
		x = norm(x + rhs.x);
		return *this;
	}
	constexpr MLong &operator-=(MLong rhs) & {
		x = norm(x - rhs.x);
		return *this;
	}
	constexpr MLong &operator/=(MLong rhs) & {
		return *this *= rhs.inv();
	}
	friend constexpr MLong operator*(MLong lhs, MLong rhs) {
		MLong res = lhs;
		res *= rhs;
		return res;
	}
	friend constexpr MLong operator+(MLong lhs, MLong rhs) {
		MLong res = lhs;
		res += rhs;
		return res;
	}
	friend constexpr MLong operator-(MLong lhs, MLong rhs) {
		MLong res = lhs;
		res -= rhs;
		return res;
	}
	friend constexpr MLong operator/(MLong lhs, MLong rhs) {
		MLong res = lhs;
		res /= rhs;
		return res;
	}
	friend constexpr std::istream &operator>>(std::istream &is, MLong &a) {
		i64 v;
		is >> v;
		a = MLong(v);
		return is;
	}
	friend constexpr std::ostream &operator<<(std::ostream &os, const MLong &a) {
		return os << a.val();
	}
	friend constexpr bool operator==(MLong lhs, MLong rhs) {
		return lhs.val() == rhs.val();
	}
	friend constexpr bool operator!=(MLong lhs, MLong rhs) {
		return lhs.val() != rhs.val();
	}
};

template<>
i64 MLong<0LL>::Mod = i64(1E18) + 9;

template<int P>
struct MInt {
	int x;
	constexpr MInt() : x{} {}
	constexpr MInt(i64 x) : x{norm(x % getMod())} {}

	static int Mod;
	constexpr static int getMod() {
		if (P > 0) {
			return P;
		} else {
			return Mod;
		}
	}
	constexpr static void setMod(int Mod_) {
		Mod = Mod_;
	}
	constexpr int norm(int x) const {
		if (x < 0) {
			x += getMod();
		}
		if (x >= getMod()) {
			x -= getMod();
		}
		return x;
	}
	constexpr int val() const {
		return x;
	}
	explicit constexpr operator int() const {
		return x;
	}
	constexpr MInt operator-() const {
		MInt res;
		res.x = norm(getMod() - x);
		return res;
	}
	constexpr MInt inv() const {
		assert(x != 0);
		return power(*this, getMod() - 2);
	}
	constexpr MInt &operator*=(MInt rhs) & {
		x = 1LL * x * rhs.x % getMod();
		return *this;
	}
	constexpr MInt &operator+=(MInt rhs) & {
		x = norm(x + rhs.x);
		return *this;
	}
	constexpr MInt &operator-=(MInt rhs) & {
		x = norm(x - rhs.x);
		return *this;
	}
	constexpr MInt &operator/=(MInt rhs) & {
		return *this *= rhs.inv();
	}
	friend constexpr MInt operator*(MInt lhs, MInt rhs) {
		MInt res = lhs;
		res *= rhs;
		return res;
	}
	friend constexpr MInt operator+(MInt lhs, MInt rhs) {
		MInt res = lhs;
		res += rhs;
		return res;
	}
	friend constexpr MInt operator-(MInt lhs, MInt rhs) {
		MInt res = lhs;
		res -= rhs;
		return res;
	}
	friend constexpr MInt operator/(MInt lhs, MInt rhs) {
		MInt res = lhs;
		res /= rhs;
		return res;
	}
	friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
		i64 v;
		is >> v;
		a = MInt(v);
		return is;
	}
	friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
		return os << a.val();
	}
	friend constexpr bool operator==(MInt lhs, MInt rhs) {
		return lhs.val() == rhs.val();
	}
	friend constexpr bool operator!=(MInt lhs, MInt rhs) {
		return lhs.val() != rhs.val();
	}
};

template<>
int MInt<0>::Mod = 998244353;

template<int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();

constexpr int P = 998244353;
using Z = MInt<P>;

    // Iterating over whole array
    std::vector<int> v = { 0, 1, 2, 3, 4, 5 };
    for (auto i : v)
        std::cout << i << ' ';
  
    std::cout << '\n';

      // Iterating over array
    int a[] = { 0, 1, 2, 3, 4, 5 };
    for (int n : a)
        std::cout << n << ' ';
    s
    td::cout << '\n';
  
    // the initializer may be a braced-init-list
    for (int n : { 0, 1, 2, 3, 4, 5 })
        std::cout << n << ' ';

    std::cout << '\n';
  
    // Printing string characters
    std::string str = "Geeks";
    for (char c : str)
        std::cout << c << ' ';

#include <iostream>
using namespace std;
 
void fun(int *arr, unsigned int n)
{
   int i;
   for (i = 0; i < n; i++)
     cout <<" "<< arr[i];
}
 
// Driver program
int main()
{
   int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};
   unsigned int n = sizeof(arr)/sizeof(arr[0]);
   fun(arr, n);
   return 0;
}

    // Assign vector
    vector<int> v;
 
    // fill the vector with 10 five times
    v.assign(5, 10);
 
    cout << "The vector elements are: ";
    for (int i = 0; i < v.size(); i++)
        cout << v[i] << " ";
 
    // inserts 15 to the last position
    v.push_back(15);
    int n = v.size();
    cout << "\nThe last element is: " << v[n - 1];
 
    // removes last element
    v.pop_back();
 
    // prints the vector
    cout << "\nThe vector elements are: ";
    for (int i = 0; i < v.size(); i++)
        cout << v[i] << " ";
 
    // inserts 5 at the beginning
    v.insert(v.begin(), 5);
 
    cout << "\nThe first element is: " << v[0];
 
    // removes the first element
    v.erase(v.begin());
 
    cout << "\nThe first element is: " << v[0];
 
    // inserts at the beginning
    v.emplace(v.begin(), 5);
    cout << "\nThe first element is: " << v[0];
 
    // Inserts 20 at the end
    v.emplace_back(20);
    n = v.size();
    cout << "\nThe last element is: " << v[n - 1];
 
    // erases the vector
    v.clear();
    cout << "\nVector size after clear(): " << v.size();
 
    // two vector to perform swap
    vector<int> v1, v2;
    v1.push_back(1);
    v1.push_back(2);
    v2.push_back(3);
    v2.push_back(4);
 
    // Swaps v1 and v2
    v1.swap(v2);

#include<iostream>

using namespace std;

int main() {

    long long int a;

    cin>>a;

    int d=0;

    

    for(int i = 2;i<a;i++){

    int flag=0;

    if(a%i==0){

    for(int j=2;j<=i/2;j++){

    if(i%j==0 ){

    flag++;

    break;

    }

    }

    

    if(flag==0){

    

    if(d<i){

    d=i;

    

    }

    }

    }

    }

    cout<<d;

    

    

    

    return 0;

}

    

#include <iostream>

using namespace std;

int main(){
 
 bool ships[3][4]={{0,1,0,1},{1,0,0,1},{1,0,1,0}};
int n=1,t=0,guess=0,maxship=1;

while (n!=0)
{
    cout<<"Enter cordinates of the ship row-(0-2),col-(0-3): ";
    int c,b;
    cin>>c>>b;
   
    if (ships[c][b]==1)
    {
        
        cout<<"You hit the ship"<<endl;
        t++;
        ships[c][b]=0;
        
        if (maxship>5)
    {
        cout<<"you guessed all the coordinates in the perfect number: "<<endl;
       break;
    }
    maxship++;
    }
    else
    {
        cout<<"nearly miss next try:"<<endl;
    }
    cout<<"You want to continue press 1 for exit=0: ";
    cin>>n;
    
    
    guess++;
}


cout<<"Your number of hit:"<<t<<endl;
cout<<"number of guesses:"<<guess;



        
    
}

#include <iostream>
#include <math.h>

using namespace std;
// for find how many values for root;
int div(int a){
    int n=0;
    while (a!=0)
    {
        int d=a%10;
        a/=10;
        n++;
    }
    return n;
    
}
//for sum of the digit
int sum(int a){
    int sum=0;
    int n=a;
    while (a!=0)
    {
        int d=a%10;
        sum+=pow(d,div(n));
        a/=10;
    }
    return sum;
}
//main function
int main(){
    
    
    int a;
    cin>>a;
    int n=a;
    
    
    if(sum(a)==n){
        cout<<"Armstrong number";
    }
    else{
        cout<<"Not a Armstrong number";
    }


    
        
    
}

#include <iostream>
#include <math.h>

using namespace std;

void sumNum(){
    int a;
    cin>>a;
    int sum=0;
while (a>0)
    {
       int d=a%10;
       sum+=d;
       a=a/10;
        
    }
    cout<<sum<<endl;
}


int main(){

// int b=1;
//         while (b!=0)
//         {
//             sumNum(); 
//             cout<<"You want to exit press 0 continue 1;";
//             cin>>b;
            
            
//         }
int b;
        do
        {
          sumNum(); 
           cout<<"You want to exit press 0 continue 1;";
             cin>>b;
        } while (b!=0);
        
        cout<<"Thanks for coming";
 

}

#include <iostream>

using namespace std;



int main(){
  int arr[10]={1};
  int n=10;
  for(int i=0;i<n;i++){
   if (arr[i]>0)
   {
      cout<<arr[i]<<endl;
   }
   if (arr[i]<=0)
   {
      int b=arr[i] | 1 ;
      cout<<b<<endl;
   }
   
   
   
  }

}

#include "Eigen/Dense"
#include <vector>
#include <limits>
#include <cstring>
#include <iostream>

using namespace Eigen;

namespace Optimization
{
    template<int nDims>
    class NelderMead {
    public:
        typedef Array<double, 1, nDims> FunctionParameters;
        typedef std::function<double(FunctionParameters)> ErrorFunction;

        NelderMead(ErrorFunction errorFunction, FunctionParameters initial,
                   double minError, double initialEdgeLength,
                   double shrinkCoeff = 1, double contractionCoeff = 0.5,
                   double reflectionCoeff = 1, double expansionCoeff = 1)
                : errorFunction(errorFunction), minError(minError),
                shrinkCoeff(shrinkCoeff), contractionCoeff(contractionCoeff),
                reflectionCoeff(reflectionCoeff), expansionCoeff(expansionCoeff),
                worstValueId(-1), secondWorstValueId(-1), bestValueId(-1)
        {
            this->errors = std::vector(nDims + 1, std::numeric_limits<double>::max());

            const double b = initialEdgeLength / (nDims * SQRT2) * (sqrt(nDims + 1) - 1);
            const double a = initialEdgeLength / SQRT2;

            this->values = initial.replicate(nDims + 1, 1);

            for (int i = 0; i < nDims; i++)
            {
                FunctionParameters simplexRow;
                simplexRow.setConstant(b);
                simplexRow(0, i) = a;
                simplexRow += initial;

                this->values.row(i+1) = simplexRow;
            }
        }

        void optimize()
        {
            for (int i = 0; i < nDims+1; i++)
            {
                this->errors.at(i) = this->errorFunction(this->values.row(i));
            }

            this->invalidateIdsCache();

            while (this->errors.at(this->bestValueId) > this->minError)
            {
                step();
                auto bestError = this->errorFunction(this->best());
                auto worstError = this->errorFunction(this->worst());

                std::cout << "Best error " << std::to_string(bestError) << " with : " << this->best();
                std::cout << " Worst error " << std::to_string(worstError) << " with : " << this->worst();
                std::cout << '\n';
            }
        }

        void step()
        {
            auto meanWithoutWorst = this->getMeanWithoutWorst();

            auto reflectionOfWorst = this->getReflectionOfWorst(meanWithoutWorst);
            auto reflectionError = this->errorFunction(reflectionOfWorst);

            FunctionParameters newValue = reflectionOfWorst;
            double newError = reflectionError;

            bool shrink = false;

            if (reflectionError < this->errors.at(this->bestValueId))
            {
                auto expansionValue = this->expansion(meanWithoutWorst, reflectionOfWorst);
                double expansionError = this->errorFunction(expansionValue);

                if (expansionError < this->errors.at(this->bestValueId))
                {
                    newValue = expansionValue;
                    newError = expansionError;
                }
            }
            else if (reflectionError > this->errors.at(this->worstValueId))
            {
                newValue = this->insideContraction(meanWithoutWorst);
                newError = this->errorFunction(newValue);

                if (newError > this->errors.at(this->worstValueId)) { shrink = true; }
            }
            else if (reflectionError > this->errors.at(this->secondWorstValueId))
            {
                newValue = this->outsideContraction(meanWithoutWorst);
                newError = this->errorFunction(newValue);

                if (newError > reflectionError) { shrink = true; }
            }
            else
            {
                newValue = reflectionOfWorst;
                newError = reflectionError;
            }

            if (shrink)
            {
                this->shrink();
                this->invalidateIdsCache();
                return;
            }

            this->values.row(this->worstValueId) = newValue;
            this->errors.at(this->worstValueId) = newError;
            this->invalidateIdsCache();
        }

        inline FunctionParameters worst() { return this->values.row(this->worstValueId); }
        inline FunctionParameters best() { return this->values.row(this->bestValueId); }

    private:

        void shrink()
        {
            auto bestVertex = this->values.row(this->bestValueId);

            for (int i = 0; i < nDims + 1; i++)
            {
                if (i == this->bestValueId) { continue; }

                this->values.row(i) = bestVertex + this->shrinkCoeff * (this->values.row(i) - bestVertex);
                this->errors.at(i) = this->errorFunction(this->values.row(i));
            }
        }

        inline FunctionParameters expansion(FunctionParameters meanWithoutWorst, FunctionParameters reflection)
        {
            return reflection + this->expansionCoeff * (reflection - meanWithoutWorst);
        }

        inline FunctionParameters insideContraction(FunctionParameters meanWithoutWorst)
        {
            return meanWithoutWorst - this->contractionCoeff * (meanWithoutWorst - this->worst());
        }

        inline FunctionParameters outsideContraction(FunctionParameters meanWithoutWorst)
        {
            return meanWithoutWorst + this->contractionCoeff * (meanWithoutWorst - this->worst());
        }

        FunctionParameters getReflectionOfWorst(FunctionParameters meanWithoutWorst)
        {
            return meanWithoutWorst + this->reflectionCoeff * (meanWithoutWorst - this->worst());
        }

        FunctionParameters getMeanWithoutWorst()
        {
            FunctionParameters mean(0);
            for (int i = 0; i < nDims + 1; i++)
            {
                if (i == this->worstValueId) { continue; }

                mean += this->values.row(i);
            }

            // Not divided by nDims+1 because there's one ignored value.
            mean /= nDims;

            return mean;
        }

        void invalidateIdsCache() {
            double worstError = std::numeric_limits<double>::min();
            int worstId = -1;
            double secondWorstError = std::numeric_limits<double>::max();
            int secondWorstId = -1;
            double bestError = std::numeric_limits<double>::max();
            int bestId = -1;

            for (int i = 0; i < nDims + 1; i++)
            {
                auto error = this->errors.at(i);

                if (error > worstError)
                {
                    secondWorstError = worstError;
                    secondWorstId = worstId;
                    worstError = error;
                    worstId = i;
                }
                else if (error > secondWorstError)
                {
                    secondWorstError = error;
                    secondWorstId = i;
                }

                if (error < bestError)
                {
                    bestError = error;
                    bestId = i;
                }
            }

            // If we deal with a problem in 1D, it won't be set.
            if (secondWorstId == -1)
            {
                secondWorstId = worstId;
            }

            this->bestValueId = bestId;
            this->worstValueId = worstId;
            this->secondWorstValueId = secondWorstId;
        }

        ErrorFunction errorFunction;
        Array<double, nDims + 1, nDims> values;
        std::vector<double> errors;

        int worstValueId;
        int secondWorstValueId;
        int bestValueId;

        double minError;

        double shrinkCoeff;
        double expansionCoeff;
        double contractionCoeff;
        double reflectionCoeff;

        const double SQRT2 = sqrt(2);
    };
}

#include<bits/stdc++.h>

using namespace std;

int main() {
  unordered_map < int, int > mp;
   for (int i = 1; i <= 5; i++) {
    mp.insert({ i , i * 10});
  }

  cout << "Elements present in the map: " << endl;
  cout << "Key\tElement" << endl;
  for (auto it = mp.begin(); it != mp.end(); it++) {
    cout << it -> first << "\t" << it -> second << endl;
  }

  int n = 2;
  if (mp.find(2) != mp.end())
    cout << n << " is present in map" << endl;

  mp.erase(mp.begin());
  cout << "Elements after deleting the first element: " << endl;
  cout << "Key\tElement" << endl;
  for (auto it = mp.begin(); it != mp.end(); it++) {
    cout << it -> first << "\t" << it -> second << endl;
  }

  cout << "The size of the map is: " << mp.size() << endl;

  if (mp.empty() == false)
    cout << "The map is not empty " << endl;
  else
    cout << "The map is empty" << endl;
  mp.clear();
  cout << "Size of the set after clearing all the elements: " << mp.size();
}

int i=1;
switch (i) {
case 1:
        i=5;
        break;
default:
        i=6;
}
return 0;



0x100000eeb:  movl   $0x1, -0x8(%rbp) ;int i=1;
0x100000ef2:  xorl   %eax, %eax
0x100000ef4:  movb   %al, %cl
0x100000ef6:  testb  %cl, %cl         ;switch(i)
0x100000ef8:  jne    0x100000f0f      ;i is not 1 go to default:
0x100000efe:  jmp    0x100000f03      ;i is 1 go to case 1:
0x100000f03:  movl   $0x5, -0x8(%rbp) ;case 1: i=5;
0x100000f0a:  jmp    0x100000f16      ;break;
0x100000f0f:  movl   $0x6, -0x8(%rbp) ;default: i=6;
0x100000f16:  movl   $0x0, %eax       ;first instruction after switch-case

switch (month) {
 case 2:
   if(isLeapYear)
    days = 29;  
   else
    days = 28;
    break;
  case 4:
  case 6:
  case 9:    // do the same thing
  case 11:
    days = 30;
     break;
  default:
    days = 31;
 }

switch (current_key) 
{
  case KEY_W:
  case KEY_UP:
  case KEY_SPACE:
       player->jump();
       break;
  case KEY_S:
  case KEY_DOWN:
  case KEY_SHIFT:
       player->cover();
       break;
  default:
       //Do something
       break; 
}

#include <iostream>
#include <sstream>
#include <vector>

using namespace std;

vector<string> split (const string &s, char delim) {
    vector<string> result;
    stringstream ss (s);
    string item;

    while (getline (ss, item, delim)) {
        result.push_back (item);
    }

    return result;
}

int main() {
    string str = "adsf+qwer+poui+fdgh";
    vector<string> v = split (str, '+');

    for (auto i : v) cout << i << endl;

    return 0;
}

#include <iostream>
#include <sstream>
#include <vector>

using namespace std;

// for string delimiter
vector<string> split (string s, string delimiter) {
    size_t pos_start = 0, pos_end, delim_len = delimiter.length();
    string token;
    vector<string> res;

    while ((pos_end = s.find (delimiter, pos_start)) != string::npos) {
        token = s.substr (pos_start, pos_end - pos_start);
        pos_start = pos_end + delim_len;
        res.push_back (token);
    }

    res.push_back (s.substr (pos_start));
    return res;
}

int main() {
    string str = "adsf-+qwret-+nvfkbdsj-+orthdfjgh-+dfjrleih";
    string delimiter = "-+";
    vector<string> v = split (str, delimiter);

    for (auto i : v) cout << i << endl;

    return 0;
}

#include <iostream>
#include <string>

int main()
{
    std::string s = "scott>=tiger";
    std::string delim = ">=";

    auto start = 0U;
    auto end = s.find(delim);
    while (end != std::string::npos)
    {
        std::cout << s.substr(start, end - start) << std::endl;
        start = end + delim.length();
        end = s.find(delim, start);
    }

    std::cout << s.substr(start, end);
}

std::string s = "scott>=tiger>=mushroom";
std::string delimiter = ">=";

size_t pos = 0;
std::string token;
while ((pos = s.find(delimiter)) != std::string::npos) {
    token = s.substr(0, pos);
    std::cout << token << std::endl;
    s.erase(0, pos + delimiter.length());
}
std::cout << s << std::endl;

/*
Program: Gauss Jordan Method
All array indexes are assumed to start from 1
*/

#include<iostream>
#include<iomanip>
#include<math.h>
#include<stdlib.h>

#define   SIZE   10

using namespace std;

int main()
{
	 float a[SIZE][SIZE], x[SIZE], ratio;
	 int i,j,k,n;

     /* Setting precision and writing floating point values in fixed-point notation. */
     cout<< setprecision(3)<< fixed;

	 /* Inputs */
	 /* 1. Reading number of unknowns */
	 cout<<"Enter number of unknowns: ";
	 cin>>n;

	 /* 2. Reading Augmented Matrix */
	 cout<<"Enter Coefficients of Augmented Matrix: "<< endl;
	 for(i=1;i<=n;i++)
	 {
		  for(j=1;j<=n+1;j++)
		  {
			   cout<<"a["<< i<<"]"<< j<<"]= ";
			   cin>>a[i][j];
		  }
	 }
    /* Applying Gauss Jordan Elimination */
     for(i=1;i<=n;i++)
     {
          if(a[i][i] == 0.0)
          {
               cout<<"Mathematical Error!";
               exit(0);
          }
          for(j=1;j<=n;j++)
          {
               if(i!=j)
               {
                    ratio = a[j][i]/a[i][i];
                    for(k=1;k<=n+1;k++)
                    {
                        a[j][k] = a[j][k] - ratio*a[i][k];
                    }
               }
          }
     }
     /* Obtaining Solution */
     for(i=1;i<=n;i++)
     {
        x[i] = a[i][n+1]/a[i][i];
     }

	 /* Displaying Solution */
	 cout<< endl<<"Solution: "<< endl;
	 for(i=1;i<=n;i++)
	 {
	  	cout<<"x["<< i<<"] = "<< x[i]<< endl;
	 }

	 return(0);
}

std::ostringstream strs;
strs << dbl;
std::string str = strs.str();

{ // Block scope
     Foo fooVal = makeFoo(); // Say makeFoo() returns a (temporary, unnamed) Foo
     // Here the temporary Foo is dead (fooVal is a copy).

     // Foo &fooRef = makeFoo(); // Error, reference is non-const
     Foo const &fooCRef = makeFoo(); // All good

     // ...

     // The second temporary is still alive
     fooCRef.doSomethingFunny(); // Works like a charm !

} // The second temporary dies with fooRef

//------------------------------------------

Foo *fooPtr = new Foo; // Here is a Foo
Foo &fooRef = *fooPtr; // Here is an alias for that Foo

delete fooPtr; // Here is the end of that Foo's life

fooRef.doSomethingFunny(); // Here comes trouble...

#include<iostream>
using namespace std;
#define n 100
//stack class
class stack{
    public:
        int *arr;
        int top;
        //constructor for allocating memory
        stack()
        {
            arr = new int[n];
            top = -1;
        }

        //push function to insert an element at the top of stack
        void push(int data)
        {
            if(this->top==n-1)
            {
                cout << "no space for the new element " << endl;
                return;
            }

            ++top;
            arr[top] = data;
            

            return;
        }
        //Function for removing the element from the top of the stack 
        void pop()
        {
            if(top==-1)
            {
                cout << "Empty Stack " << endl;
                return;
            }
            top--;
        }

        //Function to get the top element value

        int Top()
        {
            if(top==-1)
            {
                cout << "Empty Stack " << endl;
                return -1;
            }
            if(top>n-1)
            {
                cout << "stack overflow " << endl;
                return -1;
            }
            return arr[top];
        }

        //Function to check is stack is empty or not
        bool empty()
        {
            return top == -1;
        }
//Function for printing the stack
void print()
{
    if(top==-1)
    {
        cout << "Empty Stack " << endl;
        return;
    }
    for (int i = 0; i <= top;i++)
    {
        cout << arr[i] << "  ";
    }
    return;
}

~stack()
{
    delete arr;
}

};


//main function
int main()
{
    //making object of stack class
    stack object;
    object.push(1);
    object.push(2);
    object.push(3);
    object.push(4);
    cout << "1st print " << endl;
    object.print();
    object.pop();
    cout << endl;
    cout << "2nd print" << endl;
    object.print();
    cout << endl;
   cout<< object.Top();
   cout << endl;
   //checking if the stack is Empty
   cout<<object.empty();
   cout << endl;

   return 0;
}

#include <iostream>
#define MAX 10
using namespace std;

//Deklarasi struct tumpukan
struct Stack {
	int top, data[MAX];
}Tumpukan;

void init(){
	Tumpukan.top = -1;
}

bool isEmpty() {
  return Tumpukan.top == -1;
}

bool isFull() {
	return Tumpukan.top == MAX-1;
}
void push() {
   if (isFull()) {
		cout << "\nTumpukan penuh"<<endl;
	}
	else {
    Tumpukan.top++;
    cout << "\nMasukkan data = "; cin >> Tumpukan.data[Tumpukan.top];
    cout << "Data " << Tumpukan.data[Tumpukan.top] << " masuk ke stack"<<endl;
	}
}
void pop() {
	if (isEmpty()) {
		cout << "\nData kosong\n"<<endl;
	}
	else {
    cout << "\nData "<<Tumpukan.data[Tumpukan.top]<<" sudah terambil"<<endl;
    Tumpukan.top--;
	}
}
void printStack() {
	if (isEmpty()) {
		cout << "Tumpukan kosong";
	}
	else {
    cout << "\nTumpukan : ";
		for (int i = Tumpukan.top; i >= 0; i--)
			cout << Tumpukan.data[i] << ((i == 0) ? "" : ",");
	}
}
int main() {
	int pilihan;
	init();
	do {
    printStack();
		cout << "\n1. Input (Push)\n"
        <<"2. Hapus (Pop)\n"
        <<"3. Keluar\n"
        <<"Masukkan Pilihan: ";
		cin >> pilihan;
		switch (pilihan)
		{
		case 1:
			push();
			break;
		case 2:
			pop();
			break;
		default:
      cout << "Pilihan tidak tersedia" << endl;
			break;
		}
	} while (pilihan!=3);
}

// here normal pointer
P* ptr = new P; // usual pointer allocated on heap
P& nat = *ptr; // object on heap bind to native object

//.. here CLI managed 
MO^ mngd = gcnew MO; // allocate on CLI heap
MO% rr = *mngd; // object on CLI heap reference to gc-lvalue

Hashtable^ tempHash = gcnew Hashtable(iterators_);

IDictionaryEnumerator^ enumerator = tempHash->GetEnumerator();

// pointer to new std::string object -> memory is not garbage-collected
std::string* strPtr = new std::string;

// pointer to System::String object -> memory is garbage-collected
System::String^ manStr = gcnew System::String;

#include <sstream>
#include <iostream>
#include <iomanip>

int main()
{
  double d = 12.3456789;
  std::stringstream ss;

  ss << std::fixed << std::setprecision( 4 ) << d;

  std::cout << ss.str() << std::endl;
}

class Foo {
public:
    Foo(std::shared_ptr<Boo> boo) 
        : m_Boo(std::move(boo)) {}
private:
    std::shared_ptr<Boo> m_Boo;
};

#include <unsupported/Eigen/CXX11/Tensor>
int main(){
    // Define a tensor
    Eigen::Tensor<double,3> A(55,50,2);
    A.setRandom();

    // Define the pairs of indices to multiply (i.e. index 1 on A twice)
    std::array<Eigen::IndexPair<long>, 1> idx = { Eigen::IndexPair<long> {1, 1} };
    
    // Define a parallel device 
    int num_threads = 4;
    Eigen::ThreadPool       tpl (num_threads);
    Eigen::ThreadPoolDevice dev (&tpl, num_threads);

    // Initialize result buffer B. B will have dimensions [55,2,55,2]
    Eigen::Tensor<double,4> B(55,2,55,2);

    // Contract using the parallel device
    B.device(dev) = A.contract(A, idx);
}

#include <fstream>

std::ifstream file(FILENAME);
if (file.is_open()) {
    std::string line;
    while (std::getline(file, line)) {
        // using printf() in all tests for consistency
        printf("%s", line.c_str());
    }
    file.close();
}

class int_ptr_wrapper
{
public:
    int_ptr_wrapper(int value = 0) :
    mInt(new int(value))
    {}

    // note! needs copy-constructor and copy-assignment operator!

    ~int_ptr_wrapper()
    {
        delete mInt;
    }

private:
    int* mInt;
};

int intvar = char - '0';