// Challenge Solution - Part #3 ------------------------------------------------------
// Create cheatingOpponent() Function
void cheatingOpponent(){
  // For each position on Player 1's grid, if it is green, that position has not been hit yet.
  // So target it with the next (cheating) hit.
  for (int k = 0; k < MATRIX_H * MATRIX_W; k++) {
    if (grid1S[k] == 4) { // If position is green, then ship is present
      target2[k] = 1; // Red Color == Hit
      grid1S[k] = 1;  // Red Color == Hit

      // Mark the attack as complete
      attackComplete = 1;
      break;
    }
  }

  // Delay briefly for smoother gameplay
  delay(500);
}
// End Challenge Solution ------------------------------------------------------------
 
  

    // Challenge Solution - Part #2 ------------------------------------------------------
    // Check to see if the cheating variable is below the cheating threshold
    // If it is, then call the "cheatingOpponent" function which you will create next
    if (pz <= cheatingPercentage){
      // Call the Cheating Function to find a target from Player 1's grid to hit. 
      cheatingOpponent();
    }
 

    // Challenge Solution - Part #1 ------------------------------------------------------
    // Comment out the following code
    /*if(hit == 1){
      post_hit_AI();
    } else {
      try_to_place_targetAI();
    }*/

    // Create a variable that represents the computer's "chance of cheating"
    int cheatingPercentage = 30;

    // Create a variable to hold the value from the "dice roll"
    int pz;

    // Roll the dice to get a percentage chance of cheating
    pz = random(100);
    

class DisjointSet {
    vector<int> rank, parent;
public:
    DisjointSet(int n) {
        rank.resize(n + 1, 0);
        parent.resize(n + 1);
        for (int i = 0; i <= n; i++) {
            parent[i] = i;
        }
    }

    int findUPar(int node) {
        if (node == parent[node])
            return node;
        return parent[node] = findUPar(parent[node]);
    }

    void unionByRank(int u, int v) {
        int ulp_u = findUPar(u);
        int ulp_v = findUPar(v);
        if (ulp_u == ulp_v) return;
        if (rank[ulp_u] < rank[ulp_v]) {
            parent[ulp_u] = ulp_v;
        }
        else if (rank[ulp_v] < rank[ulp_u]) {
            parent[ulp_v] = ulp_u;
        }
        else {
            parent[ulp_v] = ulp_u;
            rank[ulp_u]++;
        }
    }
};

using namespace std;

// An iterative binary search function.
int binarySearch(int arr[], int low, int high, int x)
{
    while (low <= high) {
        int mid = low + (high - low) / 2;

        // Check if x is present at mid
        if (arr[mid] == x)
            return mid;

        // If x greater, ignore left half
        if (arr[mid] < x)
            low = mid + 1;

        // If x is smaller, ignore right half
        else
            high = mid - 1;
    }

    // If we reach here, then element was not present
    return -1;
}

// Driver code
int main(void)
{
    int arr[] = { 2, 3, 4, 10, 40 };
    int x = 10;
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = binarySearch(arr, 0, n - 1, x);
    if(result == -1) cout << "Element is not present in array";
    else cout << "Element is present at index " << result;
    return 0;
}

// Use the ColorFromPalette function to rotate through the rainbow by the colorIndex
//ColorFromPalette( paletteName, colorIndex[0-255], brightness[0-255], blendType[NOBLEND or LINEARBLEND])
leds[j] = ColorFromPalette(RainbowColors_p, colorIndex, 255, LINEARBLEND);
colorIndex += 15;  // Increment the colorIndex to change the color for the next LED

// Add new variable to track the color palette indices
uint8_t colorIndex;

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

struct Time {
    int hours;
    int minutes;
    int seconds;
};

// Function to calculate time difference
Time calculateTimeDifference(Time t1, Time t2) {
    Time difference;

    // Calculate total seconds for both times
    int seconds1 = t1.hours * 3600 + t1.minutes * 60 + t1.seconds;
    int seconds2 = t2.hours * 3600 + t2.minutes * 60 + t2.seconds;

    // Difference in seconds
    int diffSeconds = seconds1 - seconds2;

    // Convert difference back to hours, minutes, seconds
    difference.hours = diffSeconds / 3600;
    diffSeconds = diffSeconds % 3600;
    difference.minutes = diffSeconds / 60;
    difference.seconds = diffSeconds % 60;

    return difference;
}

int main() {
    // Input the two times
    Time t1, t2;
    char colon;
    cin >> t1.hours >> colon >> t1.minutes >> colon >> t1.seconds;
    cin >> t2.hours >> colon >> t2.minutes >> colon >> t2.seconds;

    // Calculate the difference
    Time difference = calculateTimeDifference(t1, t2);

    // Output the difference in HH:MM:SS format
    cout << setfill('0') << setw(2) << difference.hours << ":"
         << setfill('0') << setw(2) << difference.minutes << ":"
         << setfill('0') << setw(2) << difference.seconds << endl;

    return 0;
}

#include <iostream>
#include <string>

using namespace std;

class Person {
private:
    string name;
    int age;
    string gender;

public:
    void setDetails(string n, int a, string g) {
        name = n;
        age = a;
        gender = g;
    }

    void displayDetails() {
        string uppercaseName = "";
        string uppercaseGender = "";

        for (char c : name) {
            uppercaseName += toupper(c);
        }

        for (char c : gender) {
            uppercaseGender += toupper(c);
        }

        cout << uppercaseName << " " << age << " " << uppercaseGender << endl;
    }
};

int main() {
    Person person;
    string name;
    int age;
    string gender;


    cin >> name;
 
    cin >> age;

    cin >> gender;

    person.setDetails(name, age, gender);
    person.displayDetails();

    return 0;
}

#include <iostream>
#include <string>

using namespace std;

class dayOfWeek {
public:
    int dayNumber;
    string dayName;

    void setDay(int n) {
        dayNumber = n;
        switch (dayNumber) {
            case 1: dayName = "Sunday"; break;
            case 2: dayName = "Monday"; break;
            case 3: dayName = "Tuesday"; break;
            case 4: dayName = "Wednesday"; break;
            case 5: dayName = "Thursday"; break;
            case 6: dayName = "Friday"; break;
            case 7: dayName = "Saturday"; break;
            case 0: dayName = "Weekend"; break;
            default: dayName = "Invalid"; break;
        }
    }

    void printDay() {
        cout << dayName << endl;
    }
};

int main() {
    dayOfWeek day;
    int dayNumber;

    cin >> dayNumber;

    day.setDay(dayNumber);
    day.printDay();

    return 0;
}

#include <iostream>
#include <cmath>

using namespace std;

int main() {
    long long binaryNumber;

    cin >> binaryNumber;

    long long decimalNumber = 0;
    int power = 0;

    while (binaryNumber != 0) {
        int digit = binaryNumber % 10;
        decimalNumber += digit * pow(2, power);
        binaryNumber /= 10;
        power++;
    }

    cout << "Decimal: " << decimalNumber << endl;

    return 0;
}

#include <bits/stdc++.h>
#include <iostream>
#include <utility>
#include <vector>
#include <queue>
#include <limits>
using namespace std;

void D(int N, vector<pair<int,int>> adj[N]; int source){
    vector<int> dist(V,1000000);
    dist[source] = 0;
    priority_queue<pair<int,int>, vector<pair<int,int>> , greater<pair<int,int>>> pq;
    pq.push({0,source});
    
    while(pq.empty() != 0) {
        int u = pq.top().second;
        int d = pq.top().first;
        pq.pop();
        
        for(int i = 0; i < adj[u].size(); i++){
            int v = adj[u][i].first;
            int weight = adj[u][i].second;
            
            if(dist[adj[u][i].first] > pq.top().first + adj[u][i].second){
                dist[adj[u][i].first] = pq.top().first + adj[u][i].second;
                pq.push({dist[adj[u][i].first], adj[u][i].first});
            }
    }
}


int main(){
    int N,M; //số đỉnh, cạnh
    cin >> N >> M;
    
    vector<pair<int,int>> adj;
    for (int i = 0; i < M; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back({b,c}); // Nếu đồ thị là vô hướng
        adj[b].push_back({a,c});
    }
    
    int source;
    cin >> source;
    D(N, adj, source);
    return 0;
    
}

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

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    string s;
    cin >> s;
    int temp = 1;
    int ans;
    for(int i = 1; i < s.size(); i++){
        if(s[i] == s[i-1]){
            temp += 1;
            cout << temp << " ";
        }
        else;
            ans = max(ans, temp);
            temp = 1;
        }
    if(ans >= 7){
        cout << "YES";
    }
    else{
        cout << "NO";
    }
    return 0;
}

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

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    
    int n;
    cin >> n;
    
    vector<vector<int>> S(n);
    for(int i = 0; i < n; i++){
        for(int j = 0; j <= i; j++){
            int a;
            cin >> a;
            S[i].push_back(a);
        }
    }

    vector<vector<int>> dp(n);
    for(int i = 0; i < n; i++){
        dp[i] = vector<int>(i + 1, 1);
    }
    
    dp[0][0] = S[0][0];

    for(int i = 1; i < n; i++){
        for(int j = 0; j <= i; j++){
            if (j == 0) {
                dp[i][j] = dp[i-1][j] * S[i][j];
            } else if (j == i) {
                dp[i][j] = dp[i-1][j-1] * S[i][j];
            } else {
                if(S[i][j] > 0){
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) * S[i][j];
                } else {
                    dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]) * S[i][j];
                }
            }
        }
    }
    
    cout << *max_element(dp[n-1].begin(), dp[n-1].end());

    return 0;
}

// Driver function
        for(int i = 0; i < V; i++){
            if(!vis[i]) {
                if(cycleBFS(i, vis, adj)) return true;
            }
        }



// cycle check fun by BFS
    bool cycleBFS(int src, vector<int> &vis, vector<int> adj[]){
        queue<pair<int,int>> q;
        vis[src] = 1;
        q.push({src,-1});
        
        while(!q.empty()){
            int node = q.front().first;
            int parent = q.front().second;
            q.pop();
            
            for(auto it: adj[node]){
                if(!vis[it]){
                    vis[it] = 1;
                    q.push({it, node});
                }
                else if(parent != it){
                    return true;
                }
            }
        }
        return false;
    }

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

#define MOD 1000000007
#define ll long long int
#define fr(i, a, b) for (int i = a; i < b; i++)

inline int binaryExponentiation(ll base, int exp, int mod = MOD) {
    ll result = 1;
    while (exp) {
        if (exp & 1) result = (result * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return (int)result;
}

void solve() {
    int n;
    cin >> n;
    ll answer = 0;
    fr(i, 1, n) {
        ll current = binaryExponentiation(2, n - i - 1);
        current = (2 * current * (n - i)) % MOD;
        current = (current * i) % MOD;
        current = (current * i) % MOD;
        answer = (answer + current) % MOD;
    }
    cout << answer << endl;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}

// check if a linked list is circular or not
bool isCircular (node* head) {
  if (head == NULL) {
    return true;
  }
  node* temp = head -> next;
  while (temp != NULL && temp != head) {
    temp = temp -> next;
  }
  if (temp == head) {
    return true;
  }
  return false;
}

node* kReverse (node* head, int k) {
  // base case
  if (head == NULL) {
    return NULL;
  }

  // step 1: reverse first k nodes
  node* forward = NULL;
  node* curr = head;
  node* prev = NULL;
  int cnt = 0;
  while (curr != NULL && cnt < k) {
    forward = curr -> next;
    curr -> next = prev;
    prev = curr;
    curr = forward;
    cnt++;
    
  }
  // step 2: recursion
  if (forward != NULL) {
    head -> next = kReverse(forward, k);
    
  }
  // step 3: return head of the modified list
  return prev;
}

int getLength (node* head) {
  int length = 0;
  node* temp = head;
  while (temp != NULL) {
    length++;
    temp = temp -> next;
  }
  return length;
}

node* middleNode (node* head) {
  int length = getLength(head);
  int mid = (length/2) + 1;
  int cnt = 1;
  node* temp = head;
  while (cnt < mid) {
    temp = temp -> next;
    cnt++;
  }
  return temp;
}

node* reverseLinkedList (node* & head) {
  //empty list or single node
  if (head == NULL || head -> next == NULL) {
    return head;
  }
  node* prev = NULL;
  node* curr = head;
  node* forword = NULL;
  while (curr != NULL) {
    forword = curr -> next;
    curr -> next = prev;
    prev = curr;
    curr = forword;
  }
  return prev;
}

// it will return the head of the reversed linked list
node* reverse1 (node* head) {
  // base case
  if (head == NULL || head -> next == NULL) {
    return head;
  }
  node* chotaHead = reverse1(head -> next) {
    head -> next -> next = head;
    head -> next = NULL;

    return chotaHead;
  }
}

node* reverseLinkedList (node* head) {
  // empty  list 
	if (head == NULL || head -> next == NULL) {
	return head;
	}
  node* prev = NULL;
  node* curr = head;
  node* forword = NULL;
  
  while (curr != NULL) {
	forword = curr -> next;
    curr -> next = prev;
    prev = curr;
    curr = forword;
  }
  return prev;
}

void deleteNode (node* &head, node* &tail, int position) {
  // delete first node
  if (position == 1) {
    node* temp = head;
    temp -> next -> prev = NULL;
    head = temp -> next;
    temp -> next = NULL;
    delete temp;
    return;
  }
  node* curr = head;
  node* back = NULL;
  int cnt = 1;
  while (cnt < position) {
    back = curr;
    curr = curr -> next;
    cnt++;
  }
  //delete last node 
  if (curr -> next == NULL) {
    tail = back;
    back -> next = NULL;
    curr -> prev = NULL;
    delete curr;
    return;
  }
  // delete in between node 
  back -> next = curr -> next;
  curr -> next -> prev = back;
  curr -> next = NULL;
  curr -> prev = NULL;
  delete curr;
}

void insertAtPosition(node *&head, node *&tail, int position, int d) {
  // insert at start
  if (position == 1) {
    insertAtHead(head, tail, d);
    return;
  }
  node *temp = new node(d);
  node *curr = head;
  int cnt = 1;
  while (cnt < position - 1) {
    curr = curr->next;
    cnt++;
  }
  // insert at last
  if (curr->next == NULL) {
    insertAtTail(tail, head, d);
    return;
  } else {
    temp->next = curr->next;
    curr->next = temp;
    temp->prev = curr;
    curr->next->prev = temp;
  }
}

void insertAtTail(node *&tail, node* &head, int d) {
  node *temp = new node(d);
  if (tail == NULL) {
    tail = head = temp;
  } else {
    tail->next = temp;
    temp->prev = tail;
    tail = temp;
  }
}

void insertAtHead(node *&head, node* & tail, int d) {
  node *temp = new node(d);
  if (head == NULL) {
    head = tail = temp;
  } else {
    head->prev = temp;
    temp->next = head;
    head = temp;
  }
}

int getLen(node *head) {
  int len = 0;
  node *temp = head;
  while (temp != NULL) {
    len++;
    temp = temp->next;
  }
  return len;
}

class node {
public:
  int data;
  node *next;
  node *prev;
  node(int d) {
    this->data = d;
    this->next = NULL;
    this->prev = NULL;
  }
  ~node() {
    int value = this -> data;
    if (next != NULL) {
      delete next;
      next = NULL;
    }
    cout << "memory free for node with data " << value << endl;
  }
};

void insertInPosition(node *&head, node *&tail, int d, int position) {
  if (position == 1) {
    insertAtHead(head, d);
    return;
  }

  node *temp = head;
  int count = 1;
  while (count < position - 1) {
    temp = temp->next;
    count++;
  }
  if (temp->next == NULL) {
    insertAtTail(tail, d);
    return;
  }

  node *nodeToInsert = new node(d);
  nodeToInsert->next = temp->next;
  temp->next = nodeToInsert;
}

void print (node* &head) {
  node* temp = head;
  while (temp != NULL) {
    cout << temp -> data << " ";
    temp = temp -> next;
  }
}

void insertAtTail(node *&tail, int d) {
  node *temp = new node(d);
  tail->next = temp;
  tail = temp;
}

void insertAtHead(node *&head, int d) {
  node *temp = new node(d);
  temp->next = head;
  head = temp;
}

void deleteNode(node *&head, int position) {
  if (position == 1) {
    node *temp = head;
    head = head->next;
    temp->next = NULL;
    delete temp;
  }

  else {
    node *curr = head;
    node *prev = NULL;
    int cnt = 1;
    while (cnt < position) {
      prev = curr;
      curr = curr->next;
      cnt++;
    }
    prev->next = curr->next;
    curr->next = NULL;
    delete curr;
  }
}

void merge(int *arr, int s, int e) {
  int mid = s + (e - s) / 2;
  int len1 = mid - s + 1;
  int len2 = e - mid;
  int *first = new int[len1];
  int *second = new int[len2];

  // copy vales
  int mainArrayIndex = s;
  for (int i = 0; i < len1; i++) {
    first[i] = arr[mainArrayIndex++];
  }
  mainArrayIndex = mid + 1;
  for (int i = 0; i < len2; i++) {
    second[i] = arr[mainArrayIndex++];
  }

  // merge 2 sorted arrays
  int index1 = 0;
  int index2 = 0;
  mainArrayIndex = s;
  while (index1 < len1 && index2 < len2) {
    if (first[index1] < second[index2]) {
      arr[mainArrayIndex++] = first[index1++];
    } else {
      arr[mainArrayIndex++] = second[index2++];
    }
  }
  while (index1 < len1) {
    arr[mainArrayIndex++] = first[index1++];
  }
  while (index2 < len2) {
    arr[mainArrayIndex++] = second[index2++];
  }
}

void mergeSort(int *arr, int s, int e) {
  if (s >= e) {
    return;
  }
  int mid = s + (e - s) / 2;
  // left  part
  mergeSort(arr, s, mid);
  // right part
  mergeSort(arr, mid + 1, e);
  // merge
  merge(arr, s, e);
}

bool checkPalindrome (string s, int start, int length) {
  if (start>length) {
    return true;
	}
  if (s[start] != s[length]) {
    return false;
	}
  else {
    return checkPalindrome(s,start+1,length-1;)
  }
}

bool isprime(int x){
    if(x<=1) return false;
    if(x==2 || x==3) return true;
    if(x%2==0 || x%3==0) return false;
    for(int i=5;i*i<=x;i+=6){
        if(x%i==0 || x%(i+2)==0) return false;
    }
    return true;
}

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

bool isSafe(int x, int y, int n, vector<vector<int>> visited,
            vector<vector<int>> &m) {
  if ((x >= 0 && x < n) && (y >= 0 && y < n) && visited[x][y] == 0 &&
      m[x][y] == 1) {
    return true;
  } else {
    return false;
  }
}

void solve(vector<vector<int>> &m, int n, vector<string> &ans, int x, int y,
           string path, vector<vector<int>> visited) {
  // you have reached x,y here

  // base case
  if (x == n - 1 && y == n - 1) {
    ans.push_back(path);
    return;
  }
  visited[x][y] = 1;

  // 4 choices D,L,R,U
  // down

  int newx = x + 1;
  int newy = y;
  if (isSafe(newx, newy, n, visited, m)) {
    path.push_back('D');
    solve(m, n, ans, newx, newy, path, visited);
    path.pop_back();
  }

  // left

  newx = x;
  newy = y - 1;
  if (isSafe(newx, newy, n, visited, m)) {
    path.push_back('L');
    solve(m, n, ans, newx, newy, path, visited);
    path.pop_back();
  }

  // right

  newx = x;
  newy = y + 1;
  if (isSafe(newx, newy, n, visited, m)) {
    path.push_back('R');
    solve(m, n, ans, newx, newy, path, visited);
    path.pop_back();
  }

  // up

  newx = x - 1;
  newy = y;
  if (isSafe(newx, newy, n, visited, m)) {
    path.push_back('U');
    solve(m, n, ans, newx, newy, path, visited);
    path.pop_back();
  }

  visited[x][y] = 0;
}

vector<string> findPath(vector<vector<int>> &m, int n) {
  vector<string> ans;
  if (m[0][0] == 0) {
    return ans;
  }
  int srcx = 0;
  int srcy = 0;

  vector<vector<int>> visited = m;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      visited[i][j] = 0;
    }
  }

  string path = "";
  solve(m, n, ans, srcx, srcy, path, visited);
  sort(ans.begin(), ans.end());
  return ans;
}

int main() {
  int n = 4;
  vector<vector<int>> m = {
      {1, 0, 0, 0}, {1, 1, 0, 1}, {1, 1, 0, 0}, {0, 1, 1, 1}};
  vector<string> ans = findPath(m, n);
  for (int i = 0; i < ans.size(); i++) {
    cout << ans[i] << " ";
  }
  cout << endl;
  return 0;
}

void sortArray (int *arr, int n) {
  if (n==0||n==1)
    return;
  for (int i=0; i<n-1; i++) {
    if (arr[i]>arr[i+1]) {
      swap(arr[i],arr[i+1]);
    }
  }
  sortArray(arr,n-1);
}

int power (int a, int b) {
  if (b==0)
    return 1;
  if (b==1)
    return a;
  int ans = power(a,b/2);
  if (b%2==0)
    return ans*ans;
  else
    return a*ans*ans;
}

bool binarySearch(int arr[], int s, int e, int key) {
  if (s > e)
    return false;
  int mid = s + (e - s) / 2;
  if (arr[mid] == key)
    return true;
  if (arr[mid] < key)
    return binarySearch(arr, mid + 1, e, key);
  else
    return binarySearch(arr, s, mid - 1, key);
}

bool linearsearch (int *arr, int size, int key) {
  if (size == 0)
    return false;
  if(arr[0]==key)
    return true;
  else 
    return linearsearch(arr+1, size-1, key);
}

bool isArraySorted (int arr[],int size) {
  if (size == 0 || size == 1) 
    return true;
  if (arr[0]>arr[1]) 
    return false;
  else {
    bool remainingPart = isArraySorted(arr+1,size-1); 
    return remainingPart;
  }
  
}

class Solution {
public:
    int fib(int n) {
        if (n==0)
        return 0;
        if (n==1)
        return 1;
        return fib(n-1)+fib(n-2);
        
    }
};

#include <iostream>
using namespace std;

void sayDigit (int n,string arr[]) {
  if (n==0) 
    return;
  if (n>0) {
    int digit = n%10;
    n = n/10;
    sayDigit(n,arr);
    cout << arr[digit] << " ";
  }
}

int main () {
  string arr[10] = {"zero","one","two","three","four","five","six","seven","eight","nine"};
  int n;
  cin >> n;
  sayDigit(n,arr);
  return 0;
}

vector<int> spiralPrint(vector<vector<int>> v, int r, int c) {
  vector<int> ans;
  int count = 0;
  ;
  int total = r * c;
  int startingRow = 0;
  int endingRow = r - 1;
  int startingCol = 0;
  int endingCol = c - 1;

  while (count < total) {
    // print starting row
    for (int i = startingCol; i <= endingCol && count < total; i++) {
      ans.push_back(v[startingRow][i]);
      count++;
    }
    startingRow++;
    // printing ending col
    for (int i = startingRow; i <= endingRow && count < total; i++) {
      ans.push_back(v[i][endingCol]);
      count++;
    }
    endingCol--;
    // printing ending row
    for (int i = endingCol; i >= startingCol && count < total; i--) {
      ans.push_back(v[endingRow][i]);
      count++;
    }
    endingRow--;
    // printing starting col
    for (int i = endingRow; i >= startingRow && count < total; i--) {
      ans.push_back(v[i][startingCol]);
      count++;
    }
    startingCol++;
  }

  return ans;
}

vector<int> wavePrint(vector<vector<int>> arr, int r, int c) {
  vector<int> ans;
  for (int col = 0; col < c; col++) {
    if (col & 1) {
      // odd index -> bottom to top
      for (int row = r - 1; row >= 0; row--) {
        cout << arr[row][col] << " ";
        ans.push_back(arr[row][col]);
      }
    }
    // 0 or even index -> top to bottom
    else {
      for (int row = 0; row < r; row++) {
        cout << arr[row][col] << " ";
        ans.push_back(arr[row][col]);
      }
    }
  }

  return ans;
}

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

string addInplaceOfSpaces (string &s) {
  string temp = "";
  for (int i = 0; i < s.length(); i ++) {
    if (s[i] == ' ') {
      temp.push_back('@');
      temp.push_back('2');
      temp.push_back('3');
    }
    else {
      temp.push_back(s[i]);
    }
  }
  return temp;
}

int main() {
  string s ="my name is vishnu deb jha" ;
  string v = addInplaceOfSpaces(s);
  cout << v << endl;
  return 0;
}
// output is my@23name@23is@23vishnu@23deb@23jha

char getMaxOccCharacter(string s) {
  int arr[26] = {0};
  for (int i = 0; i < s.length(); i++) {
    char ch = s[i];
    int number = 0;
    number = ch - 'a';
    arr[number]++;
  }
  int maxi = -1, ans = 0;
  for (int i = 0; i < 26; i++) {
    if (arr[i] > maxi) {
      maxi = arr[i];
      ans = i;
    }
  }
  return 'a' + ans;
}

 void dfs(int node, vector<int> adjLs[], int vis[]) {
        // mark the more as visited
        vis[node] = 1; 
        for(auto it: adjLs[node]) {
            if(!vis[it]) {
                dfs(it, adjLs, vis); 
            }
        }
    }

 vector<int> adjLs[V]; 
        
        // to change adjacency matrix to list 
        for(int i = 0;i<V;i++) {
            for(int j = 0;j<V;j++) {
                // self nodes are not considered
                if(adj[i][j] == 1 && i != j) {
                    adjLs[i].push_back(j); 
                    adjLs[j].push_back(i); 
                }
            }
        }

int f(int ind,int prev,vector<int>& nums,vector<vector<int>>& dp)
{
    if(ind<0)
    return 0;
    if(dp[ind][prev]!=-1)
    return dp[ind][prev];
    int nonpick,pick;
    nonpick = f(ind-1,prev,nums,dp);
    pick=0;
    if(nums[ind]<nums[prev])
    pick = 1+f(ind-1,ind,nums,dp);
    return dp[ind][prev] = max(pick,nonpick);
}
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        int p = n-1;
        vector<vector<int>>dp(n+1,vector<int>(n+1,-1));
        nums.push_back(INT_MAX);
        return f(n-1,n,nums,dp);
        
        
        
    }

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




class Solution
{
private:
    void dfs(int node, vector<int> &vis, vector<int> adj[],
             stack<int> &st) {
        vis[node] = 1;
        for (auto it : adj[node]) {
            if (!vis[it]) {
                dfs(it, vis, adj, st);
            }
        }

        st.push(node);
    }
private:
    void dfs3(int node, vector<int> &vis, vector<int> adjT[]) {
        vis[node] = 1;
        for (auto it : adjT[node]) {
            if (!vis[it]) {
                dfs3(it, vis, adjT);
            }
        }
    }
public:
    //Function to find number of strongly connected components in the graph.
    int kosaraju(int V, vector<int> adj[])
    {
        vector<int> vis(V, 0);
        stack<int> st;
        for (int i = 0; i < V; i++) {
            if (!vis[i]) {
                dfs(i, vis, adj, st);
            }
        }

        vector<int> adjT[V];
        for (int i = 0; i < V; i++) {
            vis[i] = 0;
            for (auto it : adj[i]) {
                // i -> it
                // it -> i
                adjT[it].push_back(i);
            }
        }
        int scc = 0;
        while (!st.empty()) {
            int node = st.top();
            st.pop();
            if (!vis[node]) {
                scc++;
                dfs3(node, vis, adjT);
            }
        }
        return scc;
    }
};

int main() {

    int n = 5;
    int edges[5][2] = {
        {1, 0}, {0, 2},
        {2, 1}, {0, 3},
        {3, 4}
    };
    vector<int> adj[n];
    for (int i = 0; i < n; i++) {
        adj[edges[i][0]].push_back(edges[i][1]);
    }
    Solution obj;
    int ans = obj.kosaraju(n, adj);
    cout << "The number of strongly connected components is: " << ans << endl;
    return 0;
}

void mergeArray(int arr1[], int n, int arr2[], int m, int arr3[]) {
  int i, j, k;
  i = j = k = 0;
  while (i < n && j < m) {
    if (arr1[i] < arr2[j]) {
      arr3[k] = arr1[i];
      k++;
      i++;
    } else {
      arr3[k] = arr2[j];
      k++;
      j++;
    }
  }
  while (i < n) {
    arr3[k] = arr1[i];
    i++;
    k++;
  }
  while (j < m) {
    arr3[k] = arr2[j];
    k++;
    j++;
  }
}

void reverseArray (int arr[],int n) {
  int start = 0;
  int end = n-1;
  while (start<=end) {
    swap (arr[start],arr[end]);
      start++;
    end--;
  }
}

//string s2 = reverse(s.begin(),s.end()); THIS IS WRONG
reverse(s.begin(),s.end());//THIS IS CORRECT

void sortArray(int arr[], int n) {
  for (int i = 1; i < n; i++) {
    for (int j = 0; j < (n - i); j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr[j], arr[j + 1]);
      }
    }
  }
}

#include <iostream>
using namespace std;

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

void sortArray (int arr[], int n) {
  for (int i = 0; i < (n-1); i ++) {
    for (int j = (i+1); j < n; j++) {
      if (arr[i] > arr[j]) {
        swap (arr[i], arr[j]);
      }
    }
  }
}

int main () {
  int n;
  cout << "Enter the size of the array: " << endl;
  cin >> n;
  int arr[n];
  cout << "Enter the elements of the array: " << endl;
  for (int i = 0; i < n; i++) {
    cin >> arr[i];
  }
  cout << "The array before sorting: " << endl;
  printArray (arr, n);
  sortArray (arr, n);
  cout << "the array after sorting :" << endl;
  printArray(arr,n);
  return 0;
}

#include <iostream>
using namespace std;

bool allocationIsPossible(int arr[], int n, int m, int mid) {
    int sum = 0;
    int studentCount = 1;
    for (int i = 0; i < n; i++) {
        if (sum + arr[i] <= mid) {
            sum += arr[i];
        } else {
            studentCount++;
            if (studentCount > m || arr[i] > mid) {
                return false;
            }
            sum = arr[i];
        }
    }
    return true;
}

int bookAllocate(int arr[], int n, int m) {
    int start = 0;
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += arr[i];
    }
    int end = sum;
    int mid = start + (end - start) / 2;
    int ans = -1;
    while (start <= end) {
        if (allocationIsPossible(arr, n, m, mid)) {
            ans = mid;
            end = mid - 1;
        } else {
            start = mid + 1;
        }
        mid = start + (end - start) / 2;
    }
    return ans;
}

int main() {
    int arr[4] = {10, 20, 30, 40};
    int ans = bookAllocate(arr, 4, 2);
    cout << "Minimum pages: " << ans << endl;
    return 0;
}
  

// output is 60

#include <iostream>
using namespace std;

bool allocationIsPossible(int arr[], int n, int m, int mid) {
    int sum = 0;
    int studentCount = 1;
    for (int i = 0; i < n; i++) {
        if (sum + arr[i] <= mid) {
            sum += arr[i];
        } else {
            studentCount++;
            if (studentCount > m || arr[i] > mid) {
                return false;
            }
            sum = arr[i];
        }
    }
    return true;
}

int bookAllocate(int arr[], int n, int m) {
    int start = 0;
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += arr[i];
    }
    int end = sum;
    int mid = start + (end - start) / 2;
    int ans = -1;
    while (start <= end) {
        if (allocationIsPossible(arr, n, m, mid)) {
            ans = mid;
            end = mid - 1;
        } else {
            start = mid + 1;
        }
        mid = start + (end - start) / 2;
    }
    return ans;
}

int main() {
    int arr[4] = {10, 20, 30, 40};
    int ans = bookAllocate(arr, 4, 2);
    cout << "Minimum pages: " << ans << endl;
    return 0;
}
  

// output is 60

#include <iostream>
#include <vector>
#include <algorithm>

class DisjointSet {
public:
    DisjointSet(int n) {
        rank.resize(n + 1, 0);
        parent.resize(n + 1);
        size.resize(n + 1, 1);
        for (int i = 0; i <= n; ++i) {
            parent[i] = i;
        }
    }

    int find_upar(int node) {
        if (node == parent[node]) {
            return node;
        }
        return parent[node] = find_upar(parent[node]);
    }

    void union_by_rank(int u, int v) {
        int ulp_u = find_upar(u);
        int ulp_v = find_upar(v);
        if (ulp_u == ulp_v) {
            return;
        }
        if (rank[ulp_u] < rank[ulp_v]) {
            parent[ulp_u] = ulp_v;
        } else if (rank[ulp_v] < rank[ulp_u]) {
            parent[ulp_v] = ulp_u;
        } else {
            parent[ulp_v] = ulp_u;
            rank[ulp_u]++;
        }
    }

    void union_by_size(int u, int v) {
        int ulp_u = find_upar(u);
        int ulp_v = find_upar(v);
        if (ulp_u == ulp_v) {
            return;
        }
        if (size[ulp_u] < size[ulp_v]) {
            parent[ulp_u] = ulp_v;
            size[ulp_v] += size[ulp_u];
        } else {
            parent[ulp_v] = ulp_u;
            size[ulp_u] += size[ulp_v];
        }
    }

private:
    std::vector<int> rank;
    std::vector<int> parent;
    std::vector<int> size;
};

class Solution {
public:
    int spanningTree(int V, std::vector<std::vector<std::pair<int, int>>>& adj) {
        std::vector<std::tuple<int, int, int>> edges;
        for (int i = 0; i < V; ++i) {
            for (auto& it : adj[i]) {
                int adjNode = it.first;
                int wt = it.second;
                int node = i;
                edges.push_back(std::make_tuple(wt, node, adjNode));
            }
        }

        DisjointSet ds(V);
        std::sort(edges.begin(), edges.end());

        int mstWt = 0;
        for (auto& edge : edges) {
            int wt = std::get<0>(edge);
            int u = std::get<1>(edge);
            int v = std::get<2>(edge);
            if (ds.find_upar(u) != ds.find_upar(v)) {
                mstWt += wt;
                ds.union_by_size(u, v);
            }
        }

        return mstWt;
    }
};

int main() {
    int V = 5;
    std::vector<std::vector<std::pair<int, int>>> adj(V);

    std::vector<std::vector<int>> edges = {
        {0, 1, 2}, {0, 2, 1}, {1, 2, 1}, {2, 3, 2}, {3, 4, 1}, {4, 2, 2}
    };

    for (auto& it : edges) {
        int u = it[0], v = it[1], wt = it[2];
        adj[u].emplace_back(v, wt);
        adj[v].emplace_back(u, wt);
    }

    Solution obj;
    int mstWt = obj.spanningTree(V, adj);
    std::cout << "The sum of all the edge weights: " << mstWt << std::endl;

    return 0;
}

#include <iostream>
#include <vector>

class DisjointSet {
public:
    DisjointSet(int n) {
        rank.resize(n + 1, 0);
        parent.resize(n + 1);
        size.resize(n + 1, 1);
        for (int i = 0; i <= n; ++i) {
            parent[i] = i;
        }
    }

    int find_upar(int node) {
        if (node == parent[node]) {
            return node;
        }
        return parent[node] = find_upar(parent[node]);
    }

    void union_by_rank(int u, int v) {
        int ulp_u = find_upar(u);
        int ulp_v = find_upar(v);
        if (ulp_u == ulp_v) {
            return;
        }
        if (rank[ulp_u] < rank[ulp_v]) {
            parent[ulp_u] = ulp_v;
        } else if (rank[ulp_v] < rank[ulp_u]) {
            parent[ulp_v] = ulp_u;
        } else {
            parent[ulp_v] = ulp_u;
            rank[ulp_u]++;
        }
    }

    void union_by_size(int u, int v) {
        int ulp_u = find_upar(u);
        int ulp_v = find_upar(v);
        if (ulp_u == ulp_v) {
            return;
        }
        if (size[ulp_u] < size[ulp_v]) {
            parent[ulp_u] = ulp_v;
            size[ulp_v] += size[ulp_u];
        } else {
            parent[ulp_v] = ulp_u;
            size[ulp_u] += size[ulp_v];
        }
    }

private:
    std::vector<int> rank;
    std::vector<int> parent;
    std::vector<int> size;
};

class Solution {
public:
    int Solve(int n, std::vector<std::vector<int>>& edge) {
        DisjointSet ds(n);
        int cnt_extras = 0;
        for (auto& e : edge) {
            int u = e[0];
            int v = e[1];
            if (ds.find_upar(u) == ds.find_upar(v)) {
                cnt_extras++;
            } else {
                ds.union_by_size(u, v);
            }
        }
        int cnt_c = 0;
        for (int i = 0; i < n; ++i) {
            if (ds.find_upar(i) == i) {
                cnt_c++;
            }
        }
        int ans = cnt_c - 1;
        if (cnt_extras >= ans) {
            return ans;
        }
        return -1;
    }
};

int main() {
    int V = 9;
    std::vector<std::vector<int>> edge = { {0, 1}, {0, 2}, {0, 3}, {1, 2}, {2, 3}, {4, 5}, {5, 6}, {7, 8} };

    Solution obj;
    int ans = obj.Solve(V, edge);
    std::cout << "The number of operations needed: " << ans << std::endl;

    return 0;
}

class Solution
{
	public:
	//Function to find sum of weights of edges of the Minimum Spanning Tree.
    int spanningTree(int V, vector<vector<int>> adj[])
    {
        // code here
        vector<int> vis(V,0);
        vector<tuple<int,int,int>> mst;
        //wt,node,parent
        priority_queue<vector<int>,vector<vector<int>>, greater<vector<int>>> pq;
        
        pq.push({0,0,-1});
        int sum =0;
        
        while(!pq.empty()){
            auto it = pq.top();
            pq.pop();
            int node = it[1];
            int wt = it[0];
            int par = it[2];
            
            if(vis[node]==1) continue;
            vis[node]=1;
            sum+=wt;
            if(par!=-1){
                mst.push_back(make_tuple(wt,par,node));
            }
            for(auto it: adj[node]){
                int ch = it[0];
                int ch_w = it[1];
                if(!vis[ch]){
                    pq.push({ch_w, ch,node});
                }
            }
        }
        for(auto it: mst){
            int weight, u, v;
            tie(weight, u, v) = it;
            cout<<weight<<":"<<u<<"->"<<v<<endl;
        }
        return sum;
    }
};

class Solution {
  public:
    /*  Function to implement Bellman Ford
    *   edges: vector of vectors which represents the graph
    *   S: source vertex to start traversing graph with
    *   V: number of vertices
    */
    vector<int> bellman_ford(int V, vector<vector<int>>& edges, int S) {
        // Code here
        //iterate through edges ond keep on updating the distance array. Iterate through all the edges for 
        //V-1 times
        vector<int> dis(V,1e8);
        dis[S]=0;
        for(int i=0;i<V-1;i++){
            
            for(int j =0;j<edges.size();j++){
                int u = edges[j][0];
                int v = edges[j][1];
                int w = edges[j][2];
                if(dis[u] != 1e8 && dis[u]+w<dis[v]){
                    dis[v]=dis[u]+w;
                }
            }
        }
        for(int i=0;i<1;i++){
            
            for(int j =0;j<edges.size();j++){
                int u = edges[j][0];
                int v = edges[j][1];
                int w = edges[j][2];
                if(dis[u] != 1e8 && dis[u]+w<dis[v]){
                    return {-1};
                }
            }
        }
        
        return dis;
    }
};

int f(int ind,int buy, vector<int>& nums ,vector<vector<int>>& dp )
{
    if(ind==(nums.size()))
    return 0;
    if(dp[ind][buy]!=-1)
    return dp[ind][buy];
    int profit;
    if(buy)
    profit = max((-nums[ind]+f(ind+1,0,nums,dp)),(f(ind+1,1,nums,dp)));
    else
    profit = max((nums[ind]+f(ind+2,1,nums,dp)),(f(ind+1,0,nums,dp)));
    return dp[ind][buy]=profit;
}
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
         vector<vector<int>> dp(n,vector<int>(2,-1));
         return f(0,1,prices,dp);
        
    }

class Solution
{
	public:
	//Function to find sum of weights of edges of the Minimum Spanning Tree.
    int spanningTree(int V, vector<vector<int>> adj[])
    {
        // code here
        vector<int> vis(V,0);
        vector<tuple<int,int,int>> mst;
        //wt,node,parent
        priority_queue<vector<int>,vector<vector<int>>, greater<vector<int>>> pq;
        
        pq.push({0,0,-1});
        int sum =0;
        
        while(!pq.empty()){
            auto it = pq.top();
            pq.pop();
            int node = it[1];
            int wt = it[0];
            int par = it[2];
            
            if(vis[node]==1) continue;
            vis[node]=1;
            sum+=wt;
            if(par!=-1){
                mst.push_back(make_tuple(wt,par,node));
            }
            for(auto it: adj[node]){
                int ch = it[0];
                int ch_w = it[1];
                if(!vis[ch]){
                    pq.push({ch_w, ch,node});
                }
            }
        }
        for(auto it: mst){
            int weight, u, v;
            tie(weight, u, v) = it;
            cout<<weight<<":"<<u<<"->"<<v<<endl;
        }
        return sum;
    }
};

int f(int ind,int buy,int t, vector<int>& nums, vector<vector<vector<int>>>& dp)
{
    if(ind==(nums.size()) || t==0)
    return 0;
    if(dp[ind][buy][t]!=-1)
    return dp[ind][buy][t];
    int profit;
    if(buy && t)
    profit = max((-nums[ind]+f(ind+1,0,t,nums,dp)),(f(ind+1,1,t,nums,dp)));
    else
    profit = max((nums[ind]+f(ind+1,1,t-1,nums,dp)),(f(ind+1,0,t,nums,dp)));
    return dp[ind][buy][t]=profit;
}
    int maxProfit(vector<int>& prices) {
         int n = prices.size();
     vector<vector<vector<int>>> dp(n, vector<vector<int>>(2, vector<int>(3, -1)));


         return f(0,1,2,prices,dp);
        
    }

int f(int ind,int buy, vector<int>& nums ,vector<vector<int>>& dp )
{
    if(ind==(nums.size()))
    return 0;
    if(dp[ind][buy]!=-1)
    return dp[ind][buy];
    int profit;
    if(buy)
    profit = max((-nums[ind]+f(ind+1,0,nums,dp)),(f(ind+1,1,nums,dp)));
    else
    profit = max((nums[ind]+f(ind+1,1,nums,dp)),(f(ind+1,0,nums,dp)));
    return dp[ind][buy]=profit;
}
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
         vector<vector<int>> dp(n,vector<int>(2,-1));
         return f(0,1,prices,dp);
        
    }

#include <iostream>
using namespace std;
int sqrt(int arr[], int n, int key) {
  int start = 0;
  int end = n - 1;
  int mid = start + (end - start) / 2;
  int ans = -1;
  while (start <= end) {
    int square = mid * mid;
    if (square == key) {
      return mid;
    } else if (square > key) {
      end = mid - 1;
    } else {
      start = mid + 1;
      ans = mid;
    }
    mid = start + (end - start) / 2;
  }
  return ans;
}
double precision(int n, int precision, int integer) {
  double factor = 1;
  double ans = integer;
  for (int i = 0; i < precision; i++) {
    factor = factor / 10;
    for (double j = ans; j * j < n; j += factor) {
      ans = j;
    }
  }
  return ans;
}
int main() {
  int n;
  cout << "enter the number :" << endl;
  cin >> n;
  int arr[n];
  for (int i = 0; i < n; i++) {
    arr[i] = (i + 1);
  }
  int squareRoot = sqrt(arr, n, n);
  double finalAns = precision(n, 3, squareRoot);
  cout << "square root of " << n << " is " << finalAns << endl;
  return 0;
}

#include <iostream>
using namespace std;
long long int binarySearch(int arr[],int n,int key) {
  int start = 0;
  int end = n-1;
  long long int mid = start + (end-start)/2;
  long long int ans = -1;
while (start <= end){
  long long int square = mid*mid;
  if (square == key) {
    return mid;
  }
  else if (square > key) {
    end = mid - 1;
  }
  else {
    start = mid + 1;
    ans = mid;
  }
  mid = start + (end-start)/2;
}
  return ans;
}
int main() {
  int n;
  cout << "enter the number :" << endl;
  cin >> n;
  int arr[n];
  for (int i = 0; i < n; i++) {
     arr[i] = (i+1);
  }
  int squareRoot = binarySearch(arr,n,n);
  cout << "square root of " << n << " is " << squareRoot << endl;
  return 0;
}

class Solution {
  public:
    /*  Function to implement Bellman Ford
    *   edges: vector of vectors which represents the graph
    *   S: source vertex to start traversing graph with
    *   V: number of vertices
    */
    vector<int> bellman_ford(int V, vector<vector<int>>& edges, int S) {
        // Code here
        //iterate through edges ond keep on updating the distance array. Iterate through all the edges for 
        //V-1 times
        vector<int> dis(V,1e8);
        dis[S]=0;
        for(int i=0;i<V-1;i++){
            
            for(int j =0;j<edges.size();j++){
                int u = edges[j][0];
                int v = edges[j][1];
                int w = edges[j][2];
                if(dis[u] != 1e8 && dis[u]+w<dis[v]){
                    dis[v]=dis[u]+w;
                }
            }
        }
        for(int i=0;i<1;i++){
            
            for(int j =0;j<edges.size();j++){
                int u = edges[j][0];
                int v = edges[j][1];
                int w = edges[j][2];
                if(dis[u] != 1e8 && dis[u]+w<dis[v]){
                    return {-1};
                }
            }
        }
        
        return dis;
    }
};

#include <iostream>
using namespace std;
int pivotSearch (int arr[],int n) {
  int start = 0;
  int end = n-1;
  int mid = start + (end-start)/2;
  while (start < end) {
    if (arr[mid] >= arr[0]) {
      start = mid + 1;
    }
    else {
      end = mid;
    }
    mid = start + (end-start)/2;
  }
  return end;
}
int binarySearch(int arr[],int n,int s,int e,int key) {
  int start = s;
  int end = e;
  int mid = start + (end-start)/2;
while (start <= end){
  if (arr[mid] == key) {
    return mid;
  }
  else if (arr[mid] > key) {
    end = mid - 1;
  }
  else {
    start = mid + 1;
  }
  mid = start + (end-start)/2;
}
  return -1;
}
int main() {
  int arr[6] = {3,8,10,0,1,2};
  int ans = pivotSearch(arr,6);
  cout << "the pivot is at : "<< ans << endl;
  if (2>=arr[ans]&&2<=arr[5]) {
    cout << "the element is present in the array at index     :" << binarySearch(arr,6,ans,5,2); 
  }
  else {
    cout << "the element is present in the array at index     :" << binarySearch(arr,6,0,ans-1,2);
  }
  return 0;
}

#include <iostream>
using namespace std;
int pivotSearch (int arr[],int n) {
  int start = 0;
  int end = n-1;
  int mid = start + (end-start)/2;
  while (start < end) {
    if (arr[mid] >= arr[0]) {
      start = mid + 1;
    }
    else {
      end = mid;
    }
    mid = start + (end-start)/2;
  }
  return end;
}
int main() {
  int arr[5] = {3,8,10,17,1};
  int ans = pivotSearch(arr,5);
  cout << "the pivot is : "<< ans;
  return 0;
}

#include <iostream>
using namespace std;
int firstOcc(int arr[], int n, int key) {
  int start = 0;
  int end = n-1;
  int ans = -1;
  int mid = start + (end-start)/2;
  while (start <= end) {
    if (arr[mid] == key) {
      ans = mid;
      end = mid - 1;
    }
    else if (arr[mid] < key) {
      start = mid + 1;
    }
    else {
      end = mid - 1;
    } 
    mid = start + (end-start)/2;
  }
  return ans;
}
int lastOcc(int arr[], int n, int key) {
  int start = 0;
  int end = n-1;
  int ans = -1;
  int mid = start + (end-start)/2;
  while (start <= end) {
    if (arr[mid] == key) {
      ans = mid;
      start = mid + 1;
    }
    else if (arr[mid] < key) {
      start = mid + 1;
    }
    else {
      end = mid - 1;
    } 
    mid = start + (end-start)/2;
  }
  return ans;
}
int main() {
  int array[6] = {1,2,2,2,2,3};
  int first = firstOcc(array,6,2);
  cout << "first occurance of 2 is at index " << first << endl;
  int last = lastOcc(array,6,2);
  cout << "last occurance of 2 is at index " << last << endl;
  return 0;
}

void getNumberPattern(int n) {
    // Write your code here.
    for(int i=0;i<2*n-1;i++){
        for(int j=0;j<2*n-1;j++){
            int top=i;
            int left=j;
            int bottom=(2*n-2)-i;
            int right=(2*n-2)-j;
            cout<<n-min(min(top,left),min(right,bottom));
        }
        cout<<"\n";
    }
}

  int f(int ind,vector<int>& nums,vector<int>& dp)
  {
      int one,two=INT_MAX;
      if(ind==0)return 0;
      if(dp[ind]!=-1)
      return dp[ind];
       one = f(ind-1,nums,dp)+abs(nums[ind]-nums[ind-1]);
      if(ind>1)
       two = f(ind-2,nums,dp)+abs(nums[ind]-nums[ind-2]);
      return dp[ind]=min(one,two);
  }
    int minimumEnergy(vector<int>& height, int n) {
        // Code here
        vector<int> dp(n,-1);
        return f(n-1,height,dp);
    }

 int f(int ind,int wt, int w[],int v[],vector<vector<int>>& dp)
    {
        if(ind==0)
        {
            return (w[0]<=wt)?v[0]:0;
        }
        int pick,nonpick;
        if(dp[ind][wt]!=-1)
        return dp[ind][wt];
        nonpick = f(ind-1,wt,w,v,dp);
        pick = INT_MIN;
        if(wt>=w[ind])
        pick = v[ind] + f(ind-1,wt-w[ind],w,v,dp);
        
        return dp[ind][wt] = max(pick,nonpick);
    }
    int knapSack(int W, int wt[], int val[], int n) 
    { 
       // Your code here
       vector<vector<int>> dp(n + 1, vector<int>(W + 1, -1));
       return f(n-1,W,wt,val,dp);
    }

   int f(int ind,int target,vector<int>& a,vector<vector<int>>& dp)
   {
    int pick,nonPick;
      
      if(ind==0)
      {
        if(target%a[0]==0)
        return 1;
        else return 0;
      }
      if(dp[ind][target]!=-1)return dp[ind][target];
       nonPick = f(ind-1,target,a,dp);
       pick=0;
      if(a[ind]<=target)
        pick = f(ind,target-a[ind],a,dp);
      return dp[ind][target]=(pick+nonPick);
   }
    int change(int amount,vector<int>& coins) {
        int n = coins.size();
        vector<vector<int>> dp(n,vector<int>(amount+1,-1));
        return f(n-1,amount,coins,dp);
        
        
    }

   int f(int ind,int target,vector<int>& a,vector<vector<int>>& dp)
   {
    int pick,nonPick;
      
      if(ind==0)
      {
        if(target%a[0]==0)return target/a[0];
        else return INT_MAX;
      }
      if(dp[ind][target]!=-1)return dp[ind][target];
       nonPick = f(ind-1,target,a,dp);
       pick = 1e9;
      if(a[ind]<=target)
        pick = 1+f(ind,target-a[ind],a,dp);
      return dp[ind][target]=min(pick,nonPick);
   }
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        vector<vector<int>> dp(n,vector<int>(amount+1,-1));
        int res =f(n-1,amount,coins,dp);
        return (res>=1e9)?-1:res;
        
    }

int gcd(int a,int b){
  if(a==0 || b==0) return (a+b);
  else if(a>=b) return gcd(a-b,b);
  else return gcd(a,b-a);
}

//{ Driver Code Starts
#include <bits/stdc++.h> 
using namespace std; 

// } Driver Code Ends

class Solution
{   
    public:
    //Function to rotate matrix anticlockwise by 90 degrees.
    void rotateby90(vector<vector<int> >& matrix, int n) 
    { 
        for(int i=0;i<n;i++){
            reverse(matrix[i].begin(),matrix[i].end());
        }
        for(int i=0;i<n;i++){
            for(int j=i;j<n;j++){
                swap(matrix[i][j],matrix[j][i]);
            }
        }
    } 
};


//{ Driver Code Starts.
int main() {
    int t;
    cin>>t;
    
    while(t--) 
    {
        int n;
        cin>>n;
        vector<vector<int> > matrix(n); 

        for(int i=0; i<n; i++)
        {
            matrix[i].assign(n, 0);
            for( int j=0; j<n; j++)
            {
                cin>>matrix[i][j];
            }
        }

        Solution ob;
        ob.rotateby90(matrix, n);
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                cout<<matrix[i][j]<<" ";
        cout<<endl;
    }
    return 0;
}
// } Driver Code Ends

bool f(int ind,int target,vector<int>& nums,vector<vector<int>>& dp)
  {
      if(dp[ind][target]!=-1)
      return dp[ind][target];
      if(target==0)return true;
      if(ind==0)return (nums[0]==target);
      bool nottake = f(ind-1,target,nums,dp);
      bool take=false;
      if(target>=nums[ind])
       take = f(ind-1,target-nums[ind],nums,dp);
      return dp[ind][target]=(take || nottake);
  }
    bool isSubsetSum(vector<int>arr, int sum){
        // code here
        
        int n = arr.size();
        vector<vector<int>> dp(n,vector<int>(sum+1,-1));
        return f(n-1,sum,arr,dp);
    }

//{ Driver Code Starts
// Initial Template for C++

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

// } Driver Code Ends
// User function Template for C++

class Solution {
  public:
    vector<vector<int>> sortedMatrix(int N, vector<vector<int>> Mat) {
        // code here
        vector<int> v;
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                v.push_back(Mat[i][j]);
            }
        }
        sort(v.begin(),v.end());
        vector<vector<int>> sorted(N);
        for(int i=0;i<v.size();i++){
            sorted[i/N].push_back(v[i]);
        }
        return sorted;
    }
};

//{ Driver Code Starts.

int main() {
    int t;
    cin >> t;
    while (t--) {
        int N;
        cin >> N;
        vector<vector<int>> v(N, vector<int>(N));
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++) cin >> v[i][j];
        Solution ob;
        v = ob.sortedMatrix(N, v);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) cout << v[i][j] << " ";
            cout << "\n";
        }
    }
}
// } Driver Code Ends

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int s=0,e=(matrix.size()*matrix[0].size())-1;
        while(s<=e){
            int n=matrix[0].size();
            int mid=s+(e-s)/2;
            int i=mid/n;
            int j=(mid%n);
            if(matrix[i][j]==target){
                return true;
            }
            else if( matrix[i][j]<target) s=mid+1;
            else e=mid-1;
        }
        return false;
    }
};

//{ Driver Code Starts
#include <bits/stdc++.h> 
using namespace std; 

// } Driver Code Ends
class Solution
{   
    public: 
    //Function to return a list of integers denoting spiral traversal of matrix.
    vector<int> spirallyTraverse(vector<vector<int> > matrix, int r, int c) 
    {   
        vector<int> v;
        int startrow=0;
        int endrow=r-1;
        int startcol=0;
        int endcol=c-1;
        while(startrow<=endrow && startcol<=endcol){
            for(int i=startcol;i<=endcol && startrow<=endrow && startcol<=endcol;i++){
                v.push_back(matrix[startrow][i]);
            }
            startrow++;
            for(int i=startrow;i<=endrow && startrow<=endrow && startcol<=endcol;i++){
                v.push_back(matrix[i][endcol]);
            }
            endcol--;
            for(int i=endcol;i>=startcol && startrow<=endrow && startcol<=endcol;i--){
                v.push_back(matrix[endrow][i]);
            }
            endrow--;
            for(int i=endrow;i>=startrow && startrow<=endrow && startcol<=endcol;i--){
                v.push_back(matrix[i][startcol]);
            }
            startcol++;
        }
        return v;
        
    }
};

//{ Driver Code Starts.
int main() {
    int t;
    cin>>t;
    
    while(t--) 
    {
        int r,c;
        cin>>r>>c;
        vector<vector<int> > matrix(r); 

        for(int i=0; i<r; i++)
        {
            matrix[i].assign(c, 0);
            for( int j=0; j<c; j++)
            {
                cin>>matrix[i][j];
            }
        }

        Solution ob;
        vector<int> result = ob.spirallyTraverse(matrix, r, c);
        for (int i = 0; i < result.size(); ++i)
                cout<<result[i]<<" ";
        cout<<endl;
    }
    return 0;
}
// } Driver Code Ends

//{ Driver Code Starts
#include <bits/stdc++.h>
using namespace std;

// } Driver Code Ends
//User function template for C++
class Solution{
public:
    
    int onesinrow(vector<vector<int>> &arr, int i){
        int lower = lower_bound(arr[i].begin(), arr[i].end(), 1) - arr[i].begin();
        return arr[i].size() - lower;
    }

    int rowWithMax1s(vector<vector<int>> &arr, int n, int m) {
        int ans = 0;
        int ind = -1;
        for(int i = 0; i < n; i++){
            int ones = onesinrow(arr, i);
            if(ones > ans){
                ans = ones;
                ind = i;
            }
        }
        return ind;
    }
};

//{ Driver Code Starts.
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        vector< vector<int> > arr(n,vector<int>(m));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cin>>arr[i][j];
            }
        }
        Solution ob;
        auto ans = ob.rowWithMax1s(arr, n, m);
        cout << ans << "\n";
    }
    return 0;
}

// } Driver Code Ends

    int orangesRotting(vector<vector<int>>& grid) {
        int n= grid.size();
        int t;
        int m = grid[0].size();
        int vis[n][m];
        queue<pair<pair<int,int>,int>> q;
        for(int i=0;i<n;++i)
        {
            for(int j=0;j<m;++j)
            {
                if(grid[i][j]==2){
                q.push({{i,j},0});
                vis[i][j]=2;}
                else
                    vis[i][j]=0;
            }
        }
        int tm=0;
            while(!q.empty())
            {
                int r = q.front().first.first;
                int c = q.front().first.second;
                 t = q.front().second;
                 tm = max(t,tm);
                q.pop();
                int drow[] = {0,1,-1,0};
                int dcol[] = {1,0,0,-1};
                for(int i=0;i<4;++i)
                {
                    int nr = r+drow[i];
                    int nc = c+dcol[i];
                    if(nr>=0 && nr<n && nc>=0 && nc<m && vis[nr][nc]!=2 && grid[nr][nc]==1)
                    {
                        q.push({{nr,nc},t+1});
                        vis[nr][nc]=2;
                    }
                    
                }
            }
        
        for(int i=0;i<n;++i)
        {
            for(int j=0;j<m;++j)
            {
                if(grid[i][j]==1 && vis[i][j]!=2)
                return -1; 
            }

        }

        return tm;
    }

 vector<int> bfsOfGraph(int v,vector<int> adj[])
{
  vector<int> vis(v+1,0);
  vis[0]=1;
  queue<int> q;
  q.push(0);
  vector<int> bfs;
  while(!q.empty())
    {
      int node = q.front();
      bfs.push_back(node);
      q.pop();
      vis[node]=1;
      for(auto x:adj[node])
        {
          if(!vis[x]){
            q.push(x);
              vis[x]=1;
          }
        }
    }
    return bfs;
}

#include <iostream>
using namespace std;

int main() {
    float a, b, c;

    for (int i = 1; i < 30; ++i) {
        cout << "Digite as notas: " << endl;
        cin >> a >> b >> c;
       cout << "Media do aluno e de: "<< (a + b + c)/3 << endl;
    }

    return 0;
}

#include <iostream>
#include <string>
using namespace std;
int main(){
  string meses[12] = {"Janeiro", "Fevereiro", "Marco", "Abril", "Maio", "Junho", "Julho", "Agosto", "Setembro", "Outubro", "Novembro", "Dezembro"};
  int numero;
  cin >> numero;
  if (numero >= 1 && numero <= 12){
    cout << meses[numero -1] << endl;
  } else {
    cout << "Numero invalido" << endl;
  }
}

class Solution {
public:
  
   
  int f(int ind, vector<int> &nums, vector<int> &dp) {
    if(ind == 0) return nums[ind];
    if(ind < 0) return 0;
    if(dp[ind] != -1) return dp[ind];
    int pick = nums[ind] + f(ind - 2, nums, dp);
    int notPick = 0 + f(ind - 1, nums, dp);
    return dp[ind] = max(pick, notPick);
}
    int rob(vector<int>& nums) {
        int n=nums.size();
        vector<int> dp(nums.size()+2,-1);
         int a = f(n-1,nums,dp);
         return a;
        
    }
};

vector<int> pf(int n)
{
    vector<int> v;
    for(int i=2;i<=n;++i)
    {
        while(n%i==0)
        {
            v.push_back(i);
            n/=i;
        }
    }
    return v;
}

int main() {
    std::vector<int> vec = {1, 2, 2, 3, 4, 4, 5};

    // Sort the vector
    std::sort(vec.begin(), vec.end());

    // Use unique to remove duplicates
    auto last = std::unique(vec.begin(), vec.end());

    // Erase the unused elements
    vec.erase(last, vec.end());

    // Print the result
    for(int n : vec) {
        std::cout << n << " ";
    }

    return 0;
}

 vector<vector<int>> v;

    void f(int i, int tar, vector<int>& nums, vector<int>& can) {
        if ( tar == 0) {
            v.push_back(nums);
            return;
        }
        if (i == can.size() || tar < 0)
            return;
     

        nums.push_back(can[i]);
        f(i, tar - can[i], nums, can);
        nums.pop_back();

        f(i + 1, tar, nums, can);
        
    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<int> ds;
        f(0, target, ds, candidates);
        return v;
    }

vector<vector<int>> subset;
 
  void gen(vector<int>& nums,int i,vector<int> sub)
  {
     if(i==nums.size())
        {
            subset.push_back(sub);
            return;
        }
        gen(nums,i+1,sub);

        sub.push_back(nums[i]);
        gen(nums,i+1,sub);

        
  }

vector<string> valid;
  void generate(string& s , int open,int close)
  {
    
    if(open==0 && close==0)
    {
        valid.push_back(s);
        return;
    }
    if(open>0)
    {
        s.push_back('(');
        generate(s,open-1,close);
        s.pop_back();
    }
    if(close>0 && open<close)
    {
        s.push_back(')');
        generate(s,open,close-1);
        s.pop_back();
    }
  }

#include<bits/stdc++.h>
using namespace std;
int sum=0;
vector<int> rev(vector<int>& nums,int f,int r)
{
    if(f<=r)
    {
        swap(nums[f],nums[r]);
        rev(nums,f+1,r-1);
    }
    return nums;
}
int main()
{

    vector<int> v = {4,5,2,6,3,56,5};
    rev(v,0,6);
    for(int i=0;i<=6;++i)
    cout<<v[i]<<" ";
    
}

void f(int n)
{
    n--;
    if(n)
    f(n);
    cout<<"AYUSH"<<endl;
}

void f(int n)
{
    if(n)
    f(n-1);
    cout<<"AYUSH"<<endl;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3+5;
vector<int> graph[N];
bool visited[N];
void dfs(int vertex)
{
  visited[vertex]=true;
  for(int child:graph[vertex])
    {
      
      if(visited[child])
        continue;
      dfs(child);
    }
}
int main()
{
    int v,e,j,k;
    cin>>v>>e;
    for(int i=0;i<v;++i)
    {
        cin>>j>>k;
        graph[k].push_back(j);
        graph[j].push_back(k);
        
    }
}

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3+5;
vector<int> graph[N];
int main()
{
    int v,e,j,k;
    cin>>v>>e;
    for(int i=0;i<v;++i)
    {
        cin>>j>>k;
        graph[k].push_back(j);
        graph[j].push_back(k);
        
    }
}

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3+5;
int graph[N][N];
int main()
{
    int v,e,j,k;
    cin>>v>>e;
    for(int i=0;i<e;++i)
    {
        cin>>j>>k;
        graph[i][j]=1;
        graph[j][i]=1;
        
    }
}

vector<int> Primrlist()
{
    isPrime[0]=isPrime[1]=false;
    for(int i=0;i<N;++i)
    {
        if(isPrime[i]==true)
        {
            for(int j=2*i;j<=N;j+=i)
            isPrime[j]=0;
        }
    }
    return isPrime;
}

vector<int> bin(int num) 
{
    vector<int> binaryNum;
    if (num == 0) {
        binaryNum.push_back(0);
        return binaryNum;
    }
     while (num > 0) {
        binaryNum.push_back(num % 2);
        num = num / 2;
    }
    reverse(binaryNum.begin(), binaryNum.end());
    return binaryNum;
}

//Source.ccp

//Setup SDL
bool InitSDL() {
	//If failed to Initialize
	if (SDL_Init(SDL_INIT_VIDEO) < 0) {
		cout << "Failed to Init SDL. Error: " << SDL_GetError() << "\n";
		return false;
	}

	//If Sucesss
	else {
		//Create Window
		gWindow = SDL_CreateWindow("MarioBrosClone", SDL_WINDOWPOS_UNDEFINED, SDL_WINDOWPOS_UNDEFINED, SCREEN_WIDTH, SCREEN_HEIGHT, SDL_WINDOW_SHOWN); 
		
		//Create renderer
		gRenderer = SDL_CreateRenderer(gWindow, -1, SDL_RENDERER_ACCELERATED);

		//Check if Window is null
		if (gWindow == NULL) {
			cout << "Failed to create Window, Error: " << SDL_GetError() << "\n";
			return false;
		}

		//Check if renderer is null;
		if (gRenderer == NULL) {
			cout << "Failed to create Renderer, Error " << SDL_GetError() << "\n";
			return false;
		}

		//Set Texture
		else {
			int imageFlags = IMG_INIT_PNG;

			if (!(IMG_Init(imageFlags)) && imageFlags) {
				cout << "Failed to load SDL_Image, Error " << SDL_GetError() << "\n";
				return false;
			}
		}

		//Create Mixer
		if (Mix_OpenAudio(44100, MIX_DEFAULT_FORMAT, 2, 2048) < 0) {
			cout << "Mixer could not initialise. Error: " << Mix_GetError();
			return false;
		}

		if (TTF_Init() < 0) {
			cout << "Error: " << TTF_GetError() << endl;
			return false;
		}
	}

	return true;
}

//Close SDL
void CloseSDL() {
	SDL_DestroyWindow(gWindow);
	gWindow = NULL;

	IMG_Quit();
	SDL_Quit();

	SDL_DestroyRenderer(gRenderer);
	gRenderer = NULL;

	delete gTexture;
	gTexture = NULL;

	delete gameScreenManager;
	gameScreenManager = NULL;
}

//Render 
void Render() {
	//Clear Screen
	SDL_SetRenderDrawColor(gRenderer, 0x00, 0x00, 0x00, 0x00);
	SDL_RenderClear(gRenderer);
	
	//Render Texture to Screen
	gameScreenManager->Render();

	//Update Screen
	SDL_RenderPresent(gRenderer);
}

//GameScreenLevel1.cpp
void GameScreenLevel1::SetLevelMap() {
	//0 blank, 1 wall, 2 win condition
	int map[MAP_HEIGHT][MAP_WIDTH] = {
		{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
		{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
		{1,1,1,1,1,1,0,0,0,0,1,1,1,1,1,1},
		{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
		{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
		{0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0},
		{1,1,0,0,0,0,0,0,0,0,0,0,0,0,1,1},
		{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
		{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
		{1,1,1,1,1,1,0,0,0,0,1,1,1,1,1,1},
		{0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0},
		{0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0},
		{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}
	};

	//Clear up any old map
	if (mLevelMap != NULL)
	{
		delete mLevelMap;

	}

	//Set up the new one
	mLevelMap = new LevelMap(map);
}


//Collision.cpp
bool Collision::Circle(Character* character1, Character* character2) {
	//Calculate Vector between 2 characters
	Vector2D vec = Vector2D((character1->GetPosition().x - character2->GetPosition().x), (character1->GetPosition().y - character2->GetPosition().y));

	//Calculate lenght from vector
	double distance = sqrt((vec.x * vec.x) + (vec.y * vec.y));

	//Get Collision Radius 
	double combinedDistance = (character1->GetCollisionRadius() - character2->GetCollisionRadius());

	if (distance < combinedDistance) {
		return true;
	}
	else return false;
}

bool Collision::Box(Rect2D rect1, Rect2D rect2) {
	if (rect1.x + (rect1.width / 2) > rect2.x && rect1.x + (rect1.width / 2) < rect2.x + rect2.width && rect1.y + (rect1.height / 2) > rect2.y && rect1.y + (rect1.height / 2) < rect2.y + rect2.height) {
		return true;
	}
	return false;
}

 ListNode *hasCycle(ListNode *head) {
        ListNode *slow=head;
        ListNode *fast=head;
      while(fast!=NULL && fast->next!=NULL)
      {
        slow=slow->next;
        fast=fast->next->next;
        if(fast==slow)
        return slow;
      }
     return NULL;
    }
    ListNode *detectCycle(ListNode *head) {
         ListNode *t1=hasCycle(head);
         if(t1==NULL)return NULL;
        ListNode *t=head;
       

        while(t!=t1)
        {
            t=t->next;
            t1=t1->next;
        }
        return t;
        
    }

bool hasCycle(ListNode *head) {
        ListNode *slow=head;
        ListNode *fast=head;
      while(fast!=NULL && fast->next!=NULL)
      {
        slow=slow->next;
        fast=fast->next->next;
        if(fast==slow)
        return true;
      }
      return false;
    }

 bool hasCycle(ListNode *head) {
        ListNode* temp = head;
        unordered_map<ListNode*,int> m;
         while(temp != NULL) {
            m[temp]++;
            if(m[temp] == 2) {
                return true;
            }
            temp = temp->next;
        }

        return false;
    }

int maxSubArray(vector<int>& nums)
{
    int sum=0;
    int maxi = INT_MIN;
    for(int i=0;i<nums.size();++i)
    {   sum+=nums[i];
        maxi = max(maxi,sum);
        if(sum<0)
        sum=0;
    }
    return maxi;
}

int maxSubArray(vector<int>& nums)
 {
    int n=nums.size();
    if(n==1)
    return nums[0];
    vector<int> pf;
    pf.push_back(nums[0]);
    for(int i=1;i<n;++i)
    pf.push_back(nums[i]+pf[i-1]);
    int m = INT_MIN;
    int elem = *max_element(pf.begin(),pf.end());
    for(int j=0;j<n-1;++j)
    {
        for(int k=j+1;k<n;++k)
        m = max(m,(pf[k]-pf[j]));
        
    }
    m = max(m,elem);
    int mi = *max_element(nums.begin(),nums.end());
    cout<<m<<" "<<mi;
    
    if(mi>m)
    return mi;
    else return m;
    

 }

 vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        stack<int> s;
        const int N =1e5;
        vector<int> ans;
        vector<int> v(N);
        int n=nums2.size();
        s.push(nums2[n-1]);
        v[nums2[n-1]]=-1;
        
        for(int i=nums2.size()-2;i>=0;--i)
        {
             if(nums2[i]<(s.top()))
            {
                
                v[nums2[i]]=s.top();
                s.push(nums2[i]);
            }
            else
            {
                while(!s.empty() && s.top()<nums2[i]  )//order matters in &&
                s.pop();
                if(s.empty())
                v[nums2[i]]=-1;
                else
                v[nums2[i]]=s.top();
                s.push(nums2[i]);
            }
        }
        for(int j=0;j<nums1.size();++j)
        {
            ans.push_back(v[nums1[j]]);
        }


        return ans;
    }
   

Things to keep in Mind in Linked List
1) Make sure where to use temp->next1=NULL  OR temp!=NULL
2) fast!=NULL && fast->next!=NULL 
Use this order only else it will give runtime error

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteMiddle(ListNode* head) {

           ListNode* o=head;
           ListNode* t=head;
           ListNode* prev=head;
           if(head->next==NULL)
           {
            return head=NULL;
           }
           if(head->next->next==NULL)
           {
            delete head->next;
            head->next=NULL;
            return head;
           }
          while(t!=NULL && t->next!=NULL) 
           {
             if(t!=head)
             prev=prev->next;
             o=o->next;
             t=t->next->next; 
           }
           prev->next=o->next;
           delete o;
        return head;
    }
};

    ListNode* reverseList(ListNode* head)
    {ListNode* t1,*t2,*t3;
        t1 = head;
        if(head!=NULL)
         t2 = head->next;
        else
        return head;
        if(t2!=NULL)
        t3 = head->next->next;
        else
        {
            
            return head;
        }
        head->next=NULL;
        while(t3!=NULL)
        {
            t2->next=t1;
            t1=t2;
            t2=t3;
            t3=t3->next;
        }
        t2->next=t1;
        head = t2;
        return head;

    }
     

ListNode* reverseList(ListNode* head) {
        stack<int> s;
        ListNode* t=head;
           while(t!=NULL)
           {
             s.push(t->val);
             t=t->next;
           }
           t=head;
             while(t!=NULL)
           {
             t->val = s.top();
             s.pop();
             t=t->next;
           }
           return head;
    

int search(vector<int>& nums, int target) {
        int low = 0;
        int n = nums.size();
        int high = n-1;
        
        while(high>=low){
            int mid = (high+low)/2;
        if(nums[mid]==target)return mid;
        else if(target>nums[mid])
        {
            low = mid+1;
        }
        else
        {
            high=mid-1;
        }
        }
        return -1;
    }

bool cmp(pair<int,int> a,pair<int,int> b)
{return a>b;}
sort(p.begin(),p.end(),cmp);

bool cmp(int a,int b)
{
  return a>b;
}
sort(v.begin(),v.end(),cmp);
//Remember in sort use cmp not cmp()

Example 1. without virtual keyword / Using scope resolution
#include <iostream>

using namespace std;

class classA {
    public:
    int a;
};

class classB : public classA {
    public:
    int b;
};
class classC : public classA {
    public:
    int c;
};
class classD : public classB, public classC {
    public:
    int d;
    
};

int main() {
   
   classD objD;
   //objD.a; Error
   
   objD.classB::a = 100; // this way is correct
   objD.classC::a = 200;
   
   cout<<"A from classB = "<<objD.classB::a<<endl;
   cout<<"A from classc = "<<objD.classC::a<<endl;
   objD.b = 10;
   objD.c = 20;
   objD.d = 30;
   cout<<"B = "<<objD.b<<endl;
   cout<<"C = "<<objD.c<<endl;
   cout<<"D = "<<objD.d<<endl;
   
    
    return 0;
}
//Output:
A from classB = 100
A from classc = 200
B = 10
C = 20
D = 30

_______________________________________________________________-
  
  Example 2. Using Virtual Kwyeord
  #include <iostream>

using namespace std;

class classA {
    public:
    int a;
};

class classB : virtual public classA {
    public:
    int b;
};
class classC : virtual public classA {
    public:
    int c;
};
class classD : public classB, public classC {
    public:
    int d;
    
};

int main() {
   
   classD objD;
   
   objD.a = 100; // is correct using virtual keyword. we can access a value from one copy.
   cout<<"Using Virtual keyword: "<<endl;
   classB objB;
   objB.a =600;
   cout<<"A from class B = "<<objB.a<<endl;
   cout<<"A from class D = "<<objD.a<<endl;
   objD.b = 10;
   objD.c = 20;
   objD.d = 30;
   cout<<"B = "<<objD.b<<endl;
   cout<<"C = "<<objD.c<<endl;
   cout<<"D = "<<objD.d<<endl;
   
    
    return 0;
}
//Output:
Using Virtual keyword: 
A from class B = 600
A from class D = 100
B = 10
C = 20
D = 30

none_of(v.begin(),v.end(),[](int x){return x>0;});
//it returns boolean value

any_of(v.begin(),v.end(),[](int x){return x%2==0;});
//it returns boolean value

all_of(v.begin(),v.end(),[](int x){return x>0;});
//it returns boolean value

it = find(v.begin(),v.end(),num);
//if not found it returns v.end();

int sum = accumulated(v.begin(),v.end(),0);

int a =*(max_element(v.begin(),v.end()));

int a =*(min_element(v.begin(),v.end()));

pair<int, int> findNonDivisiblePair(const std::vector<int>& vec) {
    for (size_t i = 0; i < vec.size(); ++i) {
        for (size_t j = i + 1; j < vec.size(); ++j) {
            if (vec[i] % vec[j] != 0 && vec[j] % vec[i] != 0) {
                return std::make_pair(vec[i], vec[j]);
            }
        }
    }
    // If no pair is found, return a pair of -1, -1 or handle as required
    return std::make_pair(-1, -1);
}

pair<int, int> findMinimumNonDivisiblePair(const std::vector<int>& vec) {
    std::pair<int, int> minPair = std::make_pair(-1, -1);
    int minSum = std::numeric_limits<int>::max();

    for (size_t i = 0; i < vec.size(); ++i) {
        for (size_t j = i + 1; j < vec.size(); ++j) {
            if (vec[i] % vec[j] != 0 && vec[j] % vec[i] != 0) {
                int currentSum = vec[i] + vec[j];
                if (currentSum < minSum) {
                    minSum = currentSum;
                    minPair = std::make_pair(vec[i], vec[j]);
                }
            }
        }
    }
    return minPair;
}

bool check(vector<int>& nums) {
        int count = 0 ;
        if (nums[0] < nums[nums.size()-1]) count++ ;
        for (int i=1; i<nums.size(); i++){
            if (nums[i] < nums[i-1]){
                count++ ;
                if (count > 1) return false ;
            }
        }
        return true ;
    }

#include <iostream>

using namespace std;

int main() {
    
    char variable1 = 'b';
    int variable2 = 15;
    double variable3 = 10.2;
    
    char *pntr1 = &variable1;
    int *pntr2 = &variable2;
    double *pntr3 = &variable3;
    
    cout<<"before changing: "<<endl;
    cout<<"variable1 value= "<<variable1<<",\t\tAddress: "<<&variable1<<",\t*pntr1 value = "<<*pntr1<<endl;
    cout<<"variable2 value= "<<variable2<<",\tAddress: "<<&variable2<<",\t*pntr2 = "<<*pntr2<<endl;
    cout<<"variable3 value= "<<variable3<<",\tAddress: "<<&variable3<<",\t*pntr3 = "<<*pntr3<<endl;
    
    *pntr1 = 'c';
    *pntr2 = 25;
    *pntr3 = 12.50;
    
    cout<<"____________________"<<endl;
    cout<<"After changing: "<<endl;
    cout<<"variable1 value= "<<variable1<<",\t\tAddress: "<<&variable1<<",\t*pntr1 value = "<<*pntr1<<endl;
    cout<<"variable2 value= "<<variable2<<",\tAddress: "<<&variable2<<",\t*pntr2 = "<<*pntr2<<endl;
    cout<<"variable3 value= "<<variable3<<",\tAddress: "<<&variable3<<",\t*pntr3 = "<<*pntr3<<endl;

    
    return 0;
}
//OUTPUT:
before changing: 
variable1 value= b,		Address: b(b5��,	*pntr1 value = b
variable2 value= 15,	Address: 0x7ffce6356230,	*pntr2 = 15
variable3 value= 10.2,	Address: 0x7ffce6356228,	*pntr3 = 10.2
____________________
After changing: 
variable1 value= c,		Address: c(b5��,	*pntr1 value = c
variable2 value= 25,	Address: 0x7ffce6356230,	*pntr2 = 25
variable3 value= 12.5,	Address: 0x7ffce6356228,	*pntr3 = 12.5

 int findMaxConsecutiveOnes(vector<int>& nums) {
        int count = 0;
        int m=0;
        int n=nums.size();
        for(int j=0;j<n;++j)
        {
            if(nums[j]==1)
            {
                count++;
                 m=max(count,m);
            }
            else{
               
                count=0;
            }
        }
        return m;
        
    }

    vector<int> v;
        int n=nums.size();
        int f=k%(n);
        int a=n-f;
        for(int i=0;i<n;++i)
        {
            if((a+i)<=(n-1))
            v.push_back(nums[a+i]);
            else
            v.push_back(nums[a+i-nums.size()]);
        }
        nums=v;}
};

 int removeDuplicates(vector<int>& nums) {
       int i=0;
       int n=nums.size();
       for(int j=1;j<n;++j)
       {if(nums[i]!=nums[j])
        {  nums[i+1]=nums[j]; i++;}}
       return i+1;}

 int removeDuplicates(vector<int>& nums) {
        set<int> s;
        for(int i=0;i<nums.size();++i)
        {
            s.insert(nums[i]);
        }
        set<int> :: iterator it;
        vector<int> v;
        for(it=s.begin();it!=s.end();++it)
        {
            v.push_back(*it);
        }
        nums=v;
        int a = s.size();
        return a;
        
    }

int setBit(int n)
    {
        // Write Youwhile(r Code here
        int count=0;
        while((n%2)!=0)
    {
        n=n>>1;
        count++;
    }
    n=n+1;
    for(int i=0;i<count;++i)
    {
        n=n*2+1;
    }
        return n;
    }

int setBit(int n)
    {
        // Write Youwhile(r Code here
        int count=0;
        while((n%2)!=0)
    {
        n=n>>1;
        count++;
    }
    n=n+1;
    for(int i=0;i<count;++i)
    {
        n=n*2+1;
    }
        return n;
    }

 const int N = 1e5;
        vector<int> dp(N,-1);
class Solution {
public:
    int climbStairs(int n) {
       
        if(n==1)return 1;
        if(n==2)return 2;
        if(dp[n]!=-1)return dp[n];
        return dp[n]=climbStairs(n-1)+climbStairs(n-2);
      }
};

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5;
vector<int> dp(N,-1);
int fib(int n)
{
    if(n==0)return 0;
    if(n==1)return 1;
    if(dp[n]!=-1)return dp[n];
    return dp[n]=fib(n-1)+fib(n-2);
}
int main()
{
    int n=6;
    cout<<fib(n);
}

string reverseWords(string s) {
       int n = s.size();
       std::string reverse_string = "";
       for ( int i = n-1 ; i > -1; --i ){
        if (s[i] == ' '){
            continue;
        }
        int count = 0;
        while ( i > -1 && s[i] != ' '){
            --i; count++;
        }
        if (reverse_string != ""){
            reverse_string.append(" ");
        }
        reverse_string.append(s.substr(i+1,count));
       }
       return reverse_string; 
    }

class Solution {
public:
    string frequencySort(string s) {
        map<char,int> m1;
        multimap<int,char> m2;
        map<char,int> :: iterator it;
        multimap<int,char>::iterator it1;
        string str = "";
        for(int i=0;i<s.length();++i)
         m1[s[i]]++;
        for(it=m1.begin();it!=m1.end();++it)
        m2.insert({it->second,it->first});
        for(it1=m2.begin();it1!=m2.end();++it1)
         {
            for(int j=it1->first;j>0;--j)
            {str.push_back(it1->second);}
         }
         reverse(str.begin(),str.end());
         return str;
     }
};

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        string r;
        if(s.length()!=t.length())
        return false;
        map<char,char> m1,m2,m3;
        for(int i=0;i<s.length();++i)
        {
            m1.insert({s[i],t[i]});
            m2.insert({t[i],s[i]});
        }
        if(m1.size()>=m2.size())
        {m3=m2;
        r=s;}
        else
        {m3=m1;r=t;}
        for(int j=0;j<s.length();++j)
        {
            if(r[j]==m3[t[j]])
            continue;
            else
            return false;
        }
        return true;
        
    }
};

 string s= "ayush";
    sort(s.begin(),s.end());
    cout<<s;

if(str.find(goal) != string::npos)
           {return true;}
           else{return false;}

if(str.find(goal) != string::npos)
           {return true;}
           else{return false;}

if(n==1)return v[0];
if(v[0]!=v[1])return v[0];
if(v[n-1]!=v[n-2])return v[n-1];
low=1;high=n-2;
while(low<high)
  {
    mid=high-((high-low)/2);
    if(v[mid]!=v[mid-1] && v[mid]!=v[mid+1])return v[mid];
    if((mid%2==0 && v[mid-1]==v[mid]) || (mid%2==1 && v[mid+1]==v[mid]))
      {
        high=mid-1;
      }
    else if((mid%2==1 && v[mid-1]==v[mid]) || (mid%2==0 && v[mid+1]==v[mid]))
      {
        low=mid+1;
      }
  }
  

#include <iostream>
#include <istream>
#include <string>
#include <vector>

using namespace std;

class Book {
    int BookID;
    std::string Title;
    std::string Author;
    double price;
    static int numOfBooks;
    
  friend class Library; // Declare Library as a friend class

    public:
    Book(int BookID, std::string Title, std::string Author, double price){
        this->BookID = BookID;
        this->Title = Title;
        this->Author = Author;
        this->price = price;
        numOfBooks ++;
    }
    int getBookID() const {
    return BookID;
}

    
    std::string getTitle() const {
    return Title;
}
   std::string getAuthor() const {
    return Author;
}
   double getPrice() const {
    return price;
}
    //Static Function
   static int getTotalNumOfBooks(){
        return numOfBooks;
    };

};

int Book::numOfBooks = 0;


//Class User
class Users{
    
    public:
    std::string name;
    std::string address;
    std::string email;
    int phoneNum;
    
    Users(std::string n, std::string addre,std::string em, int pN){
        name = n;
        address = addre;
        email = em;
        phoneNum = pN;
    }
    
    //Virtual Function & Overiding function
    virtual void display(){
    }
    
};
//Derived Class from Base class User
class Student: public Users{
    
    int studentID;
    public:
    Student(int studentID, std::string name, std::string address, std::string email, int phoneNum):Users(name, address, email, phoneNum){
        this->studentID = studentID;
    }
    
    int getStudentID() const {
    return studentID;
}
    
    //Function Overloading, Same Name but different arguments.
    void print(std::string name){
        cout<<"student Name: "<<name<<endl;
    }
    void print(std::string name, int studentID){
        cout<<"Student Name: "<<name<<endl;
        cout<<"Student ID: "<<studentID<<endl;
    }
    //Default arguments
    void print(std::string name, std::string email, int studentID = 1111){
        cout<<"Student Name: "<<name<<endl;
        cout<<"Student Email: "<<email<<endl;
        cout<<"Student ID: "<<studentID<<endl;
    }
    
    void display(){
        cout<<"\n__Student Info:_ "<<endl;
        cout<<"ID: "<<studentID<<endl;
        cout<<"Name: "<<name<<endl;
        cout<<"Address: "<<address<<endl;
        cout<<"Email: "<<email<<endl;
        cout<<"Phone Number: "<<phoneNum<<endl;
    }
    
    //Friend Function
    friend void globalFunction(Student &stud);
};
class Staff: public Users{
    int staffID;
    public:
    Staff(int staffID, std::string name, std::string address, std::string email, int phoneNum):Users(name, address, email, phoneNum){
        this->staffID = staffID;
    }
    int getStaffID(){
        return staffID;
    }
    
    void display(){
        cout<<"\n___Staff Info:_ "<<endl;
        cout<<"ID: "<<staffID<<endl;
        cout<<"Name: "<<name<<endl;
        cout<<"Address: "<<address<<endl;
        cout<<"Email: "<<email<<endl;
        cout<<"Phone Number: "<<phoneNum<<endl;
    }
    friend void globalFunction(Staff &staf);
};

//Friend Function implementation
void globalFunction(Student &stud, Staff &staf){
    cout<<"\nAccessing Student ID: "<<stud.getStudentID()<<endl;
    cout<<"Accessing Staff ID: "<<staf.getStaffID()<<endl;
}

 class Library{

vector<Book*> books; // Declaration of books vector
vector<Student*> students;
    
    Book *book;
    std::string name;
    std::string address;
    
    public:
    Library(std::string name, std::string address){
        this->name = name;
        this->address = address;
    }
    
    void setBook(Book *book){
        this->book = book;
    }
    Book* getBook(){
        return book;
    }
    std::string getName(){
        return name;
    }
    void setName(std::string name){
        this->name = name;
    }
    std::string getAddress(){
        return address;
    }
    void setAddress(std::string address){
        this->address = address;
    }
    void addBook(const std::string& title, const std::string& author, double price) {
        int id = books.size() + 1; // Generate ID automatically based on the number of books
        books.push_back(new Book(id, title, author, price));
        cout << "Book added successfully with ID: " << id << endl;
    }
    bool deleteBook(int id) {
        auto it = find_if(books.begin(), books.end(), [id](const Book* book) {
            return book->getBookID() == id;
        });
        if (it != books.end()) {
            books.erase(it);
            return true;
        }
        return false;
    }
    void editBook(int id, std::string newTitle, std::string newAuthor, double newPrice) {
        auto it = find_if(books.begin(), books.end(), [id](const Book* book) {
            return book->getBookID() == id;
        });
        if (it != books.end()) {
            (*it)->Title = newTitle;
            (*it)->Author = newAuthor;
            (*it)->price = newPrice;
        }
    }
    void showBookInfo(int id) {
        auto it = std::find_if(books.begin(), books.end(), [id](const Book* book) {
            return book->getBookID() == id;
        });
        if (it != books.end()) {
            std::cout << "Book ID: " << (*it)->getBookID() << std::endl;
            std::cout << "Book Title: " << (*it)->getTitle() << std::endl;
            std::cout << "Book Author: " << (*it)->getAuthor() << std::endl;
            std::cout << "Book Price: " << (*it)->getPrice() << std::endl;
        }
    }

    std::vector<Book*>& getBooks() { // Return a reference to the vector of books
        return books;
    }


    void addStudent(const std::string& name, const std::string& address, const std::string& email, int phoneNum) {
        int id = students.size() + 1; // Generate ID automatically based on the number of students
        students.push_back(new Student(id, name, address, email, phoneNum));
        cout << "Student added successfully with ID: " << id << endl;
    }

    bool deleteStudent(int id) {
        auto it = find_if(students.begin(), students.end(), [id](const Student* student) {
            return student->getStudentID() == id;
        });
        if (it != students.end()) {
            students.erase(it);
            return true;
        }
        return false;
    }

    void editStudent(int id, const string& newName, const string& newAddress, const string& newEmail, int newPhoneNum) {
        auto it = find_if(students.begin(), students.end(), [id](const Student* student) {
            return student->getStudentID() == id;
        });
        if (it != students.end()) {
            (*it)->name = newName;
            (*it)->address = newAddress;
            (*it)->email = newEmail;
            (*it)->phoneNum = newPhoneNum;
        }
    }

    void showStudentInfo(int id) {
    auto it = find_if(students.begin(), students.end(), [id](const Student* student) {
        return student->getStudentID() == id;
    });
    if (it != students.end()) {
        cout << "Student ID: " << (*it)->getStudentID() << endl;
        cout << "Student Name: " << (*it)->name << endl;
        cout << "Student Address: " << (*it)->address << endl;
        cout << "Student Email: " << (*it)->email << endl;
        cout << "Student Phone Number: " << (*it)->phoneNum << endl;
    }
}
};





int main() {
    Library library("University Library", "Uskudar");

    while (true) {
        cout << "\nMenu:" << endl;
        cout << "1. Manage Books" << endl;
        cout << "2. Manage Students" << endl;
        cout << "3. Exit" << endl;
        cout << "Enter your choice: ";

        int choice;
        cin >> choice;

        switch (choice) {
        case 1: {
            cout << "\nBooks Menu:" << endl;
            cout << "1. Add Book" << endl;
            cout << "2. Delete Book" << endl;
            cout << "3. Edit Book" << endl;
            cout << "4. Show Book Information" << endl;
            cout << "5. Book List" << endl;
            cout << "Enter your choice: ";

            int bookChoice;
            cin >> bookChoice;

            switch (bookChoice) {
            case 1: {
              std::string title, author;
              double price;
              cout << "Enter book title: ";
                 cin.ignore();
                 getline(cin, title);
                 cout << "Enter book author: ";
                     getline(cin, author);
                   cout << "Enter book price: ";
                   cin >> price;
                   library.addBook(title, author, price);

                
                break;
            }
            case 2: {
                int id;
                cout << "Enter ID of the book to delete: ";
                cin >> id;
                if (library.deleteBook(id)) {
                    cout << "Book with ID " << id << " deleted successfully." << endl;
                }
                else {
                    cout << "Book with ID " << id << " not found." << endl;
                }
                break;
            }
            case 3: {
                int id;
                string newTitle, newAuthor;
                double newPrice;
                cout << "Enter ID of the book to edit: ";
                cin >> id;
                cout << "Enter new title: ";
                cin.ignore();
                getline(cin, newTitle);
                cout << "Enter new author: ";
                getline(cin, newAuthor);
                cout << "Enter new price: ";
                cin >> newPrice;
                library.editBook(id, newTitle, newAuthor, newPrice);
                cout << "Book edited successfully." << endl;
                break;
            }
            case 4: {
                int id;
                cout << "Enter ID of the book to show information: ";
                cin >> id;
                library.showBookInfo(id);
                break;
            }
           case 5: {
            vector<Book*> books = library.getBooks();
             cout << "\nBook List:" << endl;
            for (Book* book : books) {
    cout << "Book ID: " << book->getBookID() << ", Title: " << book->getTitle() << ", Author: " << book->getAuthor() << ", Price: " << book->getPrice() << endl;
}
                 break;
               }

            default:
                cout << "Invalid choice." << endl;
            }
            break;
        }
            case 2: {
                cout << "\nStudents Menu:" << endl;
                cout << "1. Add Student" << endl;
                cout << "2. Remove Student" << endl;
                cout << "3. Edit Student" << endl;
                cout << "4. Get Student Info" << endl;
                cout << "5. Exit" << endl;
                cout << "Enter your choice: ";

                int studentChoice;
                cin >> studentChoice;

                switch (studentChoice) {
                    case 1: {
                         std::string name, address, email;
                        int phoneNum;
                        cout << "Enter student name: ";
                        cin.ignore();
                        getline(cin, name);
                        cout << "Enter student address: ";
                        getline(cin, address);
                        cout << "Enter student email: ";
                        cin >> email;
                         cout << "Enter student phone number: ";
                        cin >> phoneNum;
                        library.addStudent(name, address, email, phoneNum);
                        
                        break;
                    }
                    case 2: {
                        int id;
                        cout << "Enter ID of the student to remove: ";
                        cin >> id;
                        if (library.deleteStudent(id)) {
                            cout << "Student with ID " << id << " removed successfully." << endl;
                        } else {
                            cout << "Student with ID " << id << " not found." << endl;
                        }
                        break;
                    }
                    case 3: {
                        int id;
                        string newName, newAddress, newEmail;
                        int newPhoneNum;
                        cout << "Enter ID of the student to edit: ";
                        cin >> id;
                        cout << "Enter new name: ";
                        cin.ignore();
                        getline(cin, newName);
                        cout << "Enter new address: ";
                        getline(cin, newAddress);
                        cout << "Enter new email: ";
                        cin >> newEmail;
                        cout << "Enter new phone number: ";
                        cin >> newPhoneNum;
                        library.editStudent(id, newName, newAddress, newEmail, newPhoneNum);
                        cout << "Student edited successfully." << endl;
                        break;
                    }
                    case 4: {
                        int id;
                        cout << "Enter ID of the student to get information: ";
                        cin >> id;
                        library.showStudentInfo(id);
                        break;
                    }
                    case 5: {
                        cout << "Exiting students menu..." << endl;
                        break;
                    }
                    default:
                        cout << "Invalid choice." << endl;
                }
                break;
            }
        case 3:
            cout << "Exiting..." << endl;
            return 0;
        default:
            cout << "Invalid choice. Please enter a number from 1 to 3." << endl;
        }
    }

    return 0;
}
//OUTPUT:


Menu:
1. Manage Books
2. Manage Students
3. Exit
Enter your choice: 1

Books Menu:
1. Add Book
2. Delete Book
3. Edit Book
4. Show Book Information
5. Book List
Enter your choice: 1
Enter book title: The Power
Enter book author: James
Enter book price: 23
Book added successfully with ID: 1

Menu:
1. Manage Books
2. Manage Students
3. Exit
Enter your choice: 1

Books Menu:
1. Add Book
2. Delete Book
3. Edit Book
4. Show Book Information
5. Book List
Enter your choice: 1
Enter book title: Psychology
Enter book author: Mike
Enter book price: 21
Book added successfully with ID: 2

Menu:
1. Manage Books
2. Manage Students
3. Exit
Enter your choice: 1

Books Menu:
1. Add Book
2. Delete Book
3. Edit Book
4. Show Book Information
5. Book List
Enter your choice: 5

Book List:
Book ID: 1, Title: The Power, Author: James, Price: 23
Book ID: 2, Title: Physcology, Author: Mike, Price: 21

Menu:
1. Manage Books
2. Manage Students
3. Exit
Enter your choice: 1

Books Menu:
1. Add Book
2. Delete Book
3. Edit Book
4. Show Book Information
5. Book List
Enter your choice: 2
Enter ID of the book to delete: 2
Book with ID 2 deleted successfully.

Menu:
1. Manage Books
2. Manage Students
3. Exit
Enter your choice: 1

Books Menu:
1. Add Book
2. Delete Book
3. Edit Book
4. Show Book Information
5. Book List
Enter your choice: 5

Book List:
Book ID: 1, Title: The Power, Author: James, Price: 23

Menu:
1. Manage Books
2. Manage Students
3. Exit
Enter your choice: 2

Students Menu:
1. Add Student
2. Remove Student
3. Edit Student
4. Get Student Info
5. Exit
Enter your choice: 1
Enter student name: Mohamed
Enter student address: Istanbul
Enter student email: moha@gmail.com
Enter student phone number: 5544
Student added successfully with ID: 1

Menu:
1. Manage Books
2. Manage Students
3. Exit
Enter your choice: 2

Students Menu:
1. Add Student
2. Remove Student
3. Edit Student
4. Get Student Info
5. Exit
Enter your choice: 1
Enter student name: Nasir
Enter student address: Istanbul
Enter student email: nasir@gmail.com
Enter student phone number: 1122
Student added successfully with ID: 2

Menu:
1. Manage Books
2. Manage Students
3. Exit
Enter your choice: 2

Students Menu:
1. Add Student
2. Remove Student
3. Edit Student
4. Get Student Info
5. Exit
Enter your choice: 2
Enter ID of the student to remove: 2
Student with ID 2 removed successfully.

Menu:
1. Manage Books
2. Manage Students
3. Exit
Enter your choice: 2

Students Menu:
1. Add Student
2. Remove Student
3. Edit Student
4. Get Student Info
5. Exit
Enter your choice: 4
Enter ID of the student to get information: 2

Menu:
1. Manage Books
2. Manage Students
3. Exit
Enter your choice: 2

Students Menu:
1. Add Student
2. Remove Student
3. Edit Student
4. Get Student Info
5. Exit
Enter your choice: 4
Enter ID of the student to get information: 1
Student ID: 1
Student Name: Mohamed
Student Address: Istanbul
Student Email: moha@gmail.com
Student Phone Number: 5544

Menu:
1. Manage Books
2. Manage Students
3. Exit
Enter your choice: 3
Exiting...
 
Normal program termination. Exit status: 0

#include <iostream>

using namespace std;

class Book{
    int BookID;
    string Title;
    string Author;
    double price;
    static int numOfBooks;
    
    public:
    //Parameter Constructor
    Book(int BookID, string Title, string Author, double price){
        this->BookID = BookID;
        this->Title = Title;
        this->Author = Author;
        this->price = price;
        numOfBooks ++;
    }
    int getBookID(){
        return BookID;
    }
    string getTitle(){
        return Title;
    }
    string getAuthor(){
        return Author;
    }
    double getPrice(){
        return price;
    }
    //Static Function
   static int getTotalNumOfBooks(){
        return numOfBooks;
    }
};
int Book::numOfBooks = 0;

class Library{
    Book *book;
    string name;
    string address;
    
    public:
    Library(string name, string address){
        this->name = name;
        this->address = address;
    }
    
    void setBook(Book *book){
        this->book = book;
    }
    Book* getBook(){
        return book;
    }
    string getName(){
        return name;
    }
    void setName(string name){
        this->name = name;
    }
    string getAddress(){
        return address;
    }
    void setAddress(string address){
        this->address = address;
    }
};

//Class User
class Users{
    
    public:
    string name;
    string address;
    string email;
    int phoneNum;
    
    Users(string n, string addre,string em, int pN){
        name = n;
        address = addre;
        email = em;
        phoneNum = pN;
    }
    
    //Virtual Function & Overiding function
    virtual void display(){
    }
    
};
//Derived Class from Base class User
class Student: public Users{
    
    int studentID;
    public:
    Student(int studentID, string name, string address, string email, int phoneNum):Users(name, address, email, phoneNum){
        this->studentID = studentID;
    }
    
    int getStudentID(){
        return studentID;
    }
    
    //Function Overloading, Same Name but different arguments.
    void print(string name){
        cout<<"student Name: "<<name<<endl;
    }
    void print(string name, int studentID){
        cout<<"Student Name: "<<name<<endl;
        cout<<"Student ID: "<<studentID<<endl;
    }
    //Default arguments
    void print(string name, string email, int studentID = 1111){
        cout<<"Student Name: "<<name<<endl;
        cout<<"Student Email: "<<email<<endl;
        cout<<"Student ID: "<<studentID<<endl;
    }
    
    void display(){
        cout<<"\n_____Student Info:____ "<<endl;
        cout<<"ID: "<<studentID<<endl;
        cout<<"Name: "<<name<<endl;
        cout<<"Address: "<<address<<endl;
        cout<<"Email: "<<email<<endl;
        cout<<"Phone Number: "<<phoneNum<<endl;
    }
    
    //Friend Function
    friend void globalFunction(Student &stud);
};
class Staff: public Users{
    int staffID;
    public:
    Staff(int staffID, string name, string address, string email, int phoneNum):Users(name, address, email, phoneNum){
        this->staffID = staffID;
    }
    int getStaffID(){
        return staffID;
    }
    
    void display(){
        cout<<"\n______Staff Info:____ "<<endl;
        cout<<"ID: "<<staffID<<endl;
        cout<<"Name: "<<name<<endl;
        cout<<"Address: "<<address<<endl;
        cout<<"Email: "<<email<<endl;
        cout<<"Phone Number: "<<phoneNum<<endl;
    }
    friend void globalFunction(Staff &staf);
};

//Friend Function implementation
void globalFunction(Student &stud, Staff &staf){
    cout<<"\nAccessing Student ID: "<<stud.getStudentID()<<endl;
    cout<<"Accessing Staff ID: "<<staf.getStaffID()<<endl;
}

int main() {

    cout<<"_____Library Management System._____"<<endl;
    
    Library lib("University Library","Uskudar");
    cout<<"\n____Library Info____"<<endl;
    cout<<"Name: "<<lib.getName()<<endl;
    cout<<"Address: "<<lib.getAddress()<<endl;
    
    lib.setBook(new Book(1, "Java", "James", 20.99));
    cout<<"____Book Info____"<<endl;
    cout<<"Book ID: "<<lib.getBook()->getBookID()<<endl;
    cout<<"Book Title: "<<lib.getBook()->getTitle()<<endl;
    cout<<"Book Author: "<<lib.getBook()->getAuthor()<<endl;
    cout<<"Book Price: "<<lib.getBook()->getPrice()<<endl;
    //Calling static function in the Book class
    cout<<"Total Books in the Library are: "<<Book::getTotalNumOfBooks()<<endl;
    
    lib.setBook(new Book(2, "Math", "Mike", 24.99));
    cout<<"____Book Info____"<<endl;
    cout<<"Book ID: "<<lib.getBook()->getBookID()<<endl;
    cout<<"Book Title: "<<lib.getBook()->getTitle()<<endl;
    cout<<"Book Author: "<<lib.getBook()->getAuthor()<<endl;
    cout<<"Book Price: "<<lib.getBook()->getPrice()<<endl;
    
    cout<<"Total Books in the Library are: "<<Book::getTotalNumOfBooks()<<endl;
    
    Student s1(2023, "Mohamed","Istanbul","Student@gmail.com", 11111);
    Users *user;
    user = & s1;
    user->display();
    
    Staff stff(3034,"Staff1","Istnabul","Staff@gmail.com", 9999);
    user = &stff;
    user->display();
    
    //Friend Function
    globalFunction(s1,stff);
    
    //Calling Overloading Function in the Student class
    cout<<"_____"<<endl;
    s1.print("Musa");
    s1.print("Musa",5555);
    //Calling default arguments in the student class
    s1.print("Yahya", "yahya@emial.com");

    return 0;
}
___________________________________________________________________________
//OUTPUT:

_____Library Management System._____

____Library Info____
Name: University Library
Address: Uskudar
____Book Info____
Book ID: 1
Book Title: Java
Book Author: James
Book Price: 20.99
Total Books in the Library are: 1
____Book Info____
Book ID: 2
Book Title: Math
Book Author: Mike
Book Price: 24.99
Total Books in the Library are: 2

_____Student Info:____ 
ID: 2023
Name: Mohamed
Address: Istanbul
Email: Student@gmail.com
Phone Number: 11111

______Staff Info:____ 
ID: 3034
Name: Staff1
Address: Istnabul
Email: Staff@gmail.com
Phone Number: 9999

Accessing Student ID: 2023
Accessing Staff ID: 3034
_____
student Name: Musa
Student Name: Musa
Student ID: 5555
Student Name: Yahya
Student Email: yahya@emial.com
Student ID: 1111

#include <iostream>

using namespace std;

class Base{
   
    public:
    virtual void output(){
        cout<<"Virtual Function"<<endl;
    }
    void display(){
        cout<<"Display Base Function"<<endl;
    }
};

class derived:public Base{
    
    public:
    void output(){
        cout<<"Function in the derived "<<endl;
    }
    void display(){
        cout<<"Display Derived Function"<<endl;
    }
};


int main() {
    
    Base *ptr;
    derived d;
    ptr = &d;
  //Run time binding, it will call output function in the drived class
    ptr->output();
  
  //Compile time binding, it will call display function in the base class.
    ptr->display();

    return 0;
}
//OUTPUT:
Function in the derived 
Display Base Function

question 1.

#include <iostream>

using namespace std;
//Abstract class becuase it contain ppure virtual function
class Vehicle{
    
    public:
   virtual void drive() = 0;
};

class Car: public Vehicle{
    public:
    void drive(){
        cout<<"Driving a car "<<endl;
    }
};

class Motorcycle: public Vehicle{
    public:
    void drive(){
        cout<<"Driving a motorcycle"<<endl;
    }
};


int main() {
    //Abstract class can not be instantiated. but you can write as pointer and 
    Vehicle *obj;
   Car c;
   obj = &c;
   obj->drive();
   Motorcycle m;
   obj = &m;
   obj->drive();

    return 0;
}
//OUTPUT:
Driving a car 
Driving a motorcycle
____________________________________________________________

Question 2:
#include <iostream>

using namespace std;

class Shape{
    
    public:
   double Area(){
       return 0.0;
   }
   
};

class Rectangle: public Shape{
    double width;
    double length;
    public:
    Rectangle(double width, double length){
        this->width = 10;
        this->length = 10;
    }
    double Area(){
        //int area = width * length;
        return width * length;
        //cout<<"Area of Rectangle = "<<area<<endl;
    }
    
};

class Triangle: public Shape{
    double base;
    double heigth;
    public:
    Triangle(double b, double h):base(b),heigth(h){
        
    }
    double Area(){
        return 0.5 * base * heigth;
    }
};

int main() {
    Shape *shape;
    Rectangle rect(10, 10);
    shape = &rect;
    shape->Area();
   
    

    return 0;
}

________________________________________________________________-
  Question 3.
#include <iostream>

using namespace std;

class Animal{
    
    protected:
    string name;
    public:
    Animal(string name){
        this->name = name;
    }
    virtual void makeSound(){
        cout<<"Animal: "<<endl;
    }
   
};

class Dog: public Animal{
    string breed;
    public:
    Dog(string name, string breed):Animal(name){
        this->breed = breed;
    }
    void makeSound(){
        //Animal::makeSound(); to call makeSound function in Animal class
        cout<<"Dog makes Sound."<<endl;
    }
    void display(){
        cout<<"Dog Name: "<<name<<endl;
        cout<<"Dog Breed: "<<breed<<endl;
    }
};

class Cat: public Animal{
    string color;
    
    public:
    Cat(string name, string color):Animal(name){
        this->color = color;
    }
    void makeSound(){
        cout<<"Cat makes Sound."<<endl;
    }
    void display(){
        cout<<"Cat Name: "<<name<<endl;
        cout<<"Cat Color "<<color<<endl;
    }
};

int main() {
    
    
    Dog d("Doggy","Male");
    d.display();
    d.makeSound();
    cout<<endl;
    Cat c("Catty","Brown");
    c.display();
    c.makeSound();
   
    

    return 0;
}
//OUTPUT:
Dog Name: Doggy
Dog Breed: Male
Dog makes Sound.

Cat Name: Catty
Cat Color Brown
Cat makes Sound.

#include <iostream>

using namespace std;
//PUre Virtual Function
class Employee{
    int code;
    string name[20];
    public:
    virtual void getData();
    virtual void Display();
};
class Grade : public Employee{
    char grade[20];
    float salary;
    
    public:
    void getData();
    void Display();
};

void Employee::getData(){
    
}
void Employee::Display(){
    
}
void Grade::getData(){
    cout<<"Enter Employee Grade: "<<endl;
    cin>>grade;
    cout<<"Enter Employee Salaray: "<<endl;
    cin>>salary;
}
void Grade::Display(){
    cout<<"Employee Grade is: "<<grade<<endl;
    cout<<"Employee Salaray is: "<<salary<<endl;
}

int main() {
    Employee *ptr;
    Grade obj;
    ptr = &obj;
    ptr->getData();
    ptr->Display();

    return 0;
}
//OUTPUT:
Enter Employee Grade: 
A
Enter Employee Salaray: 
24000
Employee Grade is: A
Employee Salaray is: 24000

#include <iostream>

using namespace std;
//Hierarchical inheritance
class Employee{
    
    protected:
    string name;
    int employeeID;
    
    public:
    
    void inputEmployeeInfo(){
        cout<<"Enter name: "<<endl;
        cin>>name;
        cout<<"Enter Employee ID: "<<endl;
        cin>>employeeID;
    }
    void displayEmployeeInfo(){
        cout<<"Name: "<<name<<endl;
        cout<<"Employee ID: "<<employeeID<<endl;
    }
};
//Derived Manager Class From Employee Class

class Manager :virtual public Employee{
    protected:
    int level;
    public:
    void inputManagerInfo(){
        //inputEmployeeInfo();
        cout<<"Enter Manager Level: "<<endl;
        cin>>level;
    }
    void displayManagerInfo(){
        //displayEmployeeInfo();
        cout<<"Manager Level: "<<level<<endl;
    }
};
//Derived Developer Class From Employee
class Developer : virtual public Employee{
    protected:
    int progLang;
    public:
    void inputDeveloperInfo(){
        //inputEmployeeInfo();
        cout<<"Enter Programing Language: "<<endl;
        cin>>progLang;
    }
    void displayDeveloperInfo(){
        //displayEmployeeInfo();
        cout<<"Programing Language: "<<progLang<<endl;
    }
};
//DErived class for Teamlead That will display both info manager and developer
class TeamLead : public Manager, public Developer{
    
    public:
    
    void inputInfo(){
        inputEmployeeInfo();   // Employee Info
        inputManagerInfo();    // Manager Info
        inputDeveloperInfo();   //Developer Info
    }

    void displayInfo(){
        cout<<"Team Lead Details: "<<endl;
        displayEmployeeInfo(); // Employee Info
        displayManagerInfo();  // Manager Info
        displayDeveloperInfo();  //Developer Info
    }
};

int main() {
    
    TeamLead tl;
    tl.inputInfo();
    cout<<endl;
    tl.displayInfo();
    
   

    return 0;
}

//OUTPUT:
Enter name: 
mohamed
Enter Employee ID: 
1222
Enter Manager Level: 
7
Enter Programing Language: 
java

Team Lead Details: 
Name: mohamed
Employee ID: 1222
Manager Level: 7
Programing Language: java

#include <iostream>

using namespace std;
//Hierarchical inheritance
class Shape{
    
    public:
    double area(){
    return 0.0;
    }
    
    void displayShape(){
        cout<<"Generic Shape: ";
    }
};
//Derived REctangle Class From Shape Class
class Rectangle:public Shape{
    double width;
    double length;
    
    public:
    //You can write like this also:
    Rectangle(double w, double l){
        width = w;
        length = l;
    }
    //Both of them are same
    //Rectangle(double w, double l):width(w),length(l){
        
    //}
    double AreaRectangle(){
        return width * length;
    }
    void displayRectangleInfo(){
        displayShape();
        cout<<"Rectangle: \nLength = "<<length<<"\nwidth = "<<width<<"\nArea of Rectangle = "<<AreaRectangle()<<endl;
    }
};
//Second Derived Circle class from Shape class
class Circle:public Shape{
    
    double radius;
    
    public:
    Circle(double r):radius(r){
        
    }
    double AreaCircle(){
        return 3.14 * radius * radius;
    }
    void displayCircleInfo(){
        displayShape();
        cout<<"Circle: \nRadius = "<<radius<<"\nArea of Circle = "<<AreaCircle()<<endl;
    }
};
//Third Derived class from Shape
class Triangle:public Shape {
    
    double base;
    double heigth;
    
    public:
    Triangle(double b, double h):base(b),heigth(h){
        
    }
    double AreaTriangle(){
        return 0.5 * base * heigth;
    }
    void displayTriangleInfo(){
        displayShape();
        cout<<"Triangle: \nBase = "<<base<<"\nHeigth = "<<heigth<<"\nArea of Triangle = "<<AreaTriangle()<<endl;
    }
};

int main() {
    Rectangle rect(10.2, 20.2);
    rect.displayRectangleInfo();
    cout<<endl;
    Circle c(10);
    c.displayCircleInfo();
    cout<<endl;
    Triangle tri(10.2, 10.1);
    tri.displayTriangleInfo();

    return 0;
}
//OUTPUT:
Generic Shape: Rectangle: 
Length = 20.2
width = 10.2
Area of Rectangle = 206.04

Generic Shape: Circle: 
Radius = 10
Area of Circle = 314

Generic Shape: Triangle: 
Base = 10.2
Heigth = 10.1
Area of Triangle = 51.51

Question 1.
#include <iostream>

using namespace std;

class course
{
	protected:
		int course_code;
		string course_name;
		course(int cc, string cn)
		{
			course_code = cc;
			course_name = cn;
			
		}
		void displayCourseInfo()
		{
			cout<<"Course code: "<<course_code<<endl;
			cout<<"Course name: "<<course_name<<endl;
		}
};
class studentCourse:public course
{
	public:
	int id;
	string grade;
	studentCourse(int cc, string cn, int ID, string Grade):course(cc, cn)
	{
		id = ID;
		grade = Grade;
		
	}
	void displayStudentInfo()
	{
		displayCourseInfo();
		cout<<"ID: "<<id<<endl;
		cout<<"Grade: "<<grade<<endl;
	}
};
int main()
{
	studentCourse s1(202,"OOP II", 20021212, "A");
	s1.displayStudentInfo();
	
	cout<<endl;
	studentCourse s2(201, "Software Design", 210209327, "A");
	s2.displayStudentInfo();
	return 0;
}
//OUTPUT:
Course code: 202
Course name: OOP II
ID: 20021212
Grade: A

Course code: 201
Course name: Software Design
ID: 210209327
Grade: A

Question 2.
#include <iostream>
#include <string>
using namespace std;

class Vehicle
{
	public: 
	int max_speed;
	int num_wheels;
	Vehicle(int speed, int wheels)
	{
		max_speed = speed;
		num_wheels = wheels;
	}
	void vehicle_info()
	{
		
		cout<<"Vehicle Max Speed: "<<max_speed<<endl;
		cout<<"Vehicle Wheels: "<<num_wheels<<endl;

	}
};
class Car:public Vehicle
{
	public: 
	string car_name;
	string car_model;
	Car(int speed, int wheels, string cname, string cmodel): Vehicle(speed, wheels)
	{
		car_name = cname;
		car_model = cmodel;
	}
	void car_info()
	{
		vehicle_info();
		cout<<"Car Name: "<<car_name<<endl;
		cout<<"Car Model: "<<car_model<<endl;
	}
};

class Motorcycle:public Vehicle
{
	public: 
	string mcar_name;
	string mcar_model;
	Motorcycle(int speed, int wheels, string mcname, string mcmodel): Vehicle(speed, wheels)
	{
		mcar_name = mcname;
		mcar_model = mcmodel;
	}
	void Motorcycle_info()
	{
		vehicle_info();
		cout<<"Motorcycle Name: "<<mcar_name<<endl;
		cout<<"Motorcycle Model: "<<mcar_model<<endl;
	}
};
class ConvertibleCar: public Car, public Motorcycle
{
	public: 

	ConvertibleCar(int speed, int wheels, string cname, string cmodel, string mcname, string mcmodel): 
	Car(speed, wheels, cname, cmodel), Motorcycle(speed, wheels, mcname, mcmodel)
	{}
	void ConvertibleCar_info()
	{
		car_info();
		cout<<endl;
		Motorcycle_info();
	}
}; 
int main()
{
	Car car(200, 4, "Honda", "Sedan");
    Motorcycle bike(180, 2, "Vespa", "Sport");
    ConvertibleCar convertible(220, 4, "Convertible Car", "Sport Car", "Convertible Motocycle", "Vespa");

    cout << "Car Information:" << endl;
    car.car_info();
    cout << endl;

    cout << "Motorcycle Information:" << endl;
    bike.Motorcycle_info();
    cout << endl;

    cout << "Convertible Car Information:" << endl;
    convertible.ConvertibleCar_info();


	return 0;
}
//OUTPUT:
Car Information:
Vehicle Max Speed: 200
Vehicle Wheels: 4
Car Name: Honda
Car Model: Sedan

Motorcycle Information:
Vehicle Max Speed: 180
Vehicle Wheels: 2
Motorcycle Name: Vespa
Motorcycle Model: Sport

Convertible Car Information:
Vehicle Max Speed: 220
Vehicle Wheels: 4
Car Name: Convertible Car
Car Model: Sport Car

Vehicle Max Speed: 220
Vehicle Wheels: 4
Motorcycle Name: Convertible Motocycle
Motorcycle Model: Vespa

#include <iostream>

using namespace std;

class Father{
    int age;
    char name[10];
    
    public:
    void get();
    void show();
    
};
void Father::get(){
    cout<<"Father Name Please: "<<endl;
    cin>>name;
    cout<<"Father Age Please: "<<endl;
    cin>>age;
}
void Father::show(){
    cout<<"Father name is: "<<name<<endl;
    cout<<"Father Age is: "<<age<<endl;
}

class doughter: public Father{
    int age;
    char name[10];
    
    public:
    void get();
    void show();
 
};
void doughter::get(){
    Father::get();
    cout<<"doughter name Please: "<<endl;
    cin>>name;
    cout<<"doughter Age Please: "<<endl;
    cin>>age;
}
void doughter::show(){
    Father::show();
    cout<<"doughter Name is: "<<name<<endl;
    cout<<"doughter Age is: "<<age<<endl;
}

class Son: public Father{
    int age;
    char name[10];
    
    public:
    void get();
    void show();
};

void Son::get(){
    Father::get();
    cout<<"Son name Please: "<<endl;
    cin>>name;
    cout<<"Son Age Please: "<<endl;
    cin>>age;
    
}
void Son::show(){
    Father::show();
    cout<<"Son name is: "<<name<<endl;
    cout<<"Son Age is: "<<age<<endl;
}

int main() {
    
   Son s1;
   doughter d1;
   s1.get();
   d1.get();
   s1.show();
   d1.show();
   
    return 0;
} 
//OUTPUT:
Father Name Please: 
ABdi
Father Age Please: 
56
Son name Please: 
moha
Son Age Please: 
23
Father Name Please: 
Abdi
Father Age Please: 
56
doughter name Please: 
aisha
doughter Age Please: 
21
Father name is: ABdi
Father Age is: 56
Son name is: moha
Son Age is: 23
Father name is: Abdi
Father Age is: 56
doughter Name is: aisha
doughter Age is: 21

#include <iostream>

using namespace std;

class Father{
    int age;
    char name[10];
    
    public:
    void get();
    void show();
    
};
void Father::get(){
    cout<<"Father Name Please: "<<endl;
    cin>>name;
    cout<<"Father Age Please: "<<endl;
    cin>>age;
}
void Father::show(){
    cout<<"Father name is: "<<name<<endl;
    cout<<"Father Age is: "<<age<<endl;
}

class Mother{
    int age;
    char name[10];
    
    public:
    void get();
    void show();
 
};
void Mother::get(){
    cout<<"Mother name Please: "<<endl;
    cin>>name;
    cout<<"Mother Age Please: "<<endl;
    cin>>age;
}
void Mother::show(){
    cout<<"Mother Name is: "<<name<<endl;
    cout<<"Mother Age is: "<<age<<endl;
    
}

class Son: public Father, public Mother{
    int age;
    char name[10];
    
    public:
    void get();
    void show();
};

void Son::get(){
    Father::get();
    Mother::get();
    cout<<"Son name Please: "<<endl;
    cin>>name;
    cout<<"Son Age Please: "<<endl;
    cin>>age;
    
}
void Son::show(){
    Father::show();
    Mother::show();
    cout<<"Son name is: "<<name<<endl;
    cout<<"Son Age is: "<<age<<endl;
}

int main() {
    
   Son s;
   s.get();
   s.show();
   
    return 0;
}
//OUTPUT:
Father Name Please: 
Abdi
Father Age Please: 
54
Mother name Please: 
Qamar
Mother Age Please: 
37
Son name Please: 
Moahmed
Son Age Please: 
23
Father name is: Abdi
Father Age is: 54
Mother Name is: Qamar
Mother Age is: 37
Son name is: Moahmed
Son Age is: 23

#include <iostream>

using namespace std;

class worker{
    int age;
    char name[10];
    
    public:
    void get();
    void show();
    
};
void worker::get(){
    cout<<"Your Name Please: "<<endl;
    cin>>name;
    cout<<"Your Age Please: "<<endl;
    cin>>age;
}
void worker::show(){
    cout<<"My name is: "<<name<<endl;
    cout<<"My Age is: "<<age<<endl;
}

class manager:public worker{
    int now;
    
    public:
    void get();
    void show();
 
};
void manager::get(){
    worker::get();
    cout<<"Num of workers are: "<<endl;
    cin>>now;
}
void manager::show(){
    worker::show();
    cout<<"Num of workers are: "<<now<<endl;
}

class ceo: public manager{
    int nom;
    
    public:
    void get();
    void show();
    void print();
};

void ceo::get(){
    manager::get();
    cout<<"Num of managers are: "<<endl;
    cin>>nom;
}
void ceo::show(){
    manager::show();
    cout<<"Num of managers are: "<<nom<<endl;
}

int main() {
    
    worker w1;
    manager m1;
    ceo c1;
    c1.get();
    c1.show();
 

    return 0;
}
//OUTPUT:

Your Name Please: 
moha
Your Age Please: 
45
Num of workers are: 
787
Num of managers are: 
897
My name is: moha
My Age is: 45
Num of workers are: 787
Num of managers are: 897

#include <iostream>

using namespace std;

class worker{
    int age;
    char name[10];
    
    public:
    void get();
    void show();
    
};
void worker::get(){
    cout<<"Your Name Please: "<<endl;
    cin>>name;
    cout<<"Your Age Please: "<<endl;
    cin>>age;
}
void worker::show(){
    cout<<"My name is: "<<name<<endl;
    cout<<"My Age is: "<<age<<endl;
}

class manager: public worker{
    int now;
    
    public:
    void get();
    void show();
 
};
void manager::get(){
    worker::get();
    cout<<"Num of workers are: "<<endl;
    cin>>now;
}
void manager::show(){
    worker::show();
    cout<<"Num of workers are: "<<now<<endl;
}

int main() {
    
    worker w1;
    manager m1;
    m1.get();
    m1.show();
   

    return 0;
}

//Output:
Your Name Please: 
moha
Your Age Please: 
34
Num of workers are: 
67
My name is: moha
My Age is: 34
Num of workers are: 67

void ComponentGraphics::UpdateBackground(GLFWwindow* window, Shader shader, ComponentCamera* camera, glm::vec3 difference)
{
    if (camera->getlockParallax() == false)
    {
        if (difference[0] > 0.0001f) //right
        {
            posX -= backgroundSpeed;
        }
        if (difference[0] < -0.0001f) //left
        {
           posX += backgroundSpeed;
        }
    }
    //96.0f / 50.0f, 84.0f / 50.0f
    float CurrentCameraX = camera->getCameraPosition().x;
    UpdateGraphics(0.0001, window, shader, camera, ConvertTo4x4Affine(AffineScaleMatrix(96.0f / 50.0f, 84.0f / 50.0f) * AffineTranslationMatrix(posX, posY)), "NoCamX");
}

void ComponentGraphics::setBackgroundSpeedFromFile(Stream stream)
{
    backgroundSpeed = StreamReadFloat(stream);
}

void ComponentGraphics::setBackgroundSpeed(float speed)
{
   backgroundSpeed = speed;
}

void ComponentGraphics::setPosFromFile(Stream stream)
{
    posX = StreamReadFloat(stream);
    posY = StreamReadFloat(stream);
}

//------------------------------------------------------------------------------
/*!
\file	ComponentCamera.cpp
\main author: Mary (m.khuu) Camera movement : Riti 
\par	Copyright © 2021 DigiPen (USA) Corporation.
\brief
\reference http://www.opengl-tutorial.org/beginners-tutorials/tutorial-6-keyboard-and-mouse/
*/
//------------------------------------------------------------------------------
#pragma once

//------------------------------------------------------------------------------
// Includes:
//------------------------------------------------------------------------------
#include "ComponentCamera.h"

ComponentCamera::ComponentCamera(void)
{
	ModelMatrix = mat4(0.0f);
	ViewMatrix = mat4(1.0f);
	ProjectionMatrix = mat4(0.0f);
	MVPmatrix = mat4(0.0f);

	position = glm::vec3(0.0f, 0.0f, 1.0f);

	cameraBoundariesMax = glm::vec3(0.0f, 0.0f, 1.0f);
	cameraBoundariesMin = glm::vec3(0.0f, 0.0f, 1.0f);
	cameraSize = glm::vec3(0.0f, 0.0f, 1.0f);
	cameraSpeed = glm::vec3(0.45f, 0.35f, 0.0f);

	horizontalAngle = 3.14f;
	verticalAngle = 0.0f;

	lockParallax = 0;

	lastTime = 0;
}

glm::mat4 ComponentCamera::cameraInput(GLFWwindow* window)
{
	double currentTime = glfwGetTime();
	float deltaTime = float(currentTime - lastTime);

	// Direction : Spherical coordinates to Cartesian coordinates conversion
	glm::vec3 direction(
		cos(verticalAngle) * sin(horizontalAngle),
		sin(verticalAngle),
		cos(verticalAngle) * cos(horizontalAngle)
	);

	// Right vector
	glm::vec3 right = glm::vec3(
		sin(horizontalAngle - 3.14f / 2.0f),
		0,
		cos(horizontalAngle - 3.14f / 2.0f)
	);

	// Up vector
	glm::vec3 up = glm::cross(right, direction);


	//vertical movements currently move diagonally
	if (glfwGetKey(window, GLFW_KEY_UP) == GLFW_PRESS)
	{
		position += deltaTime * cameraSpeed[1];
		position -= right * deltaTime * cameraSpeed[1];
	}
	if (glfwGetKey(window, GLFW_KEY_DOWN) == GLFW_PRESS)
	{
		position -= deltaTime * cameraSpeed[1];
		position += right * deltaTime * cameraSpeed[1];
	}

	if (glfwGetKey(window, GLFW_KEY_RIGHT) == GLFW_PRESS)
	{
		position += right * deltaTime * cameraSpeed[0];
	}
	if (glfwGetKey(window, GLFW_KEY_LEFT) == GLFW_PRESS)
	{
		position -= right * deltaTime * cameraSpeed[0];
	}

	ProjectionMatrix = glm::ortho((-cameraSize.x / 2), (cameraSize.x / 2), -(cameraSize.y / 2), (cameraSize.y / 2), 0.0f, 100.0f);

	ViewMatrix = glm::lookAt(position, position + direction, up);
	ModelMatrix = glm::mat4(1.0f);

	lastTime = currentTime;
	MVPmatrix = (ProjectionMatrix * ViewMatrix * ModelMatrix);
	return MVPmatrix; //returns MVP matrix
}

glm::mat4 ComponentCamera::tieCameraToPlayer(GLFWwindow* window, glm::vec3 playerPos)
{
	setlockParallax(false);
	glm::vec3 direction(
		cos(verticalAngle) * sin(horizontalAngle),
		sin(verticalAngle),
		cos(verticalAngle) * cos(horizontalAngle)
	);

	glm::vec3 right = glm::vec3(
		sin(horizontalAngle - 3.14f / 2.0f),
		0,
		cos(horizontalAngle - 3.14f / 2.0f)
	);

	glm::vec3 up = glm::cross(right, direction);

	ProjectionMatrix = glm::ortho((-cameraSize.x / 2), (cameraSize.x / 2), -(cameraSize.y / 2), (cameraSize.y / 2), 0.0f, 100.0f);

	vec3 CamPos = getCameraPosition();
	CamPos.x = playerPos.x;
	CamPos.y = playerPos.y;

	if (CamPos.x  - (cameraSize.x / 2) < cameraBoundariesMin[0])
	{
		CamPos.x = cameraBoundariesMin[0] + (cameraSize.x / 2);
	}
	if (CamPos.x + (cameraSize.x / 2) > cameraBoundariesMax[0])
	{
		CamPos.x = cameraBoundariesMax[0] -(cameraSize.x / 2);
	}
	if (CamPos.y < cameraBoundariesMin[1])
	{
		CamPos.y = cameraBoundariesMin[1];
	}


	//uncommented to always lock the center of camera to player
	//when player goes up
	
	if (CamPos.y > cameraBoundariesMax[1])
	{
		CamPos.y = cameraBoundariesMax[1];
	}


	setCameraPosition(CamPos);
	ViewMatrix = glm::lookAt(position, position + direction, up);

	ModelMatrix = glm::mat4(1.0f);

	MVPmatrix = (ProjectionMatrix * ViewMatrix * ModelMatrix);
	return MVPmatrix; //returns MVP matrix
}

void ComponentCamera::UpdateCamera(GLFWwindow* window, Shader shader, glm::vec3 position)
{
	shader.use();
	if (position != glm::vec3(0))
	{
		GLuint MatrixID = glGetUniformLocation(shader.ID, "transformation");
		//glm::matddddd4 MVP = cameraInput(window);
		glm::mat4 MVP = tieCameraToPlayer(window, position);
		glUniformMatrix4fv(MatrixID, 1, GL_FALSE, &MVP[0][0]);
	}
}

glm::mat4 ComponentCamera::getModelMatrix()
{
	return ModelMatrix;
}

glm::mat4 ComponentCamera::getViewMatrix()
{
	return ViewMatrix;
}

glm::mat4 ComponentCamera::getProjectionMatrix()
{
	return ProjectionMatrix;
}

glm::mat4 ComponentCamera::getMVPmatrix()
{
	return MVPmatrix;
}

glm::vec3 ComponentCamera::getCameraBoundariesMin()
{
	return cameraBoundariesMin;
}

glm::vec3 ComponentCamera::getCameraBoundariesMax()
{
	return cameraBoundariesMax;
}

glm::vec3 ComponentCamera::getCameraPosition()
{
	return position;
}

glm::vec3 ComponentCamera::getCameraSize()
{
	return cameraSize;
}

bool ComponentCamera::getlockParallax()
{
	return lockParallax;
}

void ComponentCamera::setCameraBoundariesMin(glm::vec3 boundaries)
{
	cameraBoundariesMin = boundaries;
}

void ComponentCamera::setCameraBoundariesMax(glm::vec3 boundaries)
{
	cameraBoundariesMax = boundaries;
}

void ComponentCamera::setCameraPosition(glm::vec3 P)
{
	position = P;
}

void ComponentCamera::setCameraSize(glm::vec3 S)
{
	cameraSize = S;
}

void ComponentCamera::setCameraSpeed(float speedX, float speedY)
{
	cameraSpeed[0] = speedX;
	cameraSpeed[1] = speedY;
}

void ComponentCamera::setCameraSpeedVec(glm::vec3 speed)
{
	cameraSpeed = speed;
}

void ComponentCamera::setMVPmatrix(glm::mat4 matrix)
{
	MVPmatrix = matrix;
}

void ComponentCamera::setlockParallax(bool value)
{
	lockParallax = value;
}

// ---------------------------------------------------------------------------
// Project Name		:	Nook
// File Name		:	LevelSelect.c
// Author			:	Mary Khuu
// Creation Date	:	19 Mar 2021
// Purpose			:	Level Select
//
// All content © 2021 DigiPen (USA) Corporation, all rights reserved.
// ---------------------------------------------------------------------------

#include "framework.h"
#include "AEEngine.h"
#include "Audio.h"
#include "GameStateManager.h"
#include "Sprite.h"
#include "object_data.h"

#include "LevelSelect.h"

//------------------------------------------------------------------------------
// Private Constants:
//------------------------------------------------------------------------------

//------------------------------------------------------------------------------
// Private Structures:
//------------------------------------------------------------------------------

//------------------------------------------------------------------------------
// Public Variables:
//------------------------------------------------------------------------------

//------------------------------------------------------------------------------
// Private Variables:
//------------------------------------------------------------------------------

static vec2 backgroundSize = { 1670.0f, 564.0f };
static vec2 buttonSize = { 100.0f, 30.0f };
static vec2 textSize = { 150.0f, 50.0f };
static vec2 iconSize = { 30.0f, 30.0f };
static vec2 menuPos = { 0.0f, 200.0f };
static vec2 tutorialPos = { 0.0f, 100.0f };
static vec2 level1Pos = { 0.0f, 0.0f };
static vec2 level2Pos = { 0.0f, -100.0f };
static vec2 level3Pos = { 0.0f, -200.0f };

static signed long mouseX, mouseY;
static float mouseInWorldX, mouseInWorldY;

static AEGfxVertexList* bgMesh;
static AEGfxVertexList* buttonMesh;
static AEGfxVertexList* fontMesh;
static AEGfxVertexList* iconMesh;
static AEGfxVertexList* numMesh;

static AEGfxTexture* bgTexture;
static AEGfxTexture* buttonTexture;
static AEGfxTexture* fontTexture;
static AEGfxTexture* iconTexture;
static AEGfxTexture* numTexture;

static TextureOffset numOffsets[10];
static TextureOffset fontOffsets[30];
static int* currentfontOffset = 0;
static int currfontFrame = 0;
static float* fontTime;

//------------------------------------------------------------------------------
// Private Function Declarations:
//------------------------------------------------------------------------------

//------------------------------------------------------------------------------
// Public Functions:
//------------------------------------------------------------------------------

void LevelSelectLoad()
{
    /*mesh for bg*/
    AEGfxMeshStart();

    AEGfxTriAdd(
        -backgroundSize.x, -backgroundSize.y, 0xFF00FF00, 0.0f, 1.0f,
        backgroundSize.x, -backgroundSize.y, 0xFF00FF00, 1.0f, 1.0f,
        -backgroundSize.x, backgroundSize.y, 0xFF00FF00, 0.0f, 0.0f);

    AEGfxTriAdd(
        backgroundSize.x, -backgroundSize.y, 0xFF00FF00, 1.0f, 1.0f,
        backgroundSize.x, backgroundSize.y, 0xFF00FF00, 1.0f, 0.0f,
        -backgroundSize.x, backgroundSize.y, 0xFF00FF00, 0.0f, 0.0f);

    bgMesh = AEGfxMeshEnd();
    AE_ASSERT_MESG(bgMesh, "Failed to create button!");

    bgTexture = AEGfxTextureLoad("Assets/CityscapeGrey.png");
    AE_ASSERT_MESG(bgTexture, "Failed to create pTex!!");

    /*mesh for buttons: green*/
    AEGfxMeshStart();

    AEGfxTriAdd(
        -buttonSize.x, -buttonSize.y, 0xFF00FF00, 0.0f, 1.0f,
        buttonSize.x, -buttonSize.y, 0xFF00FF00, 1.0f, 1.0f,
        -buttonSize.x, buttonSize.y, 0xFF00FF00, 0.0f, 0.0f);

    AEGfxTriAdd(
        buttonSize.x, -buttonSize.y, 0xFF00FF00, 1.0f, 1.0f,
        buttonSize.x, buttonSize.y, 0xFF00FF00, 1.0f, 0.0f,
        -buttonSize.x, buttonSize.y, 0xFF00FF00, 0.0f, 0.0f);

    buttonMesh = AEGfxMeshEnd();
    AE_ASSERT_MESG(buttonMesh, "Failed to create button!");

    buttonTexture = AEGfxTextureLoad("Assets/NookButtonBright.png");
    AE_ASSERT_MESG(buttonTexture, "Failed to create texture!");

    /*mesh for hover icon*/
    iconMesh = createQuadMesh(iconSize.x, iconSize.y, 1.0f, 1.0f, "yarn");

    iconTexture = AEGfxTextureLoad("Assets/TempHover.png");
    AE_ASSERT_MESG(iconTexture, "Failed to create texture!");

    /*mesh for text*/
    fontMesh = createQuadMesh(15.0f, 15.0f, 1.0 / 5, 1.0f / 6, "alphabets");

    fontTexture = AEGfxTextureLoad("Assets/NookFontSheet_alphabet.png");
    AE_ASSERT_MESG(fontTexture, "Failed to create texture!");    

    fontOffsets[0].mX = 0.0f;			    fontOffsets[0].mY = 0.0f / 6;  //A
    fontOffsets[1].mX = 1.0f / 5;		    fontOffsets[1].mY = 0.0f / 6;  //B
    fontOffsets[2].mX = 2.0f / 5;			fontOffsets[2].mY = 0.0f / 6;  //C
    fontOffsets[3].mX = 3.0f / 5;			fontOffsets[3].mY = 0.0f / 6;  //D
    fontOffsets[4].mX = 4.0f / 5;			fontOffsets[4].mY = 0.0f / 6;  //E

    fontOffsets[5].mX = 0.0f;			    fontOffsets[5].mY = 1.0f / 6;  //F
    fontOffsets[6].mX = 1.0f / 5;		    fontOffsets[6].mY = 1.0f / 6;  //G
    fontOffsets[7].mX = 2.0f / 5;			fontOffsets[7].mY = 1.0f / 6;  //H
    fontOffsets[8].mX = 3.0f / 5;			fontOffsets[8].mY = 1.0f / 6;  //I
    fontOffsets[9].mX = 4.0f / 5;			fontOffsets[9].mY = 1.0f / 6;  //J

    fontOffsets[10].mX = 0.0f;			    fontOffsets[10].mY = 2.0f / 6;  //K
    fontOffsets[11].mX = 1.0f / 5;		    fontOffsets[11].mY = 2.0f / 6;  //L
    fontOffsets[12].mX = 2.0f / 5;			fontOffsets[12].mY = 2.0f / 6;  //M
    fontOffsets[13].mX = 3.0f / 5;			fontOffsets[13].mY = 2.0f / 6;  //N
    fontOffsets[14].mX = 4.0f / 5;			fontOffsets[14].mY = 2.0f / 6;  //O

    fontOffsets[15].mX = 0.0f;			    fontOffsets[15].mY = 3.0f / 6;  //P
    fontOffsets[16].mX = 1.0f / 5;		    fontOffsets[16].mY = 3.0f / 6;  //Q
    fontOffsets[17].mX = 2.0f / 5;			fontOffsets[17].mY = 3.0f / 6;  //R
    fontOffsets[18].mX = 3.0f / 5;			fontOffsets[18].mY = 3.0f / 6;  //S
    fontOffsets[19].mX = 4.0f / 5;			fontOffsets[19].mY = 3.0f / 6;  //T

    fontOffsets[20].mX = 0.0f;			    fontOffsets[20].mY = 4.0f / 6;  //U
    fontOffsets[21].mX = 1.0f / 5;		    fontOffsets[21].mY = 4.0f / 6;  //V
    fontOffsets[22].mX = 2.0f / 5;			fontOffsets[22].mY = 4.0f / 6;  //W
    fontOffsets[23].mX = 3.0f / 5;			fontOffsets[23].mY = 4.0f / 6;  //X
    fontOffsets[24].mX = 4.0f / 5;			fontOffsets[24].mY = 4.0f / 6;  //Y


    fontOffsets[25].mX = 0.0f;			    fontOffsets[25].mY = 5.0f / 6;   //Z  
    fontOffsets[26].mX = 1.0f / 5;		    fontOffsets[26].mY = 5.0f / 6;  //blank (1)
    fontOffsets[27].mX = 2.0f / 5;			fontOffsets[27].mY = 5.0f / 6;  //blank (2)
    fontOffsets[28].mX = 3.0f / 5;			fontOffsets[28].mY = 5.0f / 6;  //blank (3)
    fontOffsets[29].mX = 4.0f / 5;			fontOffsets[29].mY = 5.0f / 6;  //blank (4)

    /*mesh for numbers*/
    numMesh = createQuadMesh(15.0f, 15.0f, 1.0 / 3, 1.0f / 4, "numbers");

    numTexture = AEGfxTextureLoad("Assets/NookFontSheet_numbers.png");
    AE_ASSERT_MESG(numTexture, "Failed to create texture!");

    numOffsets[0].mX = 0.0f;			    numOffsets[0].mY = 0.0f / 4;  //0
    numOffsets[1].mX = 1.0f / 3;		    numOffsets[1].mY = 0.0f / 4;  //1
    numOffsets[2].mX = 2.0f / 3;			numOffsets[2].mY = 0.0f / 4;  //2
    
    numOffsets[3].mX = 0.0f;			    numOffsets[3].mY = 1.0f / 4;  //3
    numOffsets[4].mX = 1.0f / 3;			numOffsets[4].mY = 1.0f / 4;  //4
    numOffsets[5].mX = 2.0f / 3;			numOffsets[5].mY = 1.0f / 4;  //5
    
    numOffsets[6].mX = 0.0f;		        numOffsets[6].mY = 2.0f / 4;  //6
    numOffsets[7].mX = 1.0f / 3;			numOffsets[7].mY = 2.0f / 4;  //7
    numOffsets[8].mX = 2.0f / 3;			numOffsets[8].mY = 2.0f / 4;  //8
    
    numOffsets[9].mX = 0.0f / 3;			numOffsets[9].mY = 3.0f / 4;  //9
}

void LevelSelectInit()
{
	AEGfxSetBackgroundColor(1.0f, 1.0f, 1.0f);
	AEGfxSetBlendMode(AE_GFX_BM_BLEND);
}

void LevelSelectUpdate(float dt)
{
    /* Tell the compiler that the 'dt' variable is unused. */
    UNREFERENCED_PARAMETER(dt);

    /*draw background*/
    AEGfxSetRenderMode(AE_GFX_RM_TEXTURE);
    AEGfxTextureSet(bgTexture, 0, 0);
    AEGfxSetTransparency(1.0f);
    AEGfxSetPosition(-250.0f, 0.0f);
    AEGfxMeshDraw(bgMesh, AE_GFX_MDM_TRIANGLES);

    //draw menu button
    AEGfxSetPosition(menuPos.x, menuPos.y);
    AEGfxTextureSet(buttonTexture, 0, 0); // no texture
    AEGfxMeshDraw(buttonMesh, AE_GFX_MDM_TRIANGLES);

    //draw tutorial button
    AEGfxSetPosition(tutorialPos.x, tutorialPos.y);
    AEGfxTextureSet(buttonTexture, 0, 0); // no texture
    AEGfxMeshDraw(buttonMesh, AE_GFX_MDM_TRIANGLES);
    

    //draw level1 button
    AEGfxSetPosition(level1Pos.x, level1Pos.y);
    AEGfxTextureSet(buttonTexture, 0, 0); // no texture
    AEGfxMeshDraw(buttonMesh, AE_GFX_MDM_TRIANGLES);

    //draw level2 button
    AEGfxSetPosition(level2Pos.x, level2Pos.y);
    AEGfxTextureSet(buttonTexture, 0, 0); // no texture
    AEGfxMeshDraw(buttonMesh, AE_GFX_MDM_TRIANGLES);

    //draw level3 button
    AEGfxSetPosition(level3Pos.x, level3Pos.y);
    AEGfxTextureSet(buttonTexture, 0, 0); // no texture
    AEGfxMeshDraw(buttonMesh, AE_GFX_MDM_TRIANGLES);

    /*MENU*/
    AEGfxSetPosition(menuPos.x - 45.0f, menuPos.y);
    AEGfxTextureSet(fontTexture, fontOffsets[12].mX, fontOffsets[12].mY, 0.0f);
    AEGfxMeshDraw(fontMesh, AE_GFX_MDM_TRIANGLES);

    AEGfxSetPosition(menuPos.x - 13.0f, menuPos.y);
    AEGfxTextureSet(fontTexture, fontOffsets[4].mX, fontOffsets[4].mY, 0.0f);
    AEGfxMeshDraw(fontMesh, AE_GFX_MDM_TRIANGLES);

    AEGfxSetPosition(menuPos.x + 15.0f, menuPos.y);
    AEGfxTextureSet(fontTexture, fontOffsets[13].mX, fontOffsets[13].mY, 0.0f);
    AEGfxMeshDraw(fontMesh, AE_GFX_MDM_TRIANGLES);

    AEGfxSetPosition(menuPos.x + 45.0f, menuPos.y);
    AEGfxTextureSet(fontTexture, fontOffsets[20].mX, fontOffsets[20].mY, 0.0f);
    AEGfxMeshDraw(fontMesh, AE_GFX_MDM_TRIANGLES);

    /*MENU - end*/

    /*TUTORIAL*/
    AEGfxSetPosition(tutorialPos.x - 86.0f, tutorialPos.y);
    AEGfxTextureSet(fontTexture, fontOffsets[19].mX, fontOffsets[19].mY, 0.0f);
    AEGfxMeshDraw(fontMesh, AE_GFX_MDM_TRIANGLES);

    AEGfxSetPosition(tutorialPos.x - 58.0f, tutorialPos.y);
    AEGfxTextureSet(fontTexture, fontOffsets[20].mX, fontOffsets[20].mY, 0.0f);
    AEGfxMeshDraw(fontMesh, AE_GFX_MDM_TRIANGLES);

    AEGfxSetPosition(tutorialPos.x - 30.0f, tutorialPos.y);
    AEGfxTextureSet(fontTexture, fontOffsets[19].mX, fontOffsets[19].mY, 0.0f);
    AEGfxMeshDraw(fontMesh, AE_GFX_MDM_TRIANGLES);

    AEGfxSetPosition(tutorialPos.x, tutorialPos.y);
    AEGfxTextureSet(fontTexture, fontOffsets[14].mX, fontOffsets[14].mY, 0.0f);
    AEGfxMeshDraw(fontMesh, AE_GFX_MDM_TRIANGLES);

    AEGfxSetPosition(tutorialPos.x + 30.0f, tutorialPos.y);
    AEGfxTextureSet(fontTexture, fontOffsets[17].mX, fontOffsets[17].mY, 0.0f);
    AEGfxMeshDraw(fontMesh, AE_GFX_MDM_TRIANGLES);

    AEGfxSetPosition(tutorialPos.x + 46.0f, tutorialPos.y);
    AEGfxTextureSet(fontTexture, fontOffsets[8].mX, fontOffsets[8].mY, 0.0f);
    AEGfxMeshDraw(fontMesh, AE_GFX_MDM_TRIANGLES);

    AEGfxSetPosition(tutorialPos.x + 65.0f, tutorialPos.y);
    AEGfxTextureSet(fontTexture, fontOffsets[0].mX, fontOffsets[0].mY, 0.0f);
    AEGfxMeshDraw(fontMesh, AE_GFX_MDM_TRIANGLES);

    AEGfxSetPosition(tutorialPos.x + 90.0f, tutorialPos.y);
    AEGfxTextureSet(fontTexture, fontOffsets[11].mX, fontOffsets[11].mY, 0.0f);
    AEGfxMeshDraw(fontMesh, AE_GFX_MDM_TRIANGLES);

    /*TUTORIAL - end*/

    /*LEVEL 1*/
    AEGfxSetPosition(level1Pos.x - 85.0f, level1Pos.y);
    AEGfxTextureSet(fontTexture, fontOffsets[11].mX, fontOffsets[11].mY, 0.0f);
    AEGfxMeshDraw(fontMesh, AE_GFX_MDM_TRIANGLES);

    AEGfxSetPosition(level1Pos.x - 60.0f, level1Pos.y);
    AEGfxTextureSet(fontTexture, fontOffsets[4].mX, fontOffsets[4].mY, 0.0f);
    AEGfxMeshDraw(fontMesh, AE_GFX_MDM_TRIANGLES);

    AEGfxSetPosition(level1Pos.x - 34.0f, level1Pos.y);
    AEGfxTextureSet(fontTexture, fontOffsets[21].mX, fontOffsets[21].mY, 0.0f);
    AEGfxMeshDraw(fontMesh, AE_GFX_MDM_TRIANGLES);

    AEGfxSetPosition(level1Pos.x - 5.0f, level1Pos.y);
    AEGfxTextureSet(fontTexture, fontOffsets[4].mX, fontOffsets[4].mY, 0.0f);
    AEGfxMeshDraw(fontMesh, AE_GFX_MDM_TRIANGLES);

    AEGfxSetPosition(level1Pos.x + 17.5f, level1Pos.y);
    AEGfxTextureSet(fontTexture, fontOffsets[11].mX, fontOffsets[11].mY, 0.0f);
    AEGfxMeshDraw(fontMesh, AE_GFX_MDM_TRIANGLES);

    AEGfxSetPosition(level1Pos.x + 85.0f, level1Pos.y);
    AEGfxTextureSet(numTexture, numOffsets[1].mX, numOffsets[1].mY, 0.0f); // 1
    AEGfxMeshDraw(numMesh, AE_GFX_MDM_TRIANGLES);

    /*LEVEL 1 - end*/

    /*LEVEL 2*/
    AEGfxSetPosition(level2Pos.x - 85.0f, level2Pos.y);
    AEGfxTextureSet(fontTexture, fontOffsets[11].mX, fontOffsets[11].mY, 0.0f);
    AEGfxMeshDraw(fontMesh, AE_GFX_MDM_TRIANGLES);

    AEGfxSetPosition(level2Pos.x - 60.0f, level2Pos.y);
    AEGfxTextureSet(fontTexture, fontOffsets[4].mX, fontOffsets[4].mY, 0.0f);
    AEGfxMeshDraw(fontMesh, AE_GFX_MDM_TRIANGLES);

    AEGfxSetPosition(level2Pos.x - 34.0f, level2Pos.y);
    AEGfxTextureSet(fontTexture, fontOffsets[21].mX, fontOffsets[21].mY, 0.0f);
    AEGfxMeshDraw(fontMesh, AE_GFX_MDM_TRIANGLES);

    AEGfxSetPosition(level2Pos.x - 5.0f, level2Pos.y);
    AEGfxTextureSet(fontTexture, fontOffsets[4].mX, fontOffsets[4].mY, 0.0f);
    AEGfxMeshDraw(fontMesh, AE_GFX_MDM_TRIANGLES);

    AEGfxSetPosition(level2Pos.x + 17.5f, level2Pos.y);
    AEGfxTextureSet(fontTexture, fontOffsets[11].mX, fontOffsets[11].mY, 0.0f);
    AEGfxMeshDraw(fontMesh, AE_GFX_MDM_TRIANGLES);

    AEGfxSetPosition(level2Pos.x + 85.0f, level2Pos.y);
    AEGfxTextureSet(numTexture, numOffsets[2].mX, numOffsets[2].mY, 0.0f); // 2
    AEGfxMeshDraw(numMesh, AE_GFX_MDM_TRIANGLES);

    /*LEVEL 2 - end*/

    /*LEVEL 3*/
    AEGfxSetPosition(level3Pos.x - 85.0f, level3Pos.y);
    AEGfxTextureSet(fontTexture, fontOffsets[11].mX, fontOffsets[11].mY, 0.0f);
    AEGfxMeshDraw(fontMesh, AE_GFX_MDM_TRIANGLES);

    AEGfxSetPosition(level3Pos.x - 60.0f, level3Pos.y);
    AEGfxTextureSet(fontTexture, fontOffsets[4].mX, fontOffsets[4].mY, 0.0f);
    AEGfxMeshDraw(fontMesh, AE_GFX_MDM_TRIANGLES);

    AEGfxSetPosition(level3Pos.x - 34.0f, level3Pos.y);
    AEGfxTextureSet(fontTexture, fontOffsets[21].mX, fontOffsets[21].mY, 0.0f);
    AEGfxMeshDraw(fontMesh, AE_GFX_MDM_TRIANGLES);

    AEGfxSetPosition(level3Pos.x - 5.0f, level3Pos.y);
    AEGfxTextureSet(fontTexture, fontOffsets[4].mX, fontOffsets[4].mY, 0.0f);
    AEGfxMeshDraw(fontMesh, AE_GFX_MDM_TRIANGLES);

    AEGfxSetPosition(level3Pos.x + 17.5f, level3Pos.y);
    AEGfxTextureSet(fontTexture, fontOffsets[11].mX, fontOffsets[11].mY, 0.0f);
    AEGfxMeshDraw(fontMesh, AE_GFX_MDM_TRIANGLES);

    AEGfxSetPosition(level3Pos.x + 85.0f, level3Pos.y);
    AEGfxTextureSet(numTexture, numOffsets[3].mX, numOffsets[3].mY, 0.0f); // 3
    AEGfxMeshDraw(numMesh, AE_GFX_MDM_TRIANGLES);

    /*LEVEL 3 - end*/

    /*get the mouse position*/
    AEInputGetCursorPosition(&mouseX, &mouseY);
    AEGfxConvertScreenCoordinatesToWorld(mouseX, mouseY, &mouseInWorldX, &mouseInWorldY);

    /*if menu is hovered*/
    if ((mouseInWorldX > (menuPos.x - buttonSize.x) && mouseInWorldX < (menuPos.x + buttonSize.x)) &&
        (mouseInWorldY > (menuPos.y - buttonSize.y) && mouseInWorldY < (menuPos.y + buttonSize.y)))
    {
        // Hover texture
        AEGfxSetRenderMode(AE_GFX_RM_TEXTURE);
        AEGfxSetPosition(menuPos.x - 140.0f, menuPos.y);
        AEGfxTextureSet(iconTexture, 0.0f, 0.0f);
        AEGfxMeshDraw(iconMesh, AE_GFX_MDM_TRIANGLES);

        if (AEInputCheckTriggered(RI_MOUSE_LEFT_BUTTON_DOWN))
        {
            GameStateManagerSetNextState(Menu);
        }
    }

    /*if tutorial is hovered*/
    if ((mouseInWorldX > (tutorialPos.x - buttonSize.x) && mouseInWorldX < (tutorialPos.x + buttonSize.x)) &&
        (mouseInWorldY > (tutorialPos.y - buttonSize.y) && mouseInWorldY < (tutorialPos.y + buttonSize.y)))
    {
        // Hover texture
        AEGfxSetRenderMode(AE_GFX_RM_TEXTURE);
        AEGfxSetPosition(tutorialPos.x - 140.0f, tutorialPos.y);
        AEGfxTextureSet(iconTexture, 0.0f, 0.0f);
        AEGfxMeshDraw(iconMesh, AE_GFX_MDM_TRIANGLES);

        if (AEInputCheckTriggered(RI_MOUSE_LEFT_BUTTON_DOWN))
        {
            GameStateManagerSetNextState(Tutorial);
        }
    }

    /*if level1 is hovered*/
    if ((mouseInWorldX > (level1Pos.x - buttonSize.x) && mouseInWorldX < (level1Pos.x + buttonSize.x)) &&
        (mouseInWorldY > (level1Pos.y - buttonSize.y) && mouseInWorldY < (level1Pos.y + buttonSize.y)))
    {
        // Hover texture
        AEGfxSetRenderMode(AE_GFX_RM_TEXTURE);
        AEGfxSetPosition(level1Pos.x - 140.0f, level1Pos.y);
        AEGfxTextureSet(iconTexture, 0.0f, 0.0f);
        AEGfxMeshDraw(iconMesh, AE_GFX_MDM_TRIANGLES);

        if (AEInputCheckTriggered(RI_MOUSE_LEFT_BUTTON_DOWN))
        {
            GameStateManagerSetNextState(Demo);
        }
    }

    /*if level2 is hovered*/
    if ((mouseInWorldX > (level2Pos.x - buttonSize.x) && mouseInWorldX < (level2Pos.x + buttonSize.x)) &&
        (mouseInWorldY > (level2Pos.y - buttonSize.y) && mouseInWorldY < (level2Pos.y + buttonSize.y)))
    {
        // Hover texture
        AEGfxSetRenderMode(AE_GFX_RM_TEXTURE);
        AEGfxSetPosition(level2Pos.x - 140.0f, level2Pos.y);
        AEGfxTextureSet(iconTexture, 0.0f, 0.0f);
        AEGfxMeshDraw(iconMesh, AE_GFX_MDM_TRIANGLES);

        if (AEInputCheckTriggered(RI_MOUSE_LEFT_BUTTON_DOWN))
        {
            GameStateManagerSetNextState(Level2);
        }
    }

    /*if level3 is hovered*/
    if ((mouseInWorldX > (level3Pos.x - buttonSize.x) && mouseInWorldX < (level3Pos.x + buttonSize.x)) &&
        (mouseInWorldY > (level3Pos.y - buttonSize.y) && mouseInWorldY < (level3Pos.y + buttonSize.y)))
    {
        // Hover texture
        AEGfxSetRenderMode(AE_GFX_RM_TEXTURE);
        AEGfxSetPosition(level3Pos.x - 140.0f, level3Pos.y);
        AEGfxTextureSet(iconTexture, 0.0f, 0.0f);
        AEGfxMeshDraw(iconMesh, AE_GFX_MDM_TRIANGLES);

        if (AEInputCheckTriggered(RI_MOUSE_LEFT_BUTTON_DOWN))
        {
            GameStateManagerSetNextState(Level3);
        }
    }
}

void LevelSelectShutdown()
{
    AudioCleanup();
}

void LevelSelectUnload()
{
    // Unload all textures.
    AEGfxTextureUnload(buttonTexture);
    AEGfxTextureUnload(fontTexture);
    AEGfxTextureUnload(bgTexture);
    AEGfxTextureUnload(iconTexture);
    AEGfxTextureUnload(numTexture);

    // Free all meshes.
    AEGfxMeshFree(buttonMesh);
    AEGfxMeshFree(fontMesh);
    AEGfxMeshFree(bgMesh);
    AEGfxMeshFree(iconMesh);
    AEGfxMeshFree(numMesh);
}

//------------------------------------------------------------------------------
// Private Functions:
//------------------------------------------------------------------------------

//if the last time player moved was left
if (!AEInputCheckCurr("A") && lastPlayerDir == 1 && isWalking == 0)
{
  //flip the sprite
  AEGfxTextureSet(playerIdleTexture, 0.0f, 0.0f);
  AEGfxSetFullTransform(curr->pos.x, curr->pos.y, 0.0f, -(curr->width * tile_dim), curr->height * tile_dim);
  isWalking = 0;
}

/*get the mouse x and y position*/
AEInputGetCursorPosition(&mouseX, &mouseY);
AEGfxConvertScreenCoordinatesToWorld(mouseX, mouseY, &mouseInWorldX, &mouseInWorldY);

/*only draw line if it's the wall and left click/hold on mouse occurs*/
if ((mouseInWorldX > (wallX - xHalfSize) && mouseInWorldX < (wallX + xHalfSize)) &&
    (mouseInWorldY > (wallY - yHalfSize) && mouseInWorldY < (wallY + yHalfSize)) &&
    (AEInputCheckCurr(RI_MOUSE_LEFT_BUTTON_DOWN)))
{
  /*mesh for line, needs to be updated with loop*/
  AEGfxMeshStart();

  AEGfxVertexAdd(playerX + xHalfSize, playerY, 0xFFFF0000, 0.0f, 0.0f);
  AEGfxVertexAdd(mouseInWorldX, mouseInWorldY, 0xFFFF0000, 0.0f, 0.0f);

  meshLine = AEGfxMeshEnd();
  AE_ASSERT_MESG(meshLine, "Failed to create line!");

  /*draw line*/
  AEGfxSetRenderMode(AE_GFX_RM_COLOR);
  AEGfxSetPosition(0.0f, 0.0f);
  AEGfxMeshDraw(meshLine, AE_GFX_MDM_LINES_STRIP);
}

// ---------------------------------------------------------------------------
// Project Name		:	Nook
// File Name		:	Menu.c
// Author			:	Rey Rosario, Mary Khuu
// Creation Date	:	25 Jan 2021
// Purpose			:	Main Menu
//
// All content © 2021 DigiPen (USA) Corporation, all rights reserved.
// ---------------------------------------------------------------------------

#include "framework.h"
#include "AEEngine.h"
#include "Audio.h"
#include "GameStateManager.h"
#include "object_data.h"
#include "Sprite.h"

#include "Menu.h"

//------------------------------------------------------------------------------
// Private Constants:
//------------------------------------------------------------------------------

//------------------------------------------------------------------------------
// Private Structures:
//------------------------------------------------------------------------------

//------------------------------------------------------------------------------
// Public Variables:
//------------------------------------------------------------------------------

//------------------------------------------------------------------------------
// Private Variables:
//------------------------------------------------------------------------------

static vec2 backgroundSize = { 1670.0f, 564.0f };
static vec2 buttonSize = { 100.0f, 30.0f };
static vec2 titleSize = { 150.0f, 50.0f };
static vec2 iconSize = { 30.0f, 30.0f };
static vec2 levelPos = { 0.0f, 0.0f };
static vec2 creditsPos = { 0.0f, -100.0f };
static vec2 exitPos = { 0.0f, -200.0f };
static vec2 titlePos = { 0.0f, 150.0f };

static signed long mouseX, mouseY;
static float mouseInWorldX, mouseInWorldY;

static AEGfxVertexList* buttonMesh;
static AEGfxVertexList* titleMesh;
static AEGfxVertexList* bgMesh;
static AEGfxVertexList* fontMesh;
static AEGfxVertexList* iconMesh;

static AEGfxTexture* bgTexture;
static AEGfxTexture* buttonTexture;
static AEGfxTexture* titleTexture;
static AEGfxTexture* fontTexture;
static AEGfxTexture* iconTexture;

TextureOffset titleOffsets[6];
int* currentTitleOffset = 0;
int currTitleFrame = 0;
float* titleTime;

static TextureOffset fontOffsets[30];
static int* currentfontOffset = 0;
static int currfontFrame = 0;
static float* fontTime;

static float bgMusicTimer;

//------------------------------------------------------------------------------
// Private Function Declarations:
//------------------------------------------------------------------------------

//------------------------------------------------------------------------------
// Public Functions:
//------------------------------------------------------------------------------

void MenuLoad()
{
    /*mesh for bg*/
    AEGfxMeshStart();

    AEGfxTriAdd(
        -backgroundSize.x, -backgroundSize.y, 0xFF00FF00, 0.0f, 1.0f,
        backgroundSize.x, -backgroundSize.y, 0xFF00FF00, 1.0f, 1.0f,
        -backgroundSize.x, backgroundSize.y, 0xFF00FF00, 0.0f, 0.0f);

    AEGfxTriAdd(
        backgroundSize.x, -backgroundSize.y, 0xFF00FF00, 1.0f, 1.0f,
        backgroundSize.x, backgroundSize.y, 0xFF00FF00, 1.0f, 0.0f,
        -backgroundSize.x, backgroundSize.y, 0xFF00FF00, 0.0f, 0.0f);

    bgMesh = AEGfxMeshEnd();
    AE_ASSERT_MESG(bgMesh, "Failed to create button!");

    bgTexture = AEGfxTextureLoad("Assets/CityscapeGrey.png");
    AE_ASSERT_MESG(bgTexture, "Failed to create pTex!!");

    /*mesh for buttons: green*/
    AEGfxMeshStart();

    AEGfxTriAdd(
        -buttonSize.x, -buttonSize.y, 0xFF00FF00, 0.0f, 1.0f,
        buttonSize.x, -buttonSize.y, 0xFF00FF00, 1.0f, 1.0f,
        -buttonSize.x, buttonSize.y, 0xFF00FF00, 0.0f, 0.0f);

    AEGfxTriAdd(
        buttonSize.x, -buttonSize.y, 0xFF00FF00, 1.0f, 1.0f,
        buttonSize.x, buttonSize.y, 0xFF00FF00, 1.0f, 0.0f,
        -buttonSize.x, buttonSize.y, 0xFF00FF00, 0.0f, 0.0f);

    buttonMesh = AEGfxMeshEnd();
    AE_ASSERT_MESG(buttonMesh, "Failed to create button!");

    buttonTexture = AEGfxTextureLoad("Assets/NookButtonBright.png");
    AE_ASSERT_MESG(buttonTexture, "Failed to create texture!");

    /*mesh for text*/
    AEGfxMeshStart();

    AEGfxTriAdd(
        -titleSize.x, -titleSize.y, 0xFF00FF00, 0.0f, 1.0f / 6,
        titleSize.x, -titleSize.y, 0xFF00FF00, 1.0f, 1.0f / 6,
        -titleSize.x, titleSize.y, 0xFF00FF00, 0.0f, 0.0f);

    AEGfxTriAdd(
        titleSize.x, -titleSize.y, 0xFF00FF00, 1.0f, 1.0f / 6,
        titleSize.x, titleSize.y, 0xFF00FF00, 1.0f, 0.0f,
        -titleSize.x, titleSize.y, 0xFF00FF00, 0.0f, 0.0f);

    titleMesh = AEGfxMeshEnd();
    AE_ASSERT_MESG(titleMesh, "Failed to create button!");

    titleTexture = AEGfxTextureLoad("Assets/NookLogo.png");
    AE_ASSERT_MESG(titleTexture, "Failed to create texture!");

    titleOffsets[0].mX = 0.0f;			titleOffsets[0].mY = 0.0f;
    titleOffsets[1].mX = 0.0f;			titleOffsets[1].mY = 1.0f / 6;
    titleOffsets[2].mX = 0.0f;			titleOffsets[2].mY = 2.0f / 6;
    titleOffsets[3].mX = 0.0f;			titleOffsets[3].mY = 3.0f / 6;
    titleOffsets[4].mX = 0.0f;			titleOffsets[4].mY = 4.0f / 6;
    titleOffsets[5].mX = 0.0f;			titleOffsets[5].mY = 5.0f / 6;

    /*mesh for hover icon*/
    iconMesh = createQuadMesh(iconSize.x, iconSize.y, 1.0f, 1.0f, "yarn");
    
    iconTexture = AEGfxTextureLoad("Assets/TempHover.png");
    AE_ASSERT_MESG(iconTexture, "Failed to create texture!");

    /*mesh for text*/
    fontMesh = createQuadMesh(15.0f, 15.0f, 1.0 / 5, 1.0f / 6, "alphabets");

    fontTexture = AEGfxTextureLoad("Assets/NookFontSheet_alphabet.png");
    AE_ASSERT_MESG(fontTexture, "Failed to create texture!");
        
    fontOffsets[0].mX = 0.0f;			    fontOffsets[0].mY = 0.0f / 6;  //A
    fontOffsets[1].mX = 1.0f / 5;		    fontOffsets[1].mY = 0.0f / 6;  //B
    fontOffsets[2].mX = 2.0f / 5;			fontOffsets[2].mY = 0.0f / 6;  //C
    fontOffsets[3].mX = 3.0f / 5;			fontOffsets[3].mY = 0.0f / 6;  //D
    fontOffsets[4].mX = 4.0f / 5;			fontOffsets[4].mY = 0.0f / 6;  //E

    fontOffsets[5].mX = 0.0f;			    fontOffsets[5].mY = 1.0f / 6;  //F
    fontOffsets[6].mX = 1.0f / 5;		    fontOffsets[6].mY = 1.0f / 6;  //G
    fontOffsets[7].mX = 2.0f / 5;			fontOffsets[7].mY = 1.0f / 6;  //H
    fontOffsets[8].mX = 3.0f / 5;			fontOffsets[8].mY = 1.0f / 6;  //I
    fontOffsets[9].mX = 4.0f / 5;			fontOffsets[9].mY = 1.0f / 6;  //J

    fontOffsets[10].mX = 0.0f;			    fontOffsets[10].mY = 2.0f / 6;  //K
    fontOffsets[11].mX = 1.0f / 5;		    fontOffsets[11].mY = 2.0f / 6;  //L
    fontOffsets[12].mX = 2.0f / 5;			fontOffsets[12].mY = 2.0f / 6;  //M
    fontOffsets[13].mX = 3.0f / 5;			fontOffsets[13].mY = 2.0f / 6;  //N
    fontOffsets[14].mX = 4.0f / 5;			fontOffsets[14].mY = 2.0f / 6;  //O

    fontOffsets[15].mX = 0.0f;			    fontOffsets[15].mY = 3.0f / 6;  //P
    fontOffsets[16].mX = 1.0f / 5;		    fontOffsets[16].mY = 3.0f / 6;  //Q
    fontOffsets[17].mX = 2.0f / 5;			fontOffsets[17].mY = 3.0f / 6;  //R
    fontOffsets[18].mX = 3.0f / 5;			fontOffsets[18].mY = 3.0f / 6;  //S
    fontOffsets[19].mX = 4.0f / 5;			fontOffsets[19].mY = 3.0f / 6;  //T

    fontOffsets[20].mX = 0.0f;			    fontOffsets[20].mY = 4.0f / 6;  //U
    fontOffsets[21].mX = 1.0f / 5;		    fontOffsets[21].mY = 4.0f / 6;  //V
    fontOffsets[22].mX = 2.0f / 5;			fontOffsets[22].mY = 4.0f / 6;  //W
    fontOffsets[23].mX = 3.0f / 5;			fontOffsets[23].mY = 4.0f / 6;  //X
    fontOffsets[24].mX = 4.0f / 5;			fontOffsets[24].mY = 4.0f / 6;  //Y


    fontOffsets[25].mX = 0.0f;			    fontOffsets[25].mY = 5.0f / 6;   //Z  
    fontOffsets[26].mX = 1.0f / 5;		    fontOffsets[26].mY = 5.0f / 6;  //blank
    fontOffsets[27].mX = 2.0f / 5;			fontOffsets[27].mY = 5.0f / 6;  //blank
    fontOffsets[28].mX = 3.0f / 5;			fontOffsets[28].mY = 5.0f / 6;  //blank
    fontOffsets[29].mX = 4.0f / 5;			fontOffsets[29].mY = 5.0f / 6;  //blank
}

void MenuInit()
{
	AEGfxSetBackgroundColor(0.0f, 0.0f, 0.0f);
    AEGfxSetBlendMode(AE_GFX_BM_BLEND);

    AudioInit();
    bgMusicTimer = 1638.0f; // Roughly 27 seconds
}

void MenuUpdate(float dt)
{
	/* Tell the compiler that the 'dt' variable is unused. */
	UNREFERENCED_PARAMETER(dt);

    /*play bg music*/
    if (bgMusicTimer == 1638.0f)
    {
        playSoundAdvanced("Assets/Sounds/Level2Track.mp3", 0.1f);
    }
        
    /*reset time for bg music loop*/
    if (bgMusicTimer == 0.0f)
    {
        bgMusicTimer = 1638.0f;
    }
    else
    {
        bgMusicTimer--;
    }

    /*draw background*/
    AEGfxSetRenderMode(AE_GFX_RM_TEXTURE);
    AEGfxTextureSet(bgTexture, 0, 0);
    AEGfxSetTransparency(1.0f);
    AEGfxSetPosition(-250.0f, 0.0f);
    AEGfxMeshDraw(bgMesh, AE_GFX_MDM_TRIANGLES);
    
    //draw menu button
    AEGfxSetPosition(levelPos.x, levelPos.y);
    AEGfxTextureSet(buttonTexture, 0, 0); // no texture
    AEGfxSetTransparency(1.0f);
    AEGfxSetBlendColor(0.0f, 0.0f, 0.0, 0.0f);
    AEGfxMeshDraw(buttonMesh, AE_GFX_MDM_TRIANGLES);

    //draw replay button
    AEGfxSetPosition(creditsPos.x, creditsPos.y);
    AEGfxTextureSet(buttonTexture, 0, 0); // no texture
    AEGfxMeshDraw(buttonMesh, AE_GFX_MDM_TRIANGLES);

    //draw exit button
    AEGfxSetPosition(exitPos.x, exitPos.y);
    AEGfxTextureSet(buttonTexture, 0, 0); // no texture
    AEGfxMeshDraw(buttonMesh, AE_GFX_MDM_TRIANGLES);

    /*PLAY*/

    AEGfxSetPosition(levelPos.x - 40.0f, levelPos.y);
    AEGfxTextureSet(fontTexture, fontOffsets[15].mX, fontOffsets[15].mY, 0.0f);
    AEGfxMeshDraw(fontMesh, AE_GFX_MDM_TRIANGLES);

    AEGfxSetPosition(levelPos.x - 15.0f, levelPos.y);
    AEGfxTextureSet(fontTexture, fontOffsets[11].mX, fontOffsets[11].mY, 0.0f);
    AEGfxMeshDraw(fontMesh, AE_GFX_MDM_TRIANGLES);

    AEGfxSetPosition(levelPos.x + 10.0f, levelPos.y);
    AEGfxTextureSet(fontTexture, fontOffsets[0].mX, fontOffsets[0].mY, 0.0f);
    AEGfxMeshDraw(fontMesh, AE_GFX_MDM_TRIANGLES);

    AEGfxSetPosition(levelPos.x + 35.0f, levelPos.y);
    AEGfxTextureSet(fontTexture, fontOffsets[24].mX, fontOffsets[24].mY, 0.0f);
    AEGfxMeshDraw(fontMesh, AE_GFX_MDM_TRIANGLES);

    /*PLAY - end*/

    /*CREDITS*/
    AEGfxSetPosition(creditsPos.x - 75.0f, creditsPos.y);
    AEGfxTextureSet(fontTexture, fontOffsets[2].mX, fontOffsets[2].mY, 0.0f);
    AEGfxMeshDraw(fontMesh, AE_GFX_MDM_TRIANGLES);

    AEGfxSetPosition(creditsPos.x - 45.0f, creditsPos.y);
    AEGfxTextureSet(fontTexture, fontOffsets[17].mX, fontOffsets[17].mY, 0.0f);
    AEGfxMeshDraw(fontMesh, AE_GFX_MDM_TRIANGLES);

    AEGfxSetPosition(creditsPos.x - 20.0f, creditsPos.y);
    AEGfxTextureSet(fontTexture, fontOffsets[4].mX, fontOffsets[4].mY, 0.0f);
    AEGfxMeshDraw(fontMesh, AE_GFX_MDM_TRIANGLES);

    AEGfxSetPosition(creditsPos.x + 5.0f, creditsPos.y);
    AEGfxTextureSet(fontTexture, fontOffsets[3].mX, fontOffsets[3].mY, 0.0f);
    AEGfxMeshDraw(fontMesh, AE_GFX_MDM_TRIANGLES);

    AEGfxSetPosition(creditsPos.x + 25.0f, creditsPos.y);
    AEGfxTextureSet(fontTexture, fontOffsets[8].mX, fontOffsets[8].mY, 0.0f);
    AEGfxMeshDraw(fontMesh, AE_GFX_MDM_TRIANGLES);

    AEGfxSetPosition(creditsPos.x + 47.0f, creditsPos.y);
    AEGfxTextureSet(fontTexture, fontOffsets[19].mX, fontOffsets[19].mY, 0.0f);
    AEGfxMeshDraw(fontMesh, AE_GFX_MDM_TRIANGLES);

    AEGfxSetPosition(creditsPos.x + 75.0f, creditsPos.y);
    AEGfxTextureSet(fontTexture, fontOffsets[18].mX, fontOffsets[18].mY, 0.0f);
    AEGfxMeshDraw(fontMesh, AE_GFX_MDM_TRIANGLES);

    /*CREDITS - end*/

    /*QUIT*/
    AEGfxSetPosition(exitPos.x - 40.0f, exitPos.y);
    AEGfxTextureSet(fontTexture, fontOffsets[16].mX, fontOffsets[16].mY, 0.0f);
    AEGfxMeshDraw(fontMesh, AE_GFX_MDM_TRIANGLES);

    AEGfxSetPosition(exitPos.x - 7.5f, exitPos.y);
    AEGfxTextureSet(fontTexture, fontOffsets[20].mX, fontOffsets[20].mY, 0.0f);
    AEGfxMeshDraw(fontMesh, AE_GFX_MDM_TRIANGLES);

    AEGfxSetPosition(exitPos.x + 17.5f, exitPos.y);
    AEGfxTextureSet(fontTexture, fontOffsets[8].mX, fontOffsets[8].mY, 0.0f);
    AEGfxMeshDraw(fontMesh, AE_GFX_MDM_TRIANGLES);

    AEGfxSetPosition(exitPos.x + 40.0f, exitPos.y);
    AEGfxTextureSet(fontTexture, fontOffsets[19].mX, fontOffsets[19].mY, 0.0f);
    AEGfxMeshDraw(fontMesh, AE_GFX_MDM_TRIANGLES);

    /*QUIT - end*/

    animateFrames(&currentTitleOffset, &titleTime, 0.25f, dt);
    checkEndFrames(&currentTitleOffset, 6);
    currTitleFrame = currentTitleOffset;

    /*draw player*/
    AEGfxSetRenderMode(AE_GFX_RM_TEXTURE);
    AEGfxSetPosition(titlePos.x, titlePos.y);
    AEGfxTextureSet(titleTexture, titleOffsets[currTitleFrame].mX, titleOffsets[currTitleFrame].mY);
    AEGfxSetTransparency(1.0f);
    AEGfxMeshDraw(titleMesh, AE_GFX_MDM_TRIANGLES);

    /*get the mouse position*/
    AEInputGetCursorPosition(&mouseX, &mouseY);
    AEGfxConvertScreenCoordinatesToWorld(mouseX, mouseY, &mouseInWorldX, &mouseInWorldY);

    /*if demo level is hovered*/
    if ((mouseInWorldX > (levelPos.x - buttonSize.x) && mouseInWorldX < (levelPos.x + buttonSize.x)) &&
        (mouseInWorldY > (levelPos.y - buttonSize.y) && mouseInWorldY < (levelPos.y + buttonSize.y)))
    {
        // Hover texture
        AEGfxSetRenderMode(AE_GFX_RM_TEXTURE);
        AEGfxSetPosition(levelPos.x - 140.0f, levelPos.y);
        AEGfxTextureSet(iconTexture, 0.0f, 0.0f);
        AEGfxMeshDraw(iconMesh, AE_GFX_MDM_TRIANGLES);

        if (AEInputCheckTriggered(RI_MOUSE_LEFT_BUTTON_DOWN))
        {
            GameStateManagerSetNextState(LevelSelect);
        }
    }
    /*if credits is hovered*/
    if ((mouseInWorldX > (creditsPos.x - buttonSize.x) && mouseInWorldX < (creditsPos.x + buttonSize.x)) &&
        (mouseInWorldY > (creditsPos.y - buttonSize.y) && mouseInWorldY < (creditsPos.y + buttonSize.y)))
    {
        // Hover texture
        AEGfxSetRenderMode(AE_GFX_RM_TEXTURE);
        AEGfxSetPosition(creditsPos.x - 140.0f, creditsPos.y);
        AEGfxTextureSet(iconTexture, 0.0f, 0.0f);
        AEGfxMeshDraw(iconMesh, AE_GFX_MDM_TRIANGLES);

        if (AEInputCheckTriggered(RI_MOUSE_LEFT_BUTTON_DOWN))
        {
            GameStateManagerSetNextState(Credits);
        }
    }

    /*if exit is hovered*/
    if ((mouseInWorldX > (exitPos.x - buttonSize.x) && mouseInWorldX < (exitPos.x + buttonSize.x)) &&
        (mouseInWorldY > (exitPos.y - buttonSize.y) && mouseInWorldY < (exitPos.y + buttonSize.y)))
    {
        // Hover texture
        AEGfxSetRenderMode(AE_GFX_RM_TEXTURE);
        AEGfxSetPosition(exitPos.x - 140.0f, exitPos.y);
        AEGfxTextureSet(iconTexture, 0.0f, 0.0f);
        AEGfxMeshDraw(iconMesh, AE_GFX_MDM_TRIANGLES);

        if (AEInputCheckTriggered(RI_MOUSE_LEFT_BUTTON_DOWN))
        {
            GameStateManagerSetNextState(GsQuit);
        }
    }
}

void MenuShutdown()
{
    // Do not cleanup audio so music continues into credits and level select
}

void MenuUnload()
{
	// Unload all textures.
    AEGfxTextureUnload(buttonTexture);
    AEGfxTextureUnload(titleTexture);
    AEGfxTextureUnload(bgTexture);
    AEGfxTextureUnload(fontTexture);
    AEGfxTextureUnload(iconTexture);

    // Free all meshes.
    AEGfxMeshFree(buttonMesh);
    AEGfxMeshFree(titleMesh);
    AEGfxMeshFree(bgMesh);
    AEGfxMeshFree(fontMesh);
    AEGfxMeshFree(iconMesh);
}

// ---------------------------------------------------------------------------
// Project Name		:	Nook
// File Name		:	Mesh.c
// Author			:	Mary Khuu
// Creation Date	:	19 Feb 2021
// Purpose			:	Deals with all things needed for sprites
// All content © 2021 DigiPen (USA) Corporation, all rights reserved.
// ---------------------------------------------------------------------------

#include "Sprite.h"


//function to create a quadratic mesh
AEGfxVertexList* createQuadMesh(float halfSizeX, float halfSizeY, float u, float v, const char* meshName)
{
	AEGfxVertexList* mesh;

	AEGfxMeshStart();

	AEGfxTriAdd(
		-halfSizeX, -halfSizeY, 0x00FFFFFF, 0.0f, v,
		 halfSizeX, -halfSizeY, 0x00FFFFFF, u, v,
		-halfSizeX, halfSizeY, 0x00FFFFFF, 0.0f, 0.0f);
	AEGfxTriAdd(
		 halfSizeX, -halfSizeY, 0x00FFFFFF, u, v,
		 halfSizeX, halfSizeY, 0x00FFFFFF, u, 0.0f,
		-halfSizeX, halfSizeY, 0x00FFFFFF, 0.0f, 0.0f);

	mesh = AEGfxMeshEnd();
	AE_WARNING_MESG(mesh, "Failed to create %s!", meshName);

	if (mesh != 0)
	{
		return mesh;
	}
	else
	{
		return 0;
	}
}

//same as above but less parameters, assume halfsize is the same in x and y and u = v
AEGfxVertexList* createEqualQuadMesh(float halfSize, float uv, const char* meshName)
{
	AEGfxVertexList* mesh;

	AEGfxMeshStart();

	AEGfxTriAdd(
		-halfSize, -halfSize, 0x00FFFFFF, 0.0f, uv,
		halfSize, -halfSize, 0x00FFFFFF, uv, uv,
		-halfSize, halfSize, 0x00FFFFFF, 0.0f, 0.0f);
	AEGfxTriAdd(
		halfSize, -halfSize, 0x00FFFFFF, uv, uv,
		halfSize, halfSize, 0x00FFFFFF, uv, 0.0f,
		-halfSize, halfSize, 0x00FFFFFF, 0.0f, 0.0f);

	mesh = AEGfxMeshEnd();
	AE_WARNING_MESG(mesh, "Failed to create %s!", meshName);

	if (mesh != 0)
	{
		return mesh;
	}
	else
	{
		return 0;
	}
}

int getMaxFrames(int rows, int columns)
{
	return rows * columns;
}

void animateFrames(int* currentFrame, float* time, float frameDelay, float dt)
{
	(*time) += dt;

	if (*time >= frameDelay)
	{
		(*currentFrame)++;
		*time = 0;
	}
}

void checkEndFrames(int* currentFrame, int maxFrame)
{
	if (*currentFrame >= maxFrame)
	{
		*currentFrame = 0;
	}
}

// ---------------------------------------------------------------------------
// Project Name		:	Nook
// File Name		:	Audio.c
// Author			:	Mary Khuu
// Creation Date	:	15 Mar 2021
// Purpose			:	add audio to the game
// All content © 2021 DigiPen (USA) Corporation, all rights reserved.
// ---------------------------------------------------------------------------

#include "fmod.h"
#include <stdio.h>		// printf()
#include <stdbool.h>	// FALSE
#include "AEEngine.h"

#include "Audio.h"

FMOD_SYSTEM* soundSystem;
FMOD_SOUND* sound;
FMOD_CHANNEL* channel;
FMOD_RESULT result;


// Initialize the Audio System
void AudioInit()
{
	channel = 0;

	// Create and Initialize the FMOD System
	result = FMOD_System_Create(&soundSystem);

	void* extradriverdata = 0;
	result = FMOD_System_Init(soundSystem, 32, FMOD_INIT_NORMAL, extradriverdata);
}

void playSound(bool trigger, const char* file)
{
	// Create and Play the sound
	// Note: this should be generalized for multiple sounds and
	//       be placed in a function to be used outside of init.
	result = FMOD_System_CreateStream(soundSystem, file, FMOD_LOOP_OFF | FMOD_2D, 0, &sound);

	result = FMOD_System_PlaySound(soundSystem, sound, 0, trigger, &channel);
	
}

void playSoundAdvanced(const char* file, float volume)
{
	FMOD_CHANNEL* channel;

	result = FMOD_System_CreateStream(soundSystem, file, FMOD_LOOP_OFF | FMOD_2D, 0, &sound);

	result = FMOD_System_PlaySound(soundSystem, sound, 0, true, &channel);

	result = FMOD_Channel_SetVolume(channel, volume);

	result = FMOD_Channel_SetPaused(channel, false);
}

// Update the Audio System
// Note: this should be called frequently such as every game loop or
//       every time a user enters a command depending on the engine
void AudioUpdate()
{
	result = FMOD_System_Update(soundSystem);
}

// Cleanup the Audio System
void AudioCleanup()
{
	// Release all sounds that have been created
	result = FMOD_Sound_Release(sound);

	// Close and Release the FMOD system
	result = FMOD_System_Close(soundSystem);
	result = FMOD_System_Release(soundSystem);
}

#include <pch.h>
#include "Projects/ProjectTwo.h"
#include "P2_Pathfinding.h"

#pragma region Extra Credit

std::list<AStarPather::Node*> list;
AStarPather::Node map[61][61];

bool ProjectTwo::implemented_floyd_warshall()
{
    return false;
}

bool ProjectTwo::implemented_goal_bounding()
{
    return false;
}

bool ProjectTwo::implemented_jps_plus()
{
    return false;
}
#pragma endregion

bool AStarPather::initialize()
{
    // handle any one-time setup requirements you have

    /*
        If you want to do any map-preprocessing, you'll need to listen
        for the map change message.  It'll look something like this:

        Callback cb = std::bind(&AStarPather::your_function_name, this);
        Messenger::listen_for_message(Messages::MAP_CHANGE, cb);

        There are other alternatives to using std::bind, so feel free to mix it up.
        Callback is just a typedef for std::function<void(void)>, so any std::invoke'able
        object that std::function can wrap will suffice.
    */

    return true; // return false if any errors actually occur, to stop engine initialization
}

void AStarPather::shutdown()
{
    /*
        Free any dynamically allocated memory or any other general house-
        keeping you need to do during shutdown.
    */
}
/*
    This is where you handle pathing requests, each request has several fields:

    start/goal - start and goal world positions
    path - where you will build the path upon completion, path should be
        start to goal, not goal to start
    heuristic - which heuristic calculation to use
    weight - the heuristic weight to be applied
    newRequest - whether this is the first request for this path, should generally
        be true, unless single step is on

    smoothing - whether to apply smoothing to the path
    rubberBanding - whether to apply rubber banding
    singleStep - whether to perform only a single A* step
    debugColoring - whether to color the grid based on the A* state:
        closed list nodes - yellow
        open list nodes - blue

        use terrain->set_color(row, col, Colors::YourColor);
        also it can be helpful to temporarily use other colors for specific states
        when you are testing your algorithms

    method - which algorithm to use: A*, Floyd-Warshall, JPS+, or goal bounding,
        will be A* generally, unless you implement extra credit features

    The return values are:
        PROCESSING - a path hasn't been found yet, should only be returned in
            single step mode until a path is found
        COMPLETE - a path to the goal was found and has been built in request.path
        IMPOSSIBLE - a path from start to goal does not exist, do not add start position to path
*/
PathResult AStarPather::compute_path(PathRequest &request)
{

    //start/goal - start and goal world positions
    GridPos start = terrain->get_grid_position(request.start);
    GridPos goal = terrain->get_grid_position(request.goal);

    terrain->set_color(start, Colors::Red);
    //set color to orange
    terrain->set_color(goal, Colors::Red);

    //request.path.push_back(request.start);


/***********************************A* SEARCH ALGORITHM*********************************/
    //Push Start Node onto the Open List.

    if (request.newRequest)
    {
        for (int i = 0; i <= 40; i++)
        {
            for (int j = 0; j <= 40; j++)
            {
                map[i][j].parent = NULL;
                map[i][j].pos = GridPos{j, i};
                map[i][j].onList_ = onList::NONE;
                map[i][j].cost = 0.0f;
                map[i][j].given = 0.0f;
            }
        }
        list.clear();
        list.push_back(&map[start.col][start.row]);
    }

    //While (Open List is not empty) {
    while (!list.empty())
    {
        //Pop cheapest node off Open List (parent node).
        Node* parentNode = findCheapest(list);
        
        std::list<Node*>::iterator it;
        it = list.begin();
        std::advance(it, findNodeIndex(list, parentNode));
        it = list.erase(it);

        //request.path.push_back(terrain->get_world_position(parentNode->pos));
        //If node is the Goal Node, then path found (RETURN �found�).
        if (parentNode->pos == goal)
        {
 //////////////////////////////////////////////////////////////////////////////////////////////////////////////
            Node* cur = parentNode;
            while (cur) {
                //push request
                request.path.push_front(terrain->get_world_position(cur->pos));
                //go to next parent
                cur = cur->parent;
            }
//////////////////////////////////////////////////////////////////////////////////////////////////////////////

            terrain->set_color(start, Colors::Orange);
            terrain->set_color(goal, Colors::Orange);
            return PathResult::COMPLETE;
        }

        
        bool NW = true;
        bool NE = true;
        bool SE = true;
        bool SW = true;

        //For (all neighboring child nodes)
        for (int i = 1; i <= 8; i++)
        {
            //set parent to parent
            GridPos childPos = getChild(parentNode->pos, i); //get child
            //deleted line
//////////////////////////////////////////////////////////////////////////////////////////////////////////////
            //Node* oldParent = map[childPos.col][childPos.row].parent;

            if (childPos != parentNode->pos)
            {
                //set map's parent to new parent after getting position
                //map[childNode->pos.col][childNode->pos.row].parent = &map[parentNode->pos.col][parentNode->pos.row];
                
                //grid is on the map and isn't a wall
                if (terrain->is_valid_grid_position(childPos) && !terrain->is_wall(childPos))
                {
                    //i is non diagonals or is a valid diagonal
                    if (i <= 4 || (i == 5 && NE) || (i == 6 && SE) || (i == 7 && SW) || (i == 8 && NW))
                    {
                        //Compute its cost, f(x) = g(x) + h(x)
//////////////////////////////////////////////////////////////////////////////////////////////////////////////
                        float given = parentNode->given;
                        if (i >= 4)
                        {
                            //tile is a diagonal
                            given += (float)std::sqrt(2);
                            //map[childPos.col][childPos.row].given = map[parentNode->pos.col][parentNode->pos.row].given + (float)std::sqrt(2);
                        }
                        else
                        {
                            //tile is N, S, W, E
                            given += 1;
                            //map[childPos.col][childPos.row].given = map[parentNode->pos.col][parentNode->pos.row].given + 1;
                        }

                        float h = getHeuristic(request.settings.heuristic, childPos, goal);
                        //map[childPos.col][childPos.row].cost = map[parentNode->pos.col][parentNode->pos.row].given + h * request.settings.weight;
                        float newCost = given + h * request.settings.weight;
//////////////////////////////////////////////////////////////////////////////////////////////////////////////

                        //find if child exists on curr list, and assign it
                        map[parentNode->pos.col][parentNode->pos.row].onList_ = assignList(list, map[parentNode->pos.col][parentNode->pos.row].pos);

                        //If child node isn't on Open or Closed list, put it on Open List.
                        if (map[childPos.col][childPos.row].onList_ == onList::NONE)
                        {
////////////////////////////////////////////////////////////////////////////////////////////////////////////
                            map[childPos.col][childPos.row].parent = parentNode;
                            map[childPos.col][childPos.row].given = given;
                            map[childPos.col][childPos.row].cost = newCost;
////////////////////////////////////////////////////////////////////////////////////////////////////////////
                            map[childPos.col][childPos.row].onList_ = onList::OPEN;
                            terrain->set_color(childPos, Colors::Blue);
                            list.push_back(&map[childPos.col][childPos.row]);
                        }
                        //Else if child node is on Open or Closed List,
                        else if (map[childPos.col][childPos.row].onList_ == onList::OPEN || map[childPos.col][childPos.row].onList_ == onList::CLOSE)
                        {
                            //AND this new one is cheaper,
                            //then take the old expensive one off both lists
                            //if oldCost == 0 then it's our first time setting it
                            if (map[childPos.col][childPos.row].cost > newCost)
                            {
                                //and put this new cheaper one on the Open List.
////////////////////////////////////////////////////////////////////////////////////////////////////////////
                                map[childPos.col][childPos.row].parent = parentNode;
                                map[childPos.col][childPos.row].given = given;
                                map[childPos.col][childPos.row].cost = newCost;
////////////////////////////////////////////////////////////////////////////////////////////////////////////
                                map[childPos.col][childPos.row].onList_ = onList::OPEN;
                                terrain->set_color(childPos, Colors::Blue);
                                list.push_back(&map[childPos.col][childPos.row]);
                            }
                            /*
                            else
                            {
                                map[childPos.col][childPos.row].cost = oldCost;
                                map[childPos.col][childPos.row].parent = oldParent;
                            }*/
                        }
                    }
                }
                //grid is valid but the non-diagonals is a wall, skip the diagonals
                else if (terrain->is_valid_grid_position(childPos) && terrain->is_wall(childPos) && i <= 4)
                {
                    if (i == 1) //NORTH
                    {
                        NE = false;
                        NW = false;
                    }

                    if (i == 2) //EAST
                    {
                        NE = false;
                        SE = false;
                    }

                    if (i == 3) //SOUTH
                    {
                        SE = false;
                        SW = false;
                    }

                    if (i == 4) //WEST
                    {
                        SW = false;
                        NW = false;
                    }
                }
            }
        }

/***************************************************************************************************************/
        //Place parent node on the Closed List (we're done with it).
        parentNode->onList_ = onList::CLOSE;
        map[parentNode->pos.col][parentNode->pos.row].onList_ = onList::CLOSE;
        terrain->set_color(parentNode->pos, Colors::Yellow);
        map[parentNode->pos.col][parentNode->pos.row] = *parentNode;
        //If taken too much time this frame (or in single step mode), 
        if (request.settings.singleStep == true)
        {
            //abort search for now and resume next frame (RETURN �working�).
            return PathResult::PROCESSING;
        }
    }
    //Open List empty, thus no path possible (RETURN �fail�).
    return PathResult::IMPOSSIBLE;

}

float AStarPather::getHeuristic(Heuristic method, GridPos position, GridPos goal)
{
    float dx = (float)std::fabs(position.row - goal.row);
    float dy = (float)std::fabs(position.col - goal.col);

    if (method == Heuristic::OCTILE)
    {
        return 1 * (dx + dy) + (float)(sqrt(2) - 2 * 1) * std::min(dx, dy);
    }

    if (method == Heuristic::CHEBYSHEV)
    {
        return 1 * (dx + dy) + (1 - 2 * 1) * std::min(dx, dy);
    }  

    if (method == Heuristic::MANHATTAN)
    {
        return dx + dy;
    }

    if (method == Heuristic::EUCLIDEAN)
    {
        return (float)sqrt(dx * dx + dy * dy);
    }

    return 0.0f;
}

AStarPather::onList AStarPather::assignList(std::list<Node*> list, GridPos position)
{
    //go through list
    for (const Node* node : list)
    {
        //if node exists in list
        //and is labeled as open
        if (node->pos == position && node->onList_ == onList::OPEN)
        {
            //return open
            return onList::OPEN;
        }
        //and is labeled as closed
        if (node->pos == position && node->onList_ == onList::CLOSE)
        {
            //return closed
            return onList::CLOSE;
        }
        //and is labeled as none
        if (node->pos == position && node->onList_ == onList::NONE)
        {
            return onList::NONE;
        }
    }

    //else it's not on either list
    return onList::NONE;
}

GridPos AStarPather::getChild(GridPos node, int i)
{
    GridPos pos;
    if (i == 1) //NORTH
    {
        pos = { node.row + 1, node.col};
    }
    else if (i == 5) //NE
    {
        pos = { node.row + 1, node.col + 1 };
    }
    else if (i == 2) //EAST
    {
        pos = { node.row, node.col + 1};
    }
    else if (i == 6) //SE
    {
        pos = { node.row - 1, node.col + 1 };
    }
    else if (i == 3) //SOUTH
    {
        pos = { node.row - 1, node.col };
    }
    else if (i == 7) //SW
    {
        pos = { node.row - 1, node.col - 1 };
    }
    else if (i == 4) //WEST
    {
        pos = { node.row, node.col - 1};
    }
    else if (i == 8) //NW
    {
        pos = { node.row + 1, node.col - 1};
    }

    return pos;
}

AStarPather::Node* AStarPather::findCheapest(std::list<Node*> list)
{
    Node* cheapestNode;
    float minCost = -1.0f;
    for (Node* node : list)
    {
        if ((node->cost < minCost || minCost == -1.0f) && node->onList_ != onList::CLOSE)
        {
            //is a valid node
            if (terrain->is_valid_grid_position(node->pos) && node->cost >= 0.0f)
            {
                cheapestNode = node;
//////////////////////////////////////////////////////////////////////////////////////////////////////////////
                minCost = cheapestNode->cost;
            }
        }
    }

    return cheapestNode;
}

int AStarPather::findNodeIndex(std::list<Node*> list, Node* node)
{
    int i = 0;
    int index = 0;
    for (Node* node_ : list)
    {
        if (node_->pos == node->pos)
        {
                index = i;
        }
        i++;
    }

    return index;
}

  //Challenge Solution - Part #2
  else if (digitalRead(sw2Pin) == HIGH) {
    delay(250);
    flipSwitch(sw2Pos);
  } 

  // Challenge Solution - Part #1
  // Cascading "if" statement to turn switches "ON" if they are "OFF"
  // The PULLUP configuration means that a "LOW" signal equals the switch being "ON",
  // while a "HIGH" signal equals the switch being in the "OFF" position
  if (digitalRead(sw1Pin) == HIGH) {
    delay(250);
    flipSwitch(sw1Pos);
  } 

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

void solve(){
   
}

int main(){
    int t;
    cin>>t;
    while(t-->0){
        solve();
    }
    return 0;
}

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

int main(){
    int t;
    cin>>t;
    while(t-->0){
    
    }
    return 0;
}

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

int main(){
  
  return 0;
}

// C++ code to find count of largest consectutive subset
#include <iostream>
#include <stdlib.h>
#include <unordered_set>
using namespace std;

int main() {
    int sz, num;
    unordered_set<int> numbers;
    int maxLen = 0;
    cin>>sz;
    for (int i=0;i<sz;i++) {
        cin>>num;
        numbers.insert(num);
    }
    
    for (int i : numbers) {
        if (numbers.find(i-1) == numbers.end()) {
            int temp = i;
            while (numbers.find(temp) != numbers.end()) temp++;
            
            if (maxLen < (temp-i)) maxLen = temp-i;
        }
    }

    cout<< maxLen;
    return 0;
}

# Makefile

SRC := $(wildcard *.cpp) $(wildcard *.cc) $(wildcard *.c)
OBJ := $(SRC:.cpp=.o) $(SRC:.cc=.o) $(SRC:.c=.o)
TARGET := my_program

CXX := /opt/homebrew/opt/ccache/libexec/g++
CXXFLAGS := -fdiagnostics-color=always -g -Wall -std=c++20

$(TARGET): $(OBJ)
    $(CXX) $(CXXFLAGS) -o $@ $^

clean:
    rm -f $(OBJ) $(TARGET)

#include <iostream>
#include<cstring>
#include<memory>

using namespace std;

bool isValid (string customerNumber) {
    if (customerNumber.length() != 6)
        return false;

    for(int i = 0; i < 2; i++)
    if (!isalpha(customerNumber[i]))
        return false;

   for (int i = 2; i < customerNumber.length(); i++)
       if(!isdigit(customerNumber[i]))
           return false;

   return true;
}

int main() {

    string cust_number = "AB1234";
    cout << isValid(cust_number);
  return 0;
}

#include <iostream>


using namespace std;


int main() {

    int numbers[] = {10,20,30};
    int* ptrNumbers = &numbers[size(numbers) - 1];

    while (ptrNumbers >= &numbers[0]) {//or (ptrNumbers >= numbers)
            cout << *ptrNumbers <<endl;
            ptrNumbers--;
    }
    return 0;
}

#include <iostream>


using namespace std;

void increasePrice(double& price) {
    price *= 1.2;

}
int main() {

    double price = 100;
    increasePrice(price);
    cout << price;

    return 0;
}

#include <iostream>


using namespace std;

int main() {

    int number = 10;
    int* ptr = &number; // The address of operator
    *ptr = 20; // Indirection (de-referencing) operator
    cout << number;
    
    return 0;
}

#include <iostream>


using namespace std;

int main() {

   int firstArray[] = {10,20,30,40};
   int secondArray[] = {10,20,30,40};

   bool areEqual = true;
   for (int i = 0; i<size(firstArray); i++)
       if(firstArray[i] != secondArray[i]) {
           areEqual = false;
            break;
       }
cout << boolalpha << areEqual;

#include <iostream>


using namespace std;

int main() {

   int firstArray[] = {10,20,30,40};
   int secondArray[size(firstArray)];

   for (int i = 0; i < size(firstArray); i++)
       secondArray[i] = firstArray[i];

   for (int number: secondArray)
       cout << number << endl;


    return 0;

}

#include <iostream>
using namespace std;

int main() {

    cout << "Enter a positive number: ";
    int number;
    cin >> number;

    if (number < 0)
        cout << "Error! Number is not positive";
    else {
        int factorial = 1;
        for (int i = 1; i<=number; i++)
             factorial = factorial * i;  // factorial *= i
        cout << "The factorial of " << number << ": " << factorial;
    }


    return 0;
}

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

typedef long long ll;
typedef double dl;

#define endl "\n"
#define optimize() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define fraction() cout.unsetf(ios::floatfield); cout.precision(10); cout.setf(ios::fixed,ios::floatfield);

int main()
{
   int n;
   cin>>n;
   int arr[n];int b[n];
   int max=0;
   for(int i=0;i<n;i++){
cin>>arr[i];
if(arr[i]>max)max=arr[i];
   }
int count_arr[max+1];
for(int i=0;i<=max;i++){
count_arr[i]=0;
}
for(int i=0;i<n;i++){
count_arr[arr[i]]++;
}
for(int i=1;i<=max;i++){
count_arr[i]=count_arr[i]+count_arr[i-1];
}
for(int i=n-1;i>=0;i--){
    b[--count_arr[arr[i]]]=arr[i];
}
for(int i=0;i<n;i++){
    cout<<b[i]<<" ";
}
       return 0;
}

    int n;
    cin >> n;
    string s;
    cin >> s;
    for (char c = 'A'; c <= 'Z'; c++) {
        int first = n;
        int last = -1;
        for (int i = 0; i < n; i++) {
            if (s[i] == c) {
                first = min(first, i);
                last = max(last, i);
            }
        }
        for (int i = first; i <= last; i++) {
            if (s[i] != c) {
                cout << "NO\n";
                return;
            }
        }
    }
    cout << "YES\n";

        score = score + 10 - time_to_press/100;

        score = score + 1 + time_to_press/100;

    // Challenge Solution Part 5: Add 1 bonus point for every tenth of a second under 1.0 seconds
    // Keep in mind that 1 second is equal to 1,000 milliseconds
    if(time_to_press < 1000){
        score = score + 5;
    }

      //Challenge Solution Part 4: Calculate the difference in time between the row becoming active and the button press.
      time_to_press = millis() - time_start;

    //Challenge Solution Part 3: Start the timer for this row being active
    time_start = millis();

//{ Driver Code Starts
// C++ program to remove recurring digits from
// a given number
#include <bits/stdc++.h>
using namespace std;


// } Driver Code Ends
    

class Solution{
    //Function to find the leaders in the array.
    public:
    vector<int> leaders(int a[], int n)
    {
        vector<int>ans;
      for(int i=0 ; i<n ; i++)
      {
          int j;
          for( j=i+1 ; j<n ; j++)
          {
              if(a[i]<a[j])
              {
                  break;
              }
            
          }
           if(j==n)
              {
                  ans.push_back(a[i]);
              }
      }
    return ans;
        
    }
};

//{ Driver Code Starts.

int main()
{
   long long t;
   cin >> t;//testcases
   while (t--)
   {
       long long n;
       cin >> n;//total size of array
        
        int a[n];
        
        //inserting elements in the array
        for(long long i =0;i<n;i++){
            cin >> a[i];
        }
        Solution obj;
        //calling leaders() function
        vector<int> v = obj.leaders(a, n);
        
        //printing elements of the vector
        for(auto it = v.begin();it!=v.end();it++){
            cout << *it << " ";
        }
        
        cout << endl;

   }
}

// } Driver Code Ends



//{ Driver Code Starts
// C++ program to remove recurring digits from
// a given number
#include <bits/stdc++.h>
using namespace std;


// } Driver Code Ends
    

class Solution{
    //Function to find the leaders in the array.
    public:
   vector<int> leaders(int a[], int n)
    {
        vector<int>v;
        int maxi=INT_MIN;
        for(int i=n-1 ; i>=0 ; i--)
        {
            if(a[i]>=maxi)
            {
                maxi=a[i];
                v.push_back(maxi);
            }
        }
        reverse(v.begin(),v.end());
        return v;
    }
};

//{ Driver Code Starts.

int main()
{
   long long t;
   cin >> t;//testcases
   while (t--)
   {
       long long n;
       cin >> n;//total size of array
        
        int a[n];
        
        //inserting elements in the array
        for(long long i =0;i<n;i++){
            cin >> a[i];
        }
        Solution obj;
        //calling leaders() function
        vector<int> v = obj.leaders(a, n);
        
        //printing elements of the vector
        for(auto it = v.begin();it!=v.end();it++){
            cout << *it << " ";
        }
        
        cout << endl;

   }
}

// } Driver Code Ends

//{ Driver Code Starts
#include <iostream>
using namespace std;


// } Driver Code Ends
class Solution{
    public:
    // Function to find equilibrium point in the array.
    // a: input array
    // n: size of array
    int equilibriumPoint(long long a[], int n) 
    {
        int i=0;
        int curr=0;
        int sum=0;
        for(int i=0 ; i<n ; i++)
        {
            sum+=a[i];
        }
        while(i<n)
        {
            curr+=a[i];
            if(curr==sum)
            {
                return i+1;
            }
            else
            {
                sum-=a[i];
            }
            i++;
        }
        return -1;
    }

};

//{ Driver Code Starts.


int main() {

    long long t;
    
    //taking testcases
    cin >> t;

    while (t--) {
        long long n;
        
        //taking input n
        cin >> n;
        long long a[n];

        //adding elements to the array
        for (long long i = 0; i < n; i++) {
            cin >> a[i];
        }
        
        Solution ob;

        //calling equilibriumPoint() function
        cout << ob.equilibriumPoint(a, n) << endl;
    }
    return 0;
}

// } Driver Code Ends

 if(n<m) return "No";
    
    map<int,int> mp;
    for(int i=0;i<n;i++)
    {
        mp[a1[i]]++;
    }
    
    for(int i=0;i<m;i++)
    {
        if(mp.find(a2[i]) != mp.end())
        {
            if(mp[a2[i]] == 0)
            {
                return "No";
            }
            
            mp[a2[i]]--;
            
            continue;
        }else{
            return "No";
        }
    }
    return "Yes";
}





string isSubset(int a1[], int a2[], int n, int m)
{
      int i=0;
      int count=0;
	int j=0;
	sort(a1,a1+n);

    sort(a2,a2+m);
	while(i<n and j<m)
		{
			if(a1[i]==a2[j])
			{
			    i++;
				j++;
				count++;
		
			}
			else if(a1[i]<a2[j])
			{
			    i++;
			}
			else
			{
			    return "No";
			}
		
		}
	if(count==m)
	{
		return "Yes";
	}
	return "No";
}

int lowestCommonAncestor(TreeNode<int> *root, 
int x, int y)
{
	if(!root)
    return -1;
    if(root->data==x or root->data==y)
    return root->data;
    int lefti=lowestCommonAncestor(root->left,x,y);
    int righti=lowestCommonAncestor(root->right,x,y);
    if(lefti==-1)
    return righti;
    if(righti==-1)
    return lefti;
    return root->data;
}

#include <bits/stdc++.h> 
vector<vector<string>>
 getGroupedAnagrams(vector<string> &input, int n)
{
    unordered_map<string,vector<string>>mp;
    vector<vector<string>>ans;
    for(int i=0 ; i<n ; i++)
    {
       string str=input[i];
       string s=str;
       sort(s.begin(),s.end());
       mp[s].push_back(str);
    }
    for(auto it:mp)
    {
        ans.push_back(it.second);
    }
    return ans;
}

int fib(int n)
{
    int a = 0, b = 1, c, i;
    if (n == 0)
        return a;
    for (i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}


int fib(int n)
{
    if (n <= 1)
        return n;
    return fib(n - 1) + fib(n - 2);
}

  vector <int> calculateSpan(int price[], int n)
    {
       vector<int>ans;
       stack<pair<int,int>>st;
       for(int i=0 ; i<n ; i++)
       {
           
           while(!st.empty() and st.top().first<=price[i])
           {
               st.pop();
           }
           if(st.empty())
           {
               ans.push_back(-1);
           }
           else if(!st.empty() and st.top().first>price[i])
           {
                ans.push_back(st.top().second);
           }
        st.push({price[i],i});
       }
       for(int i=0 ; i<n ; i++)
       {
           ans[i]=i-ans[i];
       }
       return ans;
    }

//{ Driver Code Starts
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    struct Node* next;
    Node(int x) {
        data = x;
        next = NULL;
    }
};


// } Driver Code Ends
/* Structure of the linked list node is as
struct Node 
{
    int data;
    struct Node* next;
    Node(int x) { data = x;  next = NULL; }
};
*/


class Solution{
  public:
    //Function to sort the given linked list using Merge Sort.
    Node* merge(Node* left,Node* right)
    {
        Node* ptr=NULL;
        if(!left)
        return right;
        if(!right)
        return left;
        if(left->data<right->data)
        {
            ptr=left;
            ptr->next=merge(left->next,right);
        }
        else
        {
            ptr=right;
            ptr->next=merge(left,right->next);
        }
        return ptr;
    }
    Node* middle(Node* head)
    {
        Node* slow=head;
        Node* fast=head->next;
        while(fast!=NULL and fast->next!=NULL)
        {
            slow=slow->next;
            fast=fast->next->next;
        }
        return slow;
    }
    Node* mergeSort(Node* head)
    {
        if(!head or !head->next)
        return head;
        Node* left=head;
        Node* mid=middle(head);
        Node* right=mid->next;
        mid->next=NULL;
        left=mergeSort(left);
        right=mergeSort(right);
        Node* ans=merge(left,right);
        return ans;
    }
};


//{ Driver Code Starts.

void printList(Node* node) {
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
    printf("\n");
}

void push(struct Node** head_ref, int new_data) {
    Node* new_node = new Node(new_data);

    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

int main() {
    long test;
    cin >> test;
    while (test--) {
        struct Node* a = NULL;
        long n, tmp;
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> tmp;
            push(&a, tmp);
        }
        Solution obj;
        a = obj.mergeSort(a);
        printList(a);
    }
    return 0;
}
// } Driver Code Ends

void merge(vector<int>&arr,int l,int mid,int h)
{
   vector<int>temp;
   int i=l;
   int j=mid+1;
while(i<=mid and j<=h)
{
    if(arr[i]<=arr[j])
    {
        temp.push_back(arr[i]);
        i++;
    }
    else 
    {
        temp.push_back(arr[j]);
        j++;
    }
}
while(i<=mid)
{
    temp.push_back(arr[i]);
    i++;
}
while(j<=h)
{
    temp.push_back(arr[j]);
    j++;
}
for(int i=l ; i<=h ; i++)
{
    arr[i]=temp[i-l];
}
}
void me(vector<int>&arr,int l,int h)
{
   
    if(l>h)
    return;
    int mid=(l+h)/2;
    me(arr,l,mid);
    me(arr,mid+1,h);
    merge(arr,l,mid,h);
}
void mergeSort(vector < int > & arr, int n)
{
    me(arr,0,n-1);
}

#include <bits/stdc++.h> 
string encode(string &message)
{
    string ans="";
    int count=1;
    int n=message.size();
    for(int i=0 ; i<n ; i++)
    {
        if(message[i]==message[i+1])
        {
           count++;  
        }
         ans+=message[i];
    ans+=to_string(count);
    count=1;
    }
   
    return ans;
}

#include <bits/stdc++.h> 
int minimumParentheses(string pattern)
{
    int cnt=0;
    int req=0;
    for(int i=0 ; i<=pattern.length()-1 ; i++) 
    {
         if(pattern[i]=='(')
         {
             cnt++;
         }
         else if(pattern[i]==')' and cnt>0)
         {
             cnt--;
         }
         else
         {
             req++;
         }
    }  
    return cnt+req;
}

#include <bits/stdc++.h>
bool search(int arr[],int n,int num)
{
    for(int i=0 ; i<=n ; i++)
    {
        if(arr[i]==num)
        return true;
    }
    return false;
} 
int firstMissing(int arr[], int n)
{
   for(int i=1 ; i<=n ; i++)
   {
       if(search(arr,n,i)==false)
       return i;
   }
   return n+1;
}

time complexity-O(N2)

#include <bits/stdc++.h> 
int pairSum(vector<int> &arr, int n, int target)
{
	int count=0;
	unordered_map<int,int>mp;
	for(int i=0 ; i<n ; i++)
	{
       if(mp.find(target-arr[i])!=mp.end())
	   {
		   count+=mp[target-arr[i]];
	   }
	   else
	   {
		   mp[arr[i]]++;
	   }
	}
	if(count==0)
	return -1;
	else
	return count;
}

void insertionSort(int n, vector<int> &arr)
{
    for(int i=0 ; i<n ; i++)
    {
        int j=i;
        while(j>0 and arr[j]<arr[j-1])
        {
            swap(arr[j],arr[j-1]);
            j--;
        }
    }
}

class Solution {
public:
    void moveZeroes(vector<int>& arr) 
    {
        int n=arr.size();
       int pos=0;
       for(int i=0 ; i<n ; i++)
       {
           if(arr[i]!=0)
           {
               swap(arr[i],arr[pos]);
               pos++;
           }
       }    
    }
};

int length(Node *head)
{
	//Write your code here
    int c = 0;
    Node *temp = head;
    while(temp != NULL)
    {
        temp = temp->next;
        c++;
    }
    return c;
}

void insertAtTail(Node* &tail,int d)
 {
   Node* temp = new Node(d);
   tail->next = temp;
   tail = tail->next;
 }

Node* constructLL(vector<int>& arr) {
    // Write your code here
    Node* head = new Node(arr[0]);
    Node* tail = head;
    
    for(int i = 1;i<arr.size();i++)
    {
      insertAtTail(tail,arr[i]);
    }
    return head;
}

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

typedef long long ll;
#define placementlelo vector<int>
#define all(a) (a).begin() , (a).end()
#define sz(a) ((int)((a).size()))

const ll INF = 4e18;

vector<placementlelo> dp(1e4+1 , placementlelo(1e4+1 , -1));

int f(int i , int j , int s , int r , string &x , string &y , string &y1)
{
    if(i>j)return 0;
    if(dp[i][j] != -1)return dp[i][j];

    int mini = 1e9;
    for(int k=i; k<=j; k++)
    {
        
        if(y1.find(x.substr(i , k-i+1)) != string::npos)mini = min(mini , r+f(k+1 , j , s , r , x , y , y1));
        if(y.find(x.substr(i , k-i+1)) != string::npos)mini = min(mini , s+f(k+1 , j , s , r , x , y , y1));
    }

    return mini;
}
int solve(int s , int r , string x, string y)
{
    string y1 = y;
    reverse(all(y1));
    return f(0 , sz(x)-1 , s, r , x , y , y1);
}

int32_t main(){

    ios_base::sync_with_stdio(false);  
    cin.tie(NULL);

    string x , y;
    cin >> x >> y;
    int s, r;
    cin >> s >> r;
    int ans = solve(s , r, x , y);
    cout << ans;

    return 0;

}

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

int main(){
    int n, m; // Replace semicolons with commas
    cin >> n >> m; // Remove the extra semicolon
   
    vector<vector<int>> cust;
    for(int i=0; i<n; i++){
        int q, p;
        cin >> q >> p;
        cust.push_back({p, q});
    }
    
    vector<vector<int>> rice;
    for(int i=0; i<m; i++){
        int q, p;
        cin >> q >> p;
        rice.push_back({p, q});
    }
    
    sort(cust.begin(), cust.end());
    sort(rice.begin(), rice.end());
    
    vector<int> placementlelo(m, 0);
    
    int ans = 0;
    
    for(int i=0; i<n; i++){
        int quan = -1;
        int index = -1;
        for(int j=0; j<m; j++){
            if(!placementlelo[j]){
               
                if(rice[j][0] > cust[i][0]) break;
                
                if(rice[j][1] > cust[i][1]){
                    if(quan == -1){
                        quan = rice[j][1];
                        index = j;
                    }
                    else{
                        if(quan > rice[j][1]){
                            index = j;
                            quan = rice[j][1];
                        }
                    }
                }
            }
        }
        
        if(index != -1){
            placementlelo[index] = 1;
            ans++;
        }
    }
    
    cout << ans;
    return 0; // Add a return statement at the end of main
}

#include <bits/stdc++.h>
using namespace std;
// calculating hamming distance
int hamdis(string& s1,string& s2) 
{
		int dis= 0;
	int n=s1.length();
		for (int i = 0; i < n ; i++) 
		{
				if (s1[i] != s2[i]) 
				{
						dis++;
				}
		}
		return dis;
}
// checking string is binary or not
bool checkbinary(string& s) {
		for (int i = 0; i <s.length() ; i++) 
	{
				if (s[i] != '0' and  s[i]!= '1') {
						return false;
				}
		}
		return true;
}
// finding min cost and distance
void findminimum(string& str, int a, int b) {
		if (!checkbinary(str))
		{
				cout << "INVALID"<<endl;
				return;
		}	
    
		string orig = str;
		sort(str.begin(), str.end());
     
		int origcost = 0;
		int count01 = 0;
		int count10 = 0;
     int m=str.length() - 1;
		for (int i = 0; i <m ; i++)
			{
				if (str[i] == '0' && str[i + 1] == '1') {
						count01++;
						origcost += a;
				} else if (str[i] == '1' && str[i + 1] == '0') {
						count10++;
						origcost += b;
				}
		}

	
		int minHammingDistance = hamdis(str, orig);

		cout << minHammingDistance << endl;
}

int main() {
		int T;
		cin >> T;

		for (int t = 0; t < T; t++) {
				string binaryStr;
				int A, B;

				cin >> binaryStr;
				cin >> A >> B;

				findminimum(binaryStr, A, B);
		}

		return 0;
}

  void reverse(int arr[],int low,int high)
    {
        while(low<=high)
        {
            int temp=arr[low];
            arr[low]=arr[high];
            arr[high]=temp;
            low++;
            high--;
        }
    }
    //Function to rotate an array by d elements in counter-clockwise direction. 
    void rotateArr(int arr[], int d, int n)
    {
        if(d>n)
        {
            d=d%n;
        }
        reverse(arr,0,d-1);
        reverse(arr,d,n-1);
        reverse(arr,0,n-1);
    }

 struct Node* reverseList(struct Node *head)
    {
        if(!head or head->next==NULL)
        {
            return head;
        }
        Node* chotahead=reverseList(head->next);
        head->next->next=head;
        head->next=NULL;
        return chotahead;
    }

class Solution{
  public:
    //Function to insert a node at the beginning of the linked list.
    Node *insertAtBegining(Node *head, int x)
    {
            
       Node* newnode=new Node(x);
       newnode->next=head;

       return newnode;
    }
    
    
    //Function to insert a node at the end of the linked list.
    Node *insertAtEnd(Node *head, int x)  
    {
        if(!head)
        {
            Node* newnode=new Node(x);
            return newnode;
        }
        Node* temp=head;
        while(temp->next!=NULL)
        {
            temp=temp->next;
        }
        Node* newnode=new Node(x);
        temp->next=newnode;
        return head;
    }
};

int isSorted(int n, vector<int> a)
{
    bool flag=false;
    for(int i=0 ; i<n-1 ; i++)
    {
      if (a[i] > a[i + 1]) {
        return 0;
      }
    }
    return 1;
}

in two traversal-
  
vector<int> getSecondOrderElements(int n, vector<int> a)
{
    int mini=INT_MAX;
    int maxi=INT_MIN;
    for(int i=0  ; i<n ; i++)
    {
        if(a[i]>maxi)
        {
            maxi=a[i];
        }
        if(a[i]<mini)
        {
            mini=a[i];
        }
    }
    vector<int>ans;
    int mi=INT_MAX;
    int ma=INT_MIN;
    for(int i=0 ; i<n ; i++)
    {
        if(a[i]>ma and a[i]!=maxi)
        {
              ma=a[i];
            
        }
        if(a[i]<mi and a[i]!=mini)
        {
            mi=a[i];
        }
    }
    ans.push_back(ma);
    ans.push_back(mi);
    return ans;
}

in single traversal-
  
int findSecondLargest(int n, vector<int> &arr)
{
    int largest=INT_MIN;
    int secondlargest=INT_MIN;
    for(int i=0 ; i<n ; i++)
    {
        if(arr[i]>largest)
        {
            secondlargest=largest;
            largest=arr[i];
        }
        if(arr[i]<largest and arr[i]>secondlargest)
        {
            secondlargest=arr[i];
        }
    }
    if(secondlargest==INT_MIN)
    {
        return -1;
    }
    return secondlargest;
}

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

int main() {
	double p,r,t;
	cin>>p>>r>>t;
	double in=(p*r*t)/100;
	cout<<fixed<<setprecision(6)<<in;
	return 0;
}

int countLeaves(Node* root)
{
   if(!root)
   return 0;
   if(root->left==NULL and root->right==NULL)
   {
       return 1;
   }
   return (countLeaves(root->left)+countLeaves(root->right));
}

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

struct StackNode {
    int data;
    StackNode *next;
    StackNode(int a) {
        data = a;
        next = NULL;
    }
};

class MyStack {
  private:
    StackNode *top;

  public:
    void push(int);
    int pop();
    MyStack() { top = NULL; }
};
//Function to push an integer into the stack.
void MyStack ::push(int x) 
{
   StackNode* newnode=new StackNode(x);
   newnode->next=top;
   top=newnode;
  
}

//Function to remove an item from top of the stack.
int MyStack ::pop() 
{
    int ddata;
    if(top==NULL)
    {
        return -1;
    }
     ddata=top->data;
    top=top->next;
    return ddata;
}

Note-
#react ko single page application bolte h kyuki pure project mai ek hi html file hoti h or sara kaam ussi ke ander hota h.
#entry point -index.js
#React DOM implementation h react ka web app pr.DOM ek tree structure h.react khud ka virtual DOM bnata h.

function Chai()
{
    return(
        <>
        {/* fragment */}
        <h2>I am Nistha</h2>
        <h3>btech</h3>
        </>
       
    )
}
export default Chai;

void def(struct Node* root,vector<int>&ans,int k);
vector<int> Kdistance(struct Node *root, int k)
{
  vector<int>ans;
  def(root,ans,k);
  return ans;
}
void def(struct Node* root,vector<int>&ans,int k)
{
    if(!root)
    return;
    if(k==0)
    ans.push_back(root->data);
    def(root->left,ans,k-1);
    def(root->right,ans,k-1);
}

 bool solve(Node* root,int mini,int maxi)
    {
        if(!root)
        return true;
        if(root->data>mini and root->data<maxi)
        {
            bool lefti=solve(root->left,mini,root->data);
            bool righti=solve(root->right,root->data,maxi);
             if(lefti and righti)
        return true;
        }
       return false;
    }
    bool isBST(Node* root) 
    {
        return solve(root,INT_MIN,INT_MAX);
    }

   long long int convertEvenBitToZero(long long int n) 
    {
        return n&0xaaaaaaaa;
    }

string reverseString(string s)
{
   unordered_map<char,int>mp;
    string ans="";
    for(int i=s.length()-1 ; i>=0 ; i--)
    {
        mp[s[i]]++;
        if((mp[s[i]]==1)&&(s[i]!=' '))
        {
            ans+=s[i];
        }
    }
    return ans;
}

 pair<int, int> get(int a, int b)
    {
        a=a+b;
        b=a-b;
        a=a-b;
        return{a,b};
    }

int main()
{
    int year;

    year=2000;

    if(year % 400 == 0)
        cout << year << " is a Leap Year";
        
    else if(year % 4 == 0  && year % 100 != 0)
        cout << year << " is a Leap Year";
        
    else
        cout << year << " is not a Leap Year";
    
    return 0;
}

 double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
    {
       vector<int>ans;
       int l=0;
       int r=0;
       while(l<nums1.size() and r<nums2.size())
       {
           if(nums1[l]<nums2[r])
           {
               ans.push_back(nums1[l]);
               l++;
           }
           else
           {
               ans.push_back(nums2[r]);
               r++;
           }
       }
       if(l<nums1.size())
       {
           while(l<nums1.size())
           {
                ans.push_back(nums1[l]);
               l++;
           }
       }
       if(r<nums2.size())
       {
            while(r<nums2.size())
           {
                ans.push_back(nums2[r]);
               r++;
           }
       }
       int size=ans.size();
       if(size%2==1)
       {
           return ans[size/2];
       }
       else
       {
               int a = ans[size / 2 - 1];
    int b = ans[size / 2];
    return (a + b) / 2.0;
       }
       return -1;
    }

vector<int> inOrder(Node* root)
    {
         vector<int>ans;
        stack<Node *>s;
        Node *curr = root;
        while(curr != NULL || !s.empty())
        {
            while(curr != NULL)
            {
                s.push(curr);
                curr = curr -> left;
            }
            curr = s.top();
            s.pop();
            ans.push_back(curr -> data);
            curr = curr -> right;
        }
        return ans;
    }

#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <iterator>
#include <algorithm>
#include <deque>
#include <cmath>
#include <stack>
#include <queue>
#define endl "\n"
#define ll long long
#define all(v) v.begin(),v.end()
void swap(int arr[] , int pos1, int pos2){
    int temp;
    temp = arr[pos1];
    arr[pos1] = arr[pos2];
    arr[pos2] = temp;
}

int partition(int arr[], int low, int high, int pivot){
    int i = low;
    int j = low;
    while( i <= high){
        if(arr[i] > pivot){
            i++;
        }
        else{
            swap(arr,i,j);
            i++;
            j++;
        }
    }
    return j-1;
}

void quickSort(int arr[], int low, int high){
    if(low < high){
        int pivot = arr[high];
        int pos = partition(arr, low, high, pivot);

        quickSort(arr, low, pos-1);
        quickSort(arr, pos+1, high);
    }
}




using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

        ll N ;
        cin>>N ;
        int X[N] ;
        for(ll i=0;i<N;i++){
        cin>>X[i];}
    quickSort(X,0,N-1) ;
    for(ll i=0;i<N;i++){
        cout<<X[i]<<" ";}

}

#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <iterator>
#include <algorithm>
#include <deque>
#include <cmath>
#include <stack>
#include <queue>
#define endl "\n"
#define ll long long
#define all(v) v.begin(),v.end()
void merge(int array[], int const left,
           int const mid, int const right)
{
    auto const subArrayOne = mid - left + 1;
    auto const subArrayTwo = right - mid;

    // Create temp arrays
    auto *leftArray = new int[subArrayOne],
            *rightArray = new int[subArrayTwo];

    // Copy data to temp arrays leftArray[]
    // and rightArray[]
    for (auto i = 0; i < subArrayOne; i++)
        leftArray[i] = array[left + i];
    for (auto j = 0; j < subArrayTwo; j++)
        rightArray[j] = array[mid + 1 + j];

    // Initial index of first sub-array
    // Initial index of second sub-array
    auto indexOfSubArrayOne = 0,
            indexOfSubArrayTwo = 0;

    // Initial index of merged array
    int indexOfMergedArray = left;

    // Merge the temp arrays back into
    // array[left..right]
    while (indexOfSubArrayOne < subArrayOne &&
           indexOfSubArrayTwo < subArrayTwo)
    {
        if (leftArray[indexOfSubArrayOne] <=
            rightArray[indexOfSubArrayTwo])
        {
            array[indexOfMergedArray] =
                    leftArray[indexOfSubArrayOne];
            indexOfSubArrayOne++;
        }
        else
        {
            array[indexOfMergedArray] =
                    rightArray[indexOfSubArrayTwo];
            indexOfSubArrayTwo++;
        }
        indexOfMergedArray++;
    }

    // Copy the remaining elements of
    // left[], if there are any
    while (indexOfSubArrayOne < subArrayOne)
    {
        array[indexOfMergedArray] =
                leftArray[indexOfSubArrayOne];
        indexOfSubArrayOne++;
        indexOfMergedArray++;
    }

    // Copy the remaining elements of
    // right[], if there are any
    while (indexOfSubArrayTwo < subArrayTwo)
    {
        array[indexOfMergedArray] =
                rightArray[indexOfSubArrayTwo];
        indexOfSubArrayTwo++;
        indexOfMergedArray++;
    }
}

// begin is for left index and end is
// right index of the sub-array
// of arr to be sorted */
void mergeSort(int array[],
               int const begin,
               int const end)
{
    // Returns recursively
    if (begin >= end)
        return;

    auto mid = begin + (end - begin) / 2;
    mergeSort(array, begin, mid);
    mergeSort(array, mid + 1, end);
    merge(array, begin, mid, end);
}




using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

        ll N ;
        cin>>N ;
        int X[N] ;
        for(ll i=0;i<N;i++){
        cin>>X[i];}
    mergeSort(X,0,N-1) ;
    for(ll i=0;i<N;i++){
        cout<<X[i]<<" ";}

}

void insertionSort(int arr[], int n)
    {
        int i, key, j;
        for (i = 1; i < n; i++) {
            key = arr[i];
            j = i - 1;

            // Move elements of arr[0..i-1],
            // that are greater than key,
            // to one position ahead of their
            // current position
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }

#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <iterator>
#include <algorithm>
#include <deque>
#include <cmath>
#include <stack>
#include <queue>
#define endl "\n"
#define ll long long
#define all(v) v.begin(),v.end()



using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll N ;
     cin>>N ;
     ll X[N] ;
     for(ll i=0 ;i<N ;i++){cin>>X[i];
     }
     ll k=N ;
    for(ll J=0 ;J<N ;J++) {
         for (ll i = 0; i < N-1-J; i++) {
             if (X[i] > X[i + 1]) {
                 swap(X[i], X[i +1]);
             }
         }
     }

     for(ll i=0 ;i<N ;i++){
         cout<<X[i]<<" ";
     }







}

//--intersection function--
IntersectionResult sphere::IntersectTest(ray _ray)
{
    //creating values
    IntersectionResult testResult;
    testResult.hitsphere = false;

    //p - a calucation for easier use in next calculations
    glm::vec3 delta = sphereCenter - _ray.origin;

    //calculating d
    float d = glm::length(delta - glm::dot(delta,_ray.dir) * _ray.dir);

    //--calculate intersection point--

    //calculating x
    float intersectx = glm::sqrt((radius * radius) - (d * d));

    //final intersect point calculation
    glm::vec3 Intersect_Point = _ray.origin + (glm::dot((sphereCenter - _ray.origin), _ray.dir) - intersectx) * _ray.dir;
    
    //main intersection test
    //if the ray is less than the radius of the sphere that means it hit so set hit to true
    if (d <= radius)
    {
        testResult.Intersectpoint = Intersect_Point;
        testResult.hitsphere = true;
    }

    //returns the result of the ray
    return testResult;
}

namespace myengine
{
    void load_ogg(const std::string& _path, std::vector<unsigned char>& _buffer,
        ALenum& _format, ALsizei& _freq)
    {

        int channels = 0;
        int sampleRate = 0;
        short* output = NULL;

        size_t samples = stb_vorbis_decode_filename(_path.c_str(),
            &channels, &sampleRate, &output);
        std::cout << samples << std::endl;

        if (samples == -1)
        {
            throw std::runtime_error("Failed to open file '" + _path + "' for decoding");
        }

        // Record the format required by OpenAL
        if (channels < 2)
        {
            _format = AL_FORMAT_MONO16;
        }
        else
        {
            _format = AL_FORMAT_STEREO16;
        }

        // Copy (# samples) * (1 or 2 channels) * (16 bits == 2 bytes == short)
        _buffer.resize(samples * channels * sizeof(short));
        memcpy(&_buffer.at(0), output, _buffer.size());

        // Record the sample rate required by OpenAL
        _freq = sampleRate;

        // Clean up the read data
        free(output);
    }

void DealersTurn(cards PlayerHand[], cards DealerHand[])//dealers turn function
{
	DealerTotalHandscore = 0;//sets ai hand score to 0 to reset it when they start thier turn

	for (i = 0; i < dealerCurrentHand; i++)//when dealer gets a card it adds to the value
	{
		DealerTotalHandscore += DealerHand[i].PlayerValue;
	}

	if (DealerTotalHandscore < 17)//if dealer is less than 17 they can draw a card
	{
		HitDealer(PlayerHand, DealerHand);//draws card for dealer
		Sleep(2000);//delay for immersion
		DealersTurn(PlayerHand, DealerHand);//dealers turn again since its below 17
	}

	if (DealerTotalHandscore >= 17)//if dealers hand is above 17
	{
		if (TotalHandscore > DealerTotalHandscore)//checks if players hand is bigger than the dealers hand, if player went over the game wouldve already end
		{
			Sleep(2000);//delay for suspense
			std::cout << "You win! Congrats! Your hand total is " << TotalHandscore << " The dealers was " << DealerTotalHandscore << std::endl;
			Sleep(2000);
			bank += currentbet * 2;
			std::cout << "You now have $" << bank << " in your bank" << std::endl;
			Sleep(2000);
			std::cout << "Do you want to continue playing? " << std::endl << "1.Yes " << std::endl << "2.No" << std::endl;
			Choice = 0;
			std::cin >> Choice;//player chooses to play or exit

			if (Choice == 1)
			{
				Choice = 0;
				reset();
			}

			if (Choice == 2)
			{
				Choice = 0;
				Quitgame();
			}
		}
	}

class Solution {
public:
    vector<int> duplicates(vector<int>& nums){
        unordered_set<int> uSet;
        int n = nums.size();
        vector<int> dup(n, 0);
        for(int i = 0 ; i < n ;i++){
            if(uSet.find(nums[i]) != uSet.end()){
                dup[i] = 1;
            }
            if(i != 0)
                dup[i] += dup[i-1];
            uSet.insert(nums[i]);
        }
        return dup;
    }
    int minOperations(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int req = nums.size() - 1 , ans = nums.size() - 1, n =nums.size();
        vector<int> d = duplicates(nums);
        for(int ptr = 0; ptr < n-1 ;ptr++ ){
            int idx = lower_bound(nums.begin(), nums.end(), req + nums[ptr]) - nums.begin();
            if(idx < n ){
                int val = nums[ptr] + req;
                if(nums[idx] != val)
                    ans = min(ans, n - idx + ptr + d[idx] - d[ptr]);
                else
                    ans = min(ans, n - idx + ptr - 1 + d[idx] - d[ptr]);
            } 
            else
                ans = min(ans, d[n-1] - d[ptr]+ptr);
        }
        return ans;

    }
};

// given two strings s1 and s2 (|s1| == |s2|) make s1 same as s2 using following 2 operations 
// 1. swap any two elements at indices i and j in s1 with cost x ,
// 2. swap two adjacent elements with cost 1
// achieve this with minimum cost 

 
#define pb push_back 

class Solution {
public:
    vector<double> dp;
    double findMin(vector<int>& diff, int i, int x){
        if( i == 0)
            return x / 2.0;
        if( i == -1)
            return 0;
        if(dp[i] != -1)
            return dp[i];
        double left  = findMin(diff, i-1, x) + x/2.0;
        double right = findMin(diff, i-2 , x) + diff[i] - diff[i-1];
        return dp[i] = min(left, right);
    }
    int minOperations(string s1, string s2, int x) {
        vector<int> diffs;
        int n = s1.length();
        for(int i = 0; i < n; i++)
            if(s1[i] != s2[i])
                diffs.pb(i);
        if(diffs.size() & 1)
            return -1;
        dp.resize(diffs.size(),-1);
        return (int)findMin(diffs, diffs.size() - 1, x);
        
    }
};
// Its O(n) time and O(n) space;

/*----------------------------*/
bool isPrime(int n){for(int i=2;i*i<=n;i++){if(n%i==0)return false;}return true;}
bool isvowel(char c){return (c=='a'||c=='e'||c=='i'||c=='o'||c=='u');}
bool isperfect(long long num){int count = 0;while (num & count<11) {count += num % 10;num /= 10;}return count == 10;}
/*----------------------------*/
#define ll long long
#define dd double
#define vi  vector<int> 
#define vvi vector<vector<int>>
#define mi map<int,int>
#define pr  pair<int,int>
#define unset unordered_set<int>
#define ff first
#define ss second
#define pb push_back
#define MAX INT_MAX
#define MIN INT_MIN
#define fr(i,a,n) for(int i=a; i<n; i++)
const int MOD=1e9+7;

#include<bits/stdc++.h>
using namespace std;
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    return 0;
}

    // for sophon opencv, the memory is not continuous if the width of image is not 64 bytes aligned
    uint8_t continous_data[cvmat.cols * cvmat.rows * cvmat.channels()];
    if (!cvmat.isContinuous())
    {
        std::cout << "cvmat is not continuous" << std::endl;
        for (int i = 0; i < cvmat.rows; i++)
        {
            std::memcpy(continous_data + i * cvmat.cols * cvmat.channels(), cvmat.ptr(i), cvmat.cols * cvmat.channels());
        }
    }
    else
    {
        std::memcpy(continous_data, cvmat.data, cvmat.cols * cvmat.rows * cvmat.channels());
    }

bool isEven(Node* head){
            Node* fast = head;
            while(fast && fast->next) fast=fast->next->next;
            if(!fast )
                return true;
            return false;
    }

#include <iostream>
using namespace std;

int getGcd(int a, int b) {
  
  while(b!=0) {
    int rem = a%b;
    a=b;
    b=rem;
  }
  return a;
}

int main() 
{
    int a,b,gcd;
    cin>>a>>b;
    gcd = getGcd(a, b);
    cout<<gcd;
    return 0;
}

#include <iostream>
using namespace std;

void primeFactorsSieve(int n) {
  int spf[n]={0};
  
  for(int i=2;i<=n;i++) {
    spf[i]=i;
  }
  
  for(int i=2;i<=n;i++) {
    if(spf[i]==i) {
      for(int j=i*i;j<=n;j+=i) {
        if(spf[j]==j) {
          spf[j]=i;
        }
      }
    }
  }
  
  while(n!=1) {
    cout<<spf[n]<<" ";
    n=n/spf[n]; 
  }
}

int main() 
{
    int n;
    cin>>n;
    primeFactorsSieve(n);
    return 0;
}

#include <iostream>
using namespace std;

void primeSieve(int n) {
  int prime[100]={0};
  int cnt=0;
  
  for(int i=2;i<=n;i++) {
    if(prime[i]==0) {
      for(int j=i*i;j<=n;j+=i) {
        prime[j]=1;
      }
    }
  }
  cout<<"\nNumbers: ";
  for(int i=2;i<=n;i++) {
    if(prime[i]==0) {
      cout<<i<<" ";
      cnt++;
    }
  }
  cout<<"\nTotal prime numbers: "<<cnt;
  cout<<endl;
}

int main() 
{
    // cout << "Hello, World!";
    int n;
    cin>>n;
    primeSieve(n);
    return 0;
}

from collections import deque

visited_states = []
total_moves = 70
expanded = 0
count = 0

class Node:
    def __init__(self, state, parent, operator, depth, cost):
        self.state = state
        self.parent = parent
        self.operator = operator
        self.depth = depth
        self.cost = cost

def create_node(state, parent, operator, depth, cost):
    return Node(state, parent, operator, depth, cost)

def expand_node(node):
    expanded_nodes = []
    
    temp_state = move_down(node.state)
    temp_node = create_node(temp_state, node, "down", node.depth + 1, node.cost + 1)
    expanded_nodes.append(temp_node)

    temp_state1 = move_up(node.state)
    temp_node1 = create_node(temp_state1, node, "up", node.depth + 1, node.cost + 1)
    expanded_nodes.append(temp_node1)

    temp_state2 = move_left(node.state)
    temp_node2 = create_node(temp_state2, node, "left", node.depth + 1, node.cost + 1)
    expanded_nodes.append(temp_node2)

    temp_state3 = move_right(node.state)
    temp_node3 = create_node(temp_state3, node, "right", node.depth + 1, node.cost + 1)
    expanded_nodes.append(temp_node3)

    return expanded_nodes

def move_left(state):
    swap = state.copy()
    idx = swap.index(0)
    if (idx == 0 or idx == 3 or idx == 6):
        return swap
    else:
        swap[idx - 1], swap[idx] = swap[idx], swap[idx - 1]
        return swap

def move_right(state):
    swap = state.copy()
    idx = swap.index(0)
    if (idx == 2 or idx == 5 or idx == 8):
        return swap
    else:
        swap[idx + 1], swap[idx] = swap[idx], swap[idx + 1]
        return swap

def move_up(state):
    swap = state.copy()
    idx = swap.index(0)
    if (idx == 0 or idx == 1 or idx == 2):
        return swap
    else:
        swap[idx - 3], swap[idx] = swap[idx], swap[idx - 3]
        return swap

def move_down(state):
    swap = state.copy()
    idx = swap.index(0)
    if (idx == 6 or idx == 7 or idx == 8):
        return swap
    else:
        swap[idx + 3], swap[idx] = swap[idx], swap[idx + 3]
        return swap

def bfs(start, goal):
    if (start == goal):
        return [None]
    else:
        to_be_expanded = []
        current_node = create_node(start, None, None, 0, 0)
        to_be_expanded.append(current_node)

        for i in range(total_moves):
            temp_expanded = []
            size = len(to_be_expanded)

            for j in range(size):
                if (to_be_expanded[j] in visited_states):
                    continue

                node_array = expand_node(to_be_expanded[j])

                for x in range(4):
                    if (node_array[x].state == goal):
                        count = i + 1
                        return node_array[x]
                    else:
                        temp_expanded.append(node_array[x])
                        visited_states.append(node_array[x].state)

            to_be_expanded.clear()
            to_be_expanded = temp_expanded.copy()
            temp_expanded.clear()

    return None

def main():
    method = 'bfs'
    length = 0
    x = 0
    x = x + 1

    board_input = input("Enter the initial state values (comma-separated): ")
    board_split = board_input.split(',')
    starting_state = [int(i) for i in board_split]

    goal_input = input("Enter the goal state values (comma-separated): ")
    goal_split = goal_input.split(',')
    goal_state = [int(i) for i in goal_split]

    if (len(starting_state) == 9 and len(goal_state) == 9):
        result = bfs(starting_state, goal_state)
        if result == None:
            print("No solution found")
        elif result == [None]:
            print("Start node was the goal!")
        else:
            print("Total number of moves needed =", result.cost)
            path = []
            path.append(result.state)
            current = result
            flag = True

            while flag:
                parent = current.parent
                prev_state = parent.state
                path.append(prev_state)
                current = parent

                if (prev_state == starting_state):
                    flag = False

            path.reverse()
            print("Step-wise Sequence of states from start to goal is ")
            for state in path:
                print(state[0], "|", state[1], "|", state[2])
                print(state[3], "|", state[4], "|", state[5])
                print(state[6], "|", state[7], "|", state[8])
                print()
    else:
        print("Invalid input")

if __name__ == "__main__":
    main()

The introduction of computerized technology in the healthcare sector - the promised to bring a qualitative change to patient one. While in various ways there was a bump in the service they received, patients should have experienced higher value all over the board. 

Let’s see some of the examples of integration of Healthcare and blockchain technology. 

Remote Patient Monitoring (RPM)

RMP should to have allowed the shift from episodic to preventative healthcare delivery. This should have been feasible with proactive patient monitoring with "Internet of Things" (IoT) approved devices. The RMP market is predicted to reach $535 Million in united states. RMP devices collect PHI, which needs protection, therefore, a private blockchain is the right choice in this case.
Smart contracts on this private blockchain analyze patient health data.

Electronic Medical Records (EMRs)

EMRs record patient data in the format of electronical, that should have reduced the requirement of paper-based processes. This should have permitted multiple healthcare providers to seamlessly access patient data. This was supposed to significantly enhance the provision of healthcare services. To secure EMRs, Medicalchain uses Hyperledger Fabric, an enterprise blockchain.

There are many healthcare blockchain business ideas that have significant potential. However, integrating any of these ideas is a complex process. Blockchain development requires a lot of expertise and planning, so you might want to get proficient help.

#include <iostream>
using namespace std;

string ending(int sum, int cash) {
  const string s = "купюр";
  const string end1 = "a";
  const string end2 = "ы";
  string banknote;

  sum /= cash;

  if (sum > 4 && sum < 21 || sum > 24 && sum % 10 > 4 
    && sum % 10 <= 9 && sum % 10 == 0 || sum == 0) banknote = s;
  if (sum == 1 || sum % 10 == 1) banknote = s + end1;
  if (sum > 1 && sum < 5 || sum % 10 > 1 
    && sum % 10 < 5)  banknote = s + end2;
  
  return banknote;
}

int remainder(int sum, int cash) {
  sum -= 1;

  if (sum >= 100 && sum != 0 && sum / cash != 0) {
    cout << sum / cash << " - " << ending(sum, cash) << " " << cash << " руб.\n";
  }
  return sum;
}

int main() {
  system("clear");
  
  int sum;
  cout << "Введите сумму, которую хотите обналичить : ";
  cin >> sum;
  sum += 1;
  
  if (sum > 100 && sum < 150000 && sum % 100 == 1) {

    int cash = 5000;
    remainder(sum, cash);
      cash = 2000; sum = sum % 5000;
    remainder(sum, cash);
      cash = 1000; sum = sum % 2000;
    remainder(sum, cash);
      cash = 500; sum = sum % 1000;
    remainder(sum, cash);
      cash = 200; sum = sum % 500;
    remainder(sum, cash);
      cash = 100; sum = sum % 200;
    remainder(sum, cash);

  } else {
    cout << "Не корректная сумма для вывода денег.";
  }
}

#include <iostream>
using namespace std;

int main() 
{
  int mansCount;
  int barbersCount;
  int mansPerBarber = 8; // один человек в час, смена 8 часов
  int mansPerBarberPerMonth = mansPerBarber * 30;
/*
mansCount;               - КолМужчин
barbersCount;            - КолБарберов
mansPerBarber            - КолПодстриженныхЗаСмену
mansPerBarberPerMonth    - КолПодстриженныхЗаМесяц
NecessaryNumberBarbers   - НеобходимоеКолБарберов
BarbersRequired          - ТребуемыеБарберы
*/
  cout << "\n************ Барбершоп-калькулятор ************\n\n";
back:
  cout << "Введите число мужчин в городе: ";
  cin >> mansCount;
  if (mansCount <= 0) {
    cout << "\nВы не можете ввести нулевое или отрицательное значение...\n";
    cout << "Попробуйте ещё раз.\n\n";
    goto back;
  }
back1:
  cout << "Сколько уже барберов удалось нанять? ";
  cin >> barbersCount;
  if (barbersCount <= 0) {
    cout << "\nВы не можете ввести нулевое или отрицательное значение...\n";
    cout << "Попробуйте ещё раз.\n\n";
    goto back1;
  }
  
  cout << "\nОдин барбер стрижёт " << mansPerBarberPerMonth << " клиентов в месяц.\n";

  // Сколько нужно барберов, чтобы постричь mansCount человек?
  int NecessaryNumberBarbers = mansCount / mansPerBarberPerMonth;
  
  if (NecessaryNumberBarbers * mansPerBarberPerMonth % mansCount) {
    NecessaryNumberBarbers += 1;
  }
  
  cout << "Необходимое число барберов: " << NecessaryNumberBarbers << "\n\n";

    const string b = "барбер";
    const string end1 = "a";
    const string end2 = "ов";
  
    string endin;
    int n = NecessaryNumberBarbers;
    if (n == 1 || (n > 20 && n % 10 == 1)) endin = b;
    else if (n > 1 && n < 5 || n > 20 && n % 10 > 1 && n % 10 < 5) endin = b + end1;
    else endin = b + end2;

  // Сколько человек успеют посчтричь NecessaryNumberBarbers за месяц?
  cout << NecessaryNumberBarbers << " " << endin << " могут постричь " 
  << NecessaryNumberBarbers * mansPerBarberPerMonth << " мужчин за месяц.\n";

    string ending;
    int nb = NecessaryNumberBarbers - barbersCount;
    if (nb == 1 || (nb > 20 && nb % 10 == 1)) ending = b;
    else if (nb > 1 && nb < 5 || nb > 20 && nb % 10 > 1 && nb % 10 < 5) ending = b + end1;
    else ending = b + end2;

  int BarbersRequired = NecessaryNumberBarbers - barbersCount;

  if (NecessaryNumberBarbers > barbersCount) {
    cout << "Требуется ещё " << BarbersRequired << " " << ending << ".\n";
  } else if (NecessaryNumberBarbers == barbersCount) {
    cout << "Барберов ровно столько, сколько нужно!!!\n";
  } else if (barbersCount % NecessaryNumberBarbers == 0) {
    cout << "У вас работает в " << barbersCount / NecessaryNumberBarbers << " раза больше барберов, чем это нужно!!!\n";
  } else cout << "Барберов хватает!!!\n";
}

#include <iostream>
#include <set>
#include <algorithm>
#include <math.h>
#include <vector>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iterator>
// #include<bits/stdc++.h>
using namespace std;
#define forn(i, a, n) for (int i = a; i < n; i++)
#define MAXN 1000000
#define MOD 1000000007
#define int long long
#define tc    \
    int t;    \
    cin >> t; \
    while (t--)
#define TC size(arr) / size(arr[0])
#define mp make_pair
#define Radhe ios::sync_with_stdio(false);
#define Krishna cin.tie(NULL);

int Time = 0;
vector<pair<int, int>> br;
set<pair<int, int>> res;

vector<int> low, disc;
vector<vector<int>> adj;

void dfsBR(int u, int p)
{
    low[u] = disc[u] = ++Time;
    for (int &v : adj[u])
    {
        if (v == p)
            continue; // we don't want to go back through the same path.
                      // if we go back is because we found another way back
        if (!disc[v])
        {
            res.insert({u, v});
            // if V has not been discovered before
            dfsBR(v, u);          // recursive DFS call
            if (disc[u] < low[v]) // condition to find a bridge
                br.push_back({u, v});

            low[u] = min(low[u], low[v]); // low[v] might be an ancestor of u
        }
        else // if v was already discovered means that we found an ancestor
        {
            if (low[u] >= disc[v])
            {
                low[u] = min(low[u], disc[v]); // finds the ancestor with the least discovery time
                res.insert({u, v});

            }else{
                if(res.find({v,u})==res.end()){
                    res.insert({u,v});
                }
            }

        }
    }
}

void BR()
{
    low = disc = vector<int>(adj.size(), 0);
    Time = 0;
    for (int u = 0; u < adj.size(); u++)
    {
        if (!disc[u])
        {
            dfsBR(u, u);
        }
    }
}

void solve()
{
    int n, m;
    cin >> n >> m;
    adj.resize(n);
    forn(i, 0, m)
    {
        int u, v;
        cin >> u >> v;
        u--, v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    BR();

    if (br.size())
    {
        cout << 0 << endl;
        return;
    }

    // cout<<br.size()<<endl;
    for (auto &x : res)
    {
        cout << x.first + 1 << " " << x.second + 1 << endl;
    }
}
int32_t main()
{
    Radhe Krishna
    {
        solve();
    }

    return 0;
}

// adj[u] = adjacent nodes of u
// ap = AP = articulation points
// p = parent
// disc[u] = discovery time of u
// low[u] = 'low' node of u

int dfsAP(int u, int p) {
  int children = 0;
  low[u] = disc[u] = ++Time;
  for (int& v : adj[u]) {
    if (v == p) continue; // we don't want to go back through the same path.
                          // if we go back is because we found another way back
    if (!disc[v]) { // if V has not been discovered before
      children++;
      dfsAP(v, u); // recursive DFS call
      if (disc[u] <= low[v]) // condition #1
        ap[u] = 1;
      low[u] = min(low[u], low[v]); // low[v] might be an ancestor of u
    } else // if v was already discovered means that we found an ancestor
      low[u] = min(low[u], disc[v]); // finds the ancestor with the least discovery time
  }
  return children;
}

void AP() {
  ap = low = disc = vector<int>(adj.size());
  Time = 0;
  for (int u = 0; u < adj.size(); u++)
    if (!disc[u])
      ap[u] = dfsAP(u, u) > 1; // condition #2
}

   for(int k=0;k<26;k++){
        for(int j=0;j<26;j++){
            for(int i=0;i<26;i++){
                if(W[i][k]!=3000 && W[k][j]!=3000)
                W[i][j]=min(W[i][j],W[i][k]+W[k][j]);
            }
        }
    }

#include <iostream>
#include <set>
#include <algorithm>
#include <math.h>
#include <vector>
#include <queue>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iterator>
// #include<bits/stdc++.h>
using namespace std;
#define forn(i, a, n) for (int i = a; i < n; i++)
#define MAXN 1000000
#define MOD 1000000007
#define INT_MAX 1e12
#define int long long
#define tc    \
    int t;    \
    cin >> t; \
    while (t--)
#define TC size(arr) / size(arr[0])
#define Radhe ios::sync_with_stdio(false);
#define Krishna cin.tie(NULL);
void solve()
{
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> adj(n);
    map<pair<int, int>, int> mp;
    vector<int> par(n, -1);
    for (int i = 0; i < m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        if (u == v)
        {
            continue;
        }
        if (v < u)
        {
            swap(u, v);
        }
        u--, v--;
        
        
        if (mp.count({u, v}))
        {
            mp[{u, v}] = min(mp[{u, v}], w);
        }
        else
        {
            mp[{u, v}] = w;
        }
    }
    
for  (auto i = mp.begin(); i != mp.end(); i++) 
    { auto x=*i;
        adj[x.first.first].push_back({x.first.second,x.second});
        adj[x.first.second].push_back({x.first.first,x.second});
    }

    priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
    vector<int> dist(n, INT_MAX);
    dist[0] = 0;
    pq.push({0, {0, -1}});
    while (!pq.empty())
    {
        int u = pq.top().second.first;
        if(pq.top().first>dist[u])
        {
            pq.pop();
            continue;
        }
        par[u] = pq.top().second.second;
        pq.pop();
        for (auto it : adj[u])
        {
            int v = it.first;
            int weight = it.second;
            if (dist[u] == INT_MAX)
            {
                continue;
            }
            if (dist[v] > dist[u] + weight)
            {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], {v, u}});
            }
        }
    }
   
    if(dist[n-1]==INT_MAX)
    {
        cout<<-1<<endl;
        return;
    }
    vector<int> ans;
    int i = n - 1;
    while (i != -1)
    {
        ans.push_back(i + 1);
        i = par[i];
    }
    for(int i=ans.size()-1;i>0;i--)
    {
        cout<<ans[i]<<" ";
    }
    cout<<ans[0]<<endl;
}
int32_t main()
{
    Radhe Krishna
    {
        solve();
    }

    return 0;
}

#include <iostream>
#include <set>
#include <algorithm>
#include <math.h>
#include <vector>
#include <stack>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iterator>
// #include<bits/stdc++.h>
using namespace std;
#define forn(i, a, n) for (int i = a; i < n; i++)
#define MAXN 1000000
#define MOD 1000000007
#define int long long
#define tc    \
    int t;    \
    cin >> t; \
    while (t--)
#define TC size(arr) / size(arr[0])
#define mp make_pair
#define Radhe ios::sync_with_stdio(false);
#define Krishna cin.tie(NULL);

vector<vector<int>> graph;
int tot = 0;

void findComponent(int u, vector<int> &disc, vector<int> &lowLink, stack<int> &stk, vector<bool> &stkItem)
{
    static int time = 0;
    disc[u] = lowLink[u] = ++time;
    stk.push(u);
    stkItem[u] = true;

    for (auto x : graph[u])
    {
        {
            if (disc[x] == -1)
            {
                findComponent(x, disc, lowLink, stk, stkItem);
                lowLink[u] = min(lowLink[u], lowLink[x]);
            }
            else if (stkItem[x])
                lowLink[u] = min(lowLink[u], disc[x]);
        }
    }
    int poppedItem = 0;

    if (lowLink[u] == disc[u])
    {
        int co = 0;

        while (stk.top() != u)
        {
            poppedItem = stk.top();
            co++;
            stkItem[poppedItem] = false;
            stk.pop();
        }
        poppedItem = stk.top();
        co++;
        stkItem[poppedItem] = false;
        stk.pop();

        if (co > 1)
        {
            tot += co;
        }
    }
}

void strongConComponent(vector<vector<int>> &graph)
{
    int v = graph.size();
    vector<int> disc(v, -1), lowLink(v, -1);
    vector<bool> stkItem(v, false);
    stack<int> stk;

    for (int i = 0; i < v; i++)
        if (disc[i] == -1)
            findComponent(i, disc, lowLink, stk, stkItem);
}

void solve()
{

    tot = 0;
    int n;
    cin >> n;
    graph = vector<vector<int>>(n);
    forn(i, 0, n)
    {
        char x;
        cin >> x;
        if (x == '<')
        {
            graph[(i + 1) % n].push_back(i);
        }
        else if (x == '>')
        {
            graph[i].push_back((i + 1) % n);
        }
        else
        {
            graph[i].push_back((i + 1) % n);
            graph[(i + 1) % n].push_back(i);
        }
    }

    strongConComponent(graph);
    cout << tot << endl;
}
int32_t main()
{
    Radhe Krishna
        tc
    {
        solve();
    }

    return 0;
}

// br = bridges, p = parent

vector<pair<int, int>> br;

int dfsBR(int u, int p) {
  low[u] = disc[u] = ++Time;
  for (int& v : adj[u]) {
    if (v == p) continue; // we don't want to go back through the same path.
                          // if we go back is because we found another way back
    if (!disc[v]) { // if V has not been discovered before
      dfsBR(v, u);  // recursive DFS call
      if (disc[u] < low[v]) // condition to find a bridge
        br.push_back({u, v});
      low[u] = min(low[u], low[v]); // low[v] might be an ancestor of u
    } else // if v was already discovered means that we found an ancestor
      low[u] = min(low[u], disc[v]); // finds the ancestor with the least discovery time
  }
}

void BR() {
  low = disc = vector<int>(adj.size());
  Time = 0;
  for (int u = 0; u < adj.size(); u++)
    if (!disc[u])
      dfsBR(u, u)
}

Bitcoin Miner Script holding a hash algorithm that executes the mining activity in a simple and effective way. Whenever a user tries to access the data for transactions, the script verifies the ledger system automatically that matches the private key to proceed with the transactions. The Bitcoin miner script is developed with the ability to support other features that includes:

Payment gateways
Ticket system
Plan management
Genealogy
Multiple currencies
Promotional banners
E-pin generation facility
Multiple languages

It was a Good approach to move ahead based on the up-gradation of technology. The usage of cryptocurrencies are really high, so that the opportunities to create a business website are in good state to yield benefits as well. Visit Best bitcoin miner script to know more about the ideal features of the script. 

> https://maticz.com/bitcoin-mining-script

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

// Main function to run the program
int main() 
{ 
    int arr[] = {10, 30, 10, 20, 10, 20, 30, 10}; 
    int n = sizeof(arr)/sizeof(arr[0]); 

    int visited[n];

    for(int i=0; i<n; i++){

        if(visited[i]!=1){
           int count = 1;
           for(int j=i+1; j<n; j++){
              if(arr[i]==arr[j]){
                 count++;
                 visited[j]=1;
              }
            }

            cout<<arr[i]<<" occurs at "<<count<<" times "<<endl;
         }
     }

    return 0; 
}

console.log('Welcome to HomePage!')

#include <stdio.h>
#include <string.h>

#define MAX_ATTEMPTS 3
#define MAX_USERS 5
#define MAX_USERNAME_LENGTH 20
#define MAX_PASSWORD_LENGTH 20

typedef struct {
    char username[MAX_USERNAME_LENGTH];
    char password[MAX_PASSWORD_LENGTH];
} User;

int main() {
    User users[MAX_USERS] = {
        {"user1", "pass1"},
        {"user2", "pass2"},
        {"user3", "pass3"},
        {"user4", "pass4"},
        {"user5", "pass5"}
    };

    int attempts = 0;
    int authenticated = 0;

    while (attempts < MAX_ATTEMPTS && !authenticated) {
        char inputUsername[MAX_USERNAME_LENGTH];
        char inputPassword[MAX_PASSWORD_LENGTH];

        printf("Enter username: ");
        scanf("%s", inputUsername);
        printf("Enter password: ");
        scanf("%s", inputPassword);

        for (int i = 0; i < MAX_USERS; i++) {
            if (strcmp(inputUsername, users[i].username) == 0 && strcmp(inputPassword, users[i].password) == 0) {
                authenticated = 1;
                break;
            }
        }

        if (!authenticated) {
            attempts++;
            printf("Authentication failed, try again.\n");
        }
    }

    if (authenticated) {
        printf("Authentication successful.\n");
    } else {
        printf("Limit exceeded. Exiting.\n");
    }

    return 0;
}

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> v(n+1, 0);
        for(int i=1;i<=n;i++)
        {
            int p=i;
            int t=32;
            int ans=0;
            
            while(p!=0)
            {
                int rsbm = p&-p;
                p-=rsbm;
                ans++;
            }
            v[i]=ans;
        }
        return v;
    }
};

#include <string.h>
#include <stdio.h>
#include <stdlib.h>
int main(int argc,char *argv[])
{
        char *cat="/bin/cat";
    if(argc<2)
        {
                printf("Please type a file name.\n");
                return 1;
        }
     char *command =malloc(strlen(cat) + strlen(argv[1]) + 2);
        sprintf(command,"%s %s", cat,argv[1]);
        system((command));
        return 0;
}

Developing a Rummy Game can be a lucrative endeavor, But it is important to consider its various factors such as the game’s design, complexity, platform compatibility, and back-end infrastructure all crucially determine the overall expenditure. Hiring freelance rummy game developers or partnering with a proficient rummy game development company can also impact the final price tag.

A simple Rummy game with important features and minimalistic graphics could set you back anywhere from $10000 to $40000. On the other hand, if your vision includes an intricate, cross-platform game with attractive visuals, the cost will be up to $35000 to $200000 or more., Thus, before you initiate looking for rummy game developers for hire, you must first determine what you are planning to build.

https://maticz.com/rummy-game-development

#include <bits/stdc++.h>

using namespace std;

struct node {
  int data;
  struct node * left, * right;
};

vector < int > postOrderTrav(node * cur) {

  vector < int > postOrder;
  if (cur == NULL) return postOrder;

  stack < node * > st;
  while (cur != NULL || !st.empty()) {

    if (cur != NULL) {
      st.push(cur);
      cur = cur -> left;
    } else {
      node * temp = st.top() -> right;
      if (temp == NULL) {
        temp = st.top();
        st.pop();
        postOrder.push_back(temp -> data);
        while (!st.empty() && temp == st.top() -> right) {
          temp = st.top();
          st.pop();
          postOrder.push_back(temp -> data);
        }
      } else cur = temp;
    }
  }
  return postOrder;

}

struct node * newNode(int data) {
  struct node * node = (struct node * ) malloc(sizeof(struct node));
  node -> data = data;
  node -> left = NULL;
  node -> right = NULL;

  return (node);
}

int main() {

  struct node * root = newNode(1);
  root -> left = newNode(2);
  root -> right = newNode(3);
  root -> left -> left = newNode(4);
  root -> left -> right = newNode(5);
  root -> left -> right -> left = newNode(8);
  root -> right -> left = newNode(6);
  root -> right -> right = newNode(7);
  root -> right -> right -> left = newNode(9);
  root -> right -> right -> right = newNode(10);

  vector < int > postOrder;
  postOrder = postOrderTrav(root);

  cout << "The postOrder Traversal is : ";
  for (int i = 0; i < postOrder.size(); i++) {
    cout << postOrder[i] << " ";
  }
  return 0;
}

#include <vector>
#include <stack>

using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> inorder;

        TreeNode* node = root;

        while (true) {
            if (node != nullptr) {
                st.push(node);
                node = node->left;
            } else {
                if (st.empty())
                    break;

                node = st.top();
                st.pop();
                inorder.push_back(node->val);

                node = node->right;
            }
        }

        return inorder;
    }
};

#include <vector>
#include <stack>

using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> preorder;

        if (root == nullptr)
            return preorder;

        stack<TreeNode*> st;
        st.push(root);

        while (!st.empty()) {
            root = st.top();
            st.pop();
            preorder.push_back(root->val);

            if (root->right != nullptr) {
                st.push(root->right);
            }

            if (root->left != nullptr) {
                st.push(root->left);
            }
        }

        return preorder;
    }
};

//level order traversal ---->  lecture 8 striver 

#include <vector>
#include <queue>

using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;

        if (root == nullptr)
            return ans;

        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            int size = q.size();
            vector<int> level;

            for (int i = 0; i < size; i++) {
                TreeNode* node = q.front();
                q.pop();

                if (node->left != nullptr)
                    q.push(node->left);
                if (node->right != nullptr)
                    q.push(node->right);

                level.push_back(node->val);
            }

            ans.push_back(level);
        }

        return ans;
    }
};

//iterative preorder traversal

Blockchain businesses have gained tremendous popularity in the upcoming years. Many companies are showing keen interest in the field of blockchain, so it is the perfect time for blockchain to rise. Because blockchain is a distributed and p2p technology, its major benefits, and application can be found in almost every sector. You can turn this blockchain use into your Blockchain business idea if you solely understand the technology.

​#include <iostream>

using namespace std;

int main()
{
    int a,b,s;
    cin >>a>>b;
    s=a+b;
    cout <<s;

    return 0;
}

Are you interested in the crypto world and want to explore new ways of trading? Do you have a knack for coding and want to develop your own crypto trading bot? If yes, you have come to the right place! Creating a crypto trading bot from scratch can sound threatening, but it is quite easier and can potentially yield great results. 

However, for the ultimate security and reliability, it is best to know how to create a trading bot for crypto if you want to make Bitcoin trading a significant portion of your revenue. Want to create your own crypto trading bot? Then Maticz can assist you to build your own trading bot in a hassle-free manner. Check out the website and get more information via >> https://maticz.com/how-to-create-a-crypto-trading-bot

Video games are a massive industry with over 59 billion USD in sales in 2015. The process of creating a video game is much more complicated than you might think, that involves a number of various disciplines and cross-generational teamwork. We have broken down the process into its component pieces so that you can see what roles each team member plays to make something like Overwatch possible.

Early Pre production:

Art Direction
Gameplay Design
Planning
Documents
Designing
Testing
Implementation
Product release

Post Production:

Marketing
Distribution
Support
Post Maintainance
End of Life

This is when the next generation of video games may be created, and when a game is retired, it is no longer eligible for future development. However, the developers may continue to work on it, but without official support.

#include <iostream>
using namespace std;

bool prompt_yes_or_no(const string& question) {
    cout << question << " (Y/N): ";
    char response;
    cin >> response;
    return (response == 'Y' || response == 'y');
}

void join_farm_out_project_teams() {
    cout << "Welcome to our Farm-out project teams!" << endl;
}

int main() {
    if (prompt_yes_or_no("Are you inspired to make the world a better place?")
        && prompt_yes_or_no("Do you want to be part of projects that cover the entire process, "
                            "from edge to cloud and from driver to (front-end) application?")
        && prompt_yes_or_no("Do you want to work on (big scaled) high-tech systems?")
        && prompt_yes_or_no("Do you enjoy responsibility and leadership roles?")
        && prompt_yes_or_no("Do you love challenges in complex architecture for distributed systems?")) {
        join_farm_out_project_teams();
    } else {
        cout << "Thank you for considering us! Keep exploring new opportunities!" << endl;
    }

    return 0;
}

for i=1 to n
   for j=1 to n    
     c[i][j]=0
     for k=1 to n
         c[i][j] = c[i][j]+a[i][k]*b[k][j]