Snippets Collections
#include <iostream>
#include "Rectangle.h"
using namespace std;
float calculateArea(float, float);//function prototype
float calculatePerimter(float, float)//function prototype
int main() {
	float length, width, area, perimeter;
	cout << "Enter the values of the length and wdith: ";
	cin >> length >> width;

	area = calculateArea(length, width);
	perimeter - calculatePerimter(length, width);
}
//function defenition
float calculateArea(float length, float width) {
	return length * width;
}
//function defenition
float calculatePeremiter(float length, float width) {
	return 2* (length + width)
}
  { 8,              40,          8,           1,        40 ,     8,       8,      3,       3,  {0xFF, 0xFF, 0x99, 0x99, 0xE7, 0xC3, 0xC3, 0xDB} ,     34,     -34}, // Minecraft Creeper Hard Mode
  { 12,             70,          8,           1,        40 ,     8,       8,      3,       5,  {0xFF, 0xFF, 0x99, 0x99, 0xE7, 0xC3, 0xC3, 0xDB} ,     28,     -28}, // Minecraft Creeper EZ Mode
  { 12,             70,          8,           1,        40 ,     8,       8,      3,       5,  {0xFF, 0xFF, 0x99, 0x99, 0xE7, 0xC3, 0xC3, 0xDB} ,     28,     -28}, // Minecraft Creeper Placeholder for Hard Mode (Part 3)
#define GAMES_NUMBER 14 // Define the number of different game boards
// Author : Khadiza Sultana
// Date : 1/4/2025
#include <iostream>
#include <vector>
using namespace std;

int search(vector<int>& nums, int target) {
    int st = 0, end = nums.size() - 1;
    while (st <= end) {
        int mid = st + (end - st) / 2;
        if (nums[mid] == target) {
            return mid;
        }
        if (nums[st] <= nums[mid]) { // Left half is sorted
            if (nums[st] <= target && target <= nums[mid]) {
                end = mid - 1;
            } else {
                st = mid + 1;
            }
        } else { // Right half is sorted
            if (nums[mid] <= target && target <= nums[end]) {
                st = mid + 1;
            } else {
                end = mid - 1;
            }
        }
    }
    return -1;
}

int main() {
    vector<int> nums = {4, 5, 6, 7, 0, 1, 2};
    int target = 0;

    int result = search(nums, target);

    if (result != -1) {
        cout << "Target " << target << " found at index: " << result << endl;
    } else {
        cout << "Target " << target << " not found in the array." << endl;
    }

    return 0;
}
// Author : Khadiza Sultana
// Date : 1/4/2025
#include<iostream>
#include<vector>
using namespace std;

int binarySearch(vector<int>&arr, int tar) { // practical implementation
    int n = arr.size();
    int st = 0, end = n-1;
    while(st <= end) {
        int mid = st + (end-st)/2; // not using (st+end)/2 to avoid integer overflow
        if (tar > arr[mid]) {
            st = mid+1;
        }
        else if (tar < arr[mid]) {
            end = mid-1;
        }
        else {
            return mid;
        }
    }
    return -1;
}

int binarySearch2(vector<int>&arr, int tar, int st, int end) { // recursive implementation
    if (st > end) { // base case
        return -1;
    }
    int mid = st + (end-st)/2;
    if (tar > arr[mid]) {
        binarySearch2(arr, tar, mid+1, end);
    }
    else if (tar < arr[mid]) {
        binarySearch2(arr, tar, st, mid-1);
    }
    else {
        return mid;
    }
}

int main() {
    vector<int>arr1 = {3, 5, 7, 12, 15, 18}; // even no of elements
    int tar1 = 3;
    vector<int>arr2 = {4, 6, 10, 11, 12, 18, 19}; // odd no of elements
    int tar2 = 19;

    cout << "Index at which tar1 is found(even no of elements) : " << binarySearch(arr1, tar1) << endl;
    cout << "Index at which tar2 is found(odd no of elements) : " << binarySearch(arr2, tar2) << endl;
    
    cout << "Using Recusive function index at which tar1 is found : " << binarySearch2(arr1, tar1, 0, 5) << endl;
    cout << "Using Recusive function index at which tar1 is found : " << binarySearch2(arr2, tar2, 0, 6) << endl;

    return 0;
}
// Author : Khadiza Sultana
#include<iostream>
#include<vector>
using namespace std;

int main() {
    int a = 10;
    int* ptr = &a;
    int** parPtr = &ptr;
    cout << ptr << endl;
    cout << parPtr << endl;
    cout << *(&a) << endl;
    cout << *(ptr) << endl;
    cout << *(parPtr) << endl;
    cout << **(parPtr) << endl;
    return 0;
}
      remainderAnswer = String(answer) + String(" rem ") + String(remainder); // Create a String combining the Integer Division "answer", "rem" for remainder, and remainder answer "remainder"
      ans = remainderAnswer; // Pass the "remainderAnswer" to the "ans" variable
      remainder = num1.toInt() % num2.toInt(); // Calculate the remainder from the division operation using the "%" operator
int               remainder; // Integer variable to hold the result of the "%" operation
String            remainderAnswer; // String variable to hold the integer division and remainder operation results
#include <iostream>

void swap(int &a, int &b) {
    int temp = a; // Store the value of a in a temporary variable
    a = b;        // Assign the value of b to a
    b = temp;    // Assign the value of temp (original a) to b
}

int main() {
    int x = 5;
    int y = 10;

    std::cout << "Before swap: x = " << x << ", y = " << y << std::endl;
    swap(x, y); // Call the swap function
    std::cout << "After swap: x = " << x << ", y = " << y << std::endl;

    return 0;
}
#include <iostream>
#include <stdexcept>
#include <string>

int main() {
	setlocale(LC_ALL, "RU");

	class Car {
	private:
		std::string name; // Приватное поле
		int mx_speed; // Приватное поле

	public:
		Car(const std::string& name, int mx_speed) {
			setName(name);
			setMaxspeed(mx_speed);
		}

		void setName(const std::string& name) {
			this->name = name;
		}

		std::string getName() const {
			return name;
		}

		void setMaxspeed(int mx_speed) {
			if (mx_speed < 0) {
				throw std::invalid_argument("Скорость машины не может быть отрицательной.");
			}
			this->mx_speed = mx_speed;
		}

		int getMaxspeed() const {
			return mx_speed;
		}
	};

	// Производный класс
	class Porshe : public Car {
	private:
		std::string color; // Новое поле

	public:
		Porshe(const std::string& name, int mx_speed, const std::string& color)
			: Car(name, mx_speed), color(color) {}

		void display() const {
			std::cout << "Porshe: " << getName() << ", Максимальная скорость: " << getMaxspeed() << ", Цвет: " << color << std::endl;
		}
	};

	// Класс, основанный на двух других
	class Price : public Porshe {
	private:
		int cost; // Новое поле

	public:
		Price(const std::string& name, int mx_speed, const std::string& color, int cost)
			: Porshe(name, mx_speed, color), cost(cost) {}

		void showPrice() const {
			display();
			std::cout << "Цена: " << cost << std::endl;
		}
	};

	// Класс, наследующий от Rose
	class SpecialPorshe : public Porshe {
	public:
		using Porshe::Porshe; // Наследуем конструктор

	private:
		// Доступ к полям базового класса ограничен
		void setColor(const std::string& color) {
			// Метод для изменения цвета, доступен только в классе
		}
	};

	// Основная функция
	try {
		Car car("Porshe Cayenne", 260);
		car.setMaxspeed(300);
		std::cout << "Машина: " << car.getName() << ", Максимальная скорость: " << car.getMaxspeed() << std::endl;

		Porshe porshe("Porshe Macan", 330, "Голубой");
		porshe.display();

		Price price("Porshe Panamera", 250, "Белый", 3000000);
		price.showPrice();

		SpecialPorshe specialPorshe("Porshe 911", 330, "Синий");
		// specialRose.setColor("Зеленый"); // Это вызовет ошибку, так как метод недоступен в main

	}
	catch (const std::invalid_argument& e) {
		std::cerr << "Ошибка: " << e.what() << std::endl;
	}

	return 0;
}
 webPage += "<br> 18 - Pikachu<br> 19 - Poke Ball";
else if(spriteInc == 18) { blitRGB(pokeball); }
static uint8_t pokeball[RGB_SPRITE_WIDTH * RGB_SPRITE_HEIGHT] = {
    0x00, 0x00, 0x00,   0xFF, 0x00, 0x00,   0xFF, 0x00, 0x00,   0xFF, 0x00, 0x00,   0xFF, 0x00, 0x00,   0xFF, 0x00, 0x00,   0xFF, 0x00, 0x00,   0x00, 0x00, 0x00,
    0xFF, 0x00, 0x00,   0xFF, 0xFF, 0xFF,   0xFF, 0xFF, 0xFF,   0xFF, 0x00, 0x00,   0xFF, 0x00, 0x00,   0xFF, 0x00, 0x00,   0xFF, 0x00, 0x00,   0xFF, 0x00, 0x00,
    0xFF, 0x00, 0x00,   0xFF, 0xFF, 0xFF,   0xFF, 0x00, 0x00,   0xFF, 0x00, 0x00,   0xFF, 0x00, 0x00,   0xFF, 0x00, 0x00,   0xFF, 0x00, 0x00,   0xFF, 0x00, 0x00,
    0xFF, 0x00, 0x00,   0xFF, 0x00, 0x00,   0xFF, 0x00, 0x00,   0x00, 0x00, 0x00,   0x00, 0x00, 0x00,   0x00, 0x00, 0x00,   0xFF, 0x00, 0x00,   0xFF, 0x00, 0x00,
    0x00, 0x00, 0x00,   0x00, 0x00, 0x00,   0x00, 0x00, 0x00,   0x00, 0x00, 0x00,   0xFF, 0xFF, 0xFF,   0x00, 0x00, 0x00,   0x00, 0x00, 0x00,   0x00, 0x00, 0x00,
    0xFF, 0xFF, 0xFF,   0xFF, 0xFF, 0xFF,   0xFF, 0xFF, 0xFF,   0x00, 0x00, 0x00,   0x00, 0x00, 0x00,   0x00, 0x00, 0x00,   0xFF, 0xFF, 0xFF,   0xFF, 0xFF, 0xFF,
    0xFF, 0xFF, 0xFF,   0xFF, 0xFF, 0xFF,   0xFF, 0xFF, 0xFF,   0xFF, 0xFF, 0xFF,   0xFF, 0xFF, 0xFF,   0xFF, 0xFF, 0xFF,   0xFF, 0xFF, 0xFF,   0xFF, 0xFF, 0xFF,
    0x00, 0x00, 0x00,   0xFF, 0xFF, 0xFF,   0xFF, 0xFF, 0xFF,   0xFF, 0xFF, 0xFF,   0xFF, 0xFF, 0xFF,   0xFF, 0xFF, 0xFF,   0xFF, 0xFF, 0xFF,   0x00, 0x00, 0x00
};
// Challenge Solution
  // Create functions for 6 points: the pre-pickup, the pickup, the lift, the move, 
  // the place, and the departure. Set a small delay between each of these points.
  Position_1(); // Pre-pickup position
  delay(1000);  // Short Delay
  Position_2(); // Pickup position
  delay(1000);  // Short Delay
  Position_3(); // Lift Position
  delay(1000);  // Short Delay
  Position_4(); // Move Position
  delay(1000);  // Short Delay
  Position_5(); // Place Position
  delay(1000);  // Short Delay
  Position_6(); // Departure Position
  delay(5000);  // Long Delay before next loop
  // End Challenge Solution
// Challenge Solution Functions
void Position_1() // Starting "Prep" position
{
  // Set the target positions to the starting positions
  posBase = 125;
  posShoulder = 55;
  posElbow = 50;
  posGripper = 0;

  // Write the starting position to each servo.
  servoBase.write(posBase);
  servoShoulder.write(posShoulder);
  servoElbow.write(posElbow);
  servoGripper.write(posGripper);
}


void Position_2() // "Grab" position
{
  // Set the target positions to the starting positions
  posBase = 125;
  posShoulder = 75;
  posElbow = 40;
  posGripper = 90;

  // Write the starting position to each servo.
  servoBase.write(posBase);
  servoShoulder.write(posShoulder);
  servoElbow.write(posElbow);
  servoGripper.write(posGripper);
}


void Position_3() // "Lift" position
{
  // Set the target positions to the starting positions
  posBase = 125;
  posShoulder =55;
  posElbow = 90;
  posGripper = 90;

  // Write the starting position to each servo.
  servoBase.write(posBase);
  servoShoulder.write(posShoulder);
  servoElbow.write(posElbow);
  servoGripper.write(posGripper);
}


void Position_4() // "Move" Position
{
  // Set the target positions to the starting positions
  posBase = 55;
  posShoulder =55;
  posElbow = 90;
  posGripper = 90;

  // Write the starting position to each servo.
  servoBase.write(posBase);
  servoShoulder.write(posShoulder);
  servoElbow.write(posElbow);
  servoGripper.write(posGripper);
}


void Position_5() // "Place" Position
{
  // Set the target positions to the starting positions
  posBase = 55;
  posShoulder = 75;
  posElbow = 40;
  posGripper = 60;

  // Write the starting position to each servo.
  servoBase.write(posBase);
  servoShoulder.write(posShoulder);
  servoElbow.write(posElbow);
  servoGripper.write(posGripper);
}


void Position_6() // "Depart" Position
{
  // Set the target positions to the starting positions
  posBase = 55;
  posShoulder = 55;
  posElbow = 50;
  posGripper = 0;

  // Write the starting position to each servo.
  servoBase.write(posBase);
  servoShoulder.write(posShoulder);
  servoElbow.write(posElbow);
  servoGripper.write(posGripper);
}
else {
   leftServo.write(90);
   rightServo.write(90);
}
else if(leftJoystick > 600) {
    leftJSVal = map(leftJoystick, 600, 1023, 85, 80);
    rightJSVal = map(leftJoystick, 600, 1023, 95, 100);

    if(rightJoystick < 420) {
      rightJSVal = rightJSVal + map(rightJoystick, 420, 0, 1, 75);
    }
    else if(rightJoystick > 600) {
      leftJSVal = leftJSVal - map(rightJoystick, 600, 1023, 1, 75);
    }

    leftServo.write(leftJSVal);
    rightServo.write(rightJSVal);
  }
leftServo.write(leftJSVal);
rightServo.write(rightJSVal);
    if(rightJoystick < 420) {
      rightJSVal = rightJSVal - map(rightJoystick, 420, 0, 1, 75);
    }
    else if(rightJoystick > 600) {
      leftJSVal = leftJSVal + map(rightJoystick, 600, 1023, 1, 75);
    }
if(leftJoystick < 420) {
   leftJSVal = map(leftJoystick, 420, 0, 95, 100);
   rightJSVal = map(leftJoystick, 420, 0, 85, 80);

}
       //Display "Super Secret Message"
        lcd.clear();
        // Set the LCD cursor to the second line, 4th position
        lcd.setCursor(4,1);
        // Write 'Super Secret' beginning at that location
        lcd.print("Super Secret");
        // Move cursor to the third line, 8th position
        lcd.setCursor(7,2);
        // Write 'Message' beginning at that location
        lcd.print("Message");
        // Display the message for 5-seconds
        delay(5000);
        // Clear the display to prepare for the next time update
        lcd.clear();
      // If the knob is in this range, display a message
      if((anaAlarm > 400) && (anaAlarm < 425)) {

      }
      // Read the Dial Potentiometer value
      anaAlarm = analogRead(A1);
 
#include <iostream>
#include <stdexcept>
#include <string>

int main() {
    setlocale(LC_ALL, "RU");

    class Flower {
    private:
        std::string name; // Приватное поле
        int petals; // Приватное поле

    public:
        Flower(const std::string& name, int petals) {
            setName(name);
            setPetals(petals);
        }

        void setName(const std::string& name) {
            this->name = name;
        }

        std::string getName() const {
            return name;
        }

        void setPetals(int petals) {
            if (petals < 0) {
                throw std::invalid_argument("Количество лепестков не может быть отрицательным.");
            }
            this->petals = petals;
        }

        int getPetals() const {
            return petals;
        }
    };

    // Производный класс
    class Rose : public Flower {
    private:
        std::string color; // Новое поле

    public:
        Rose(const std::string& name, int petals, const std::string& color)
            : Flower(name, petals), color(color) {}

        void display() const {
            std::cout << "Роза: " << getName() << ", Лепестки: " << getPetals() << ", Цвет: " << color << std::endl;
        }
    };

    // Класс, основанный на двух других
    class Bouquet : public Rose {
    private:
        int quantity; // Новое поле

    public:
        Bouquet(const std::string& name, int petals, const std::string& color, int quantity)
            : Rose(name, petals, color), quantity(quantity) {}

        void showBouquet() const {
            display();
            std::cout << "Количество: " << quantity << std::endl;
        }
    };

    // Класс, наследующий от Rose
    class SpecialRose : public Rose {
    public:
        using Rose::Rose; // Наследуем конструктор

    private:
        // Доступ к полям базового класса ограничен
        void setColor(const std::string& color) {
            // Метод для изменения цвета, доступен только в классе
        }
    };

    // Основная функция
    try {
        Flower flower("Тюльпан", 5);
        flower.setPetals(10);
        std::cout << "Цветок: " << flower.getName() << ", Лепестки: " << flower.getPetals() << std::endl;

        Rose rose("Роза", 8, "Красный");
        rose.display();

        Bouquet bouquet("Букет", 6, "Белый", 12);
        bouquet.showBouquet();

        SpecialRose specialRose("Специальная Роза", 7, "Синий");
        // specialRose.setColor("Зеленый"); // Это вызовет ошибку, так как метод недоступен в main

    }
    catch (const std::invalid_argument& e) {
        std::cerr << "Ошибка: " << e.what() << std::endl;
    }

    return 0;
}
// Author : Khadiza Sultana
#include<iostream>
#include<vector>
using namespace std;
int LinearSearch(vector<int> &vec, int target){
    int i = 0;
    for(int val : vec){
        if(val == target)
           return i;
        i++;
    }
    return -1;
}
int main(){
    vector<int> vec = {1, 2, 5, 8, 5, 7, 8};
    int target = 7;
    cout << LinearSearch(vec, target) << endl;
    return 0;
}
// Khadiza Sultana
#include<iostream>
#include <climits>
using namespace std;
int sum(int arr[], int size){
    int sum = 0;
    for(int i = 0; i < size; i++){
        sum += arr[i];
    }
    return sum;
}
int product(int arr[], int size){
    int product = 1;
    for(int i = 0; i < size; i++){
        product *= arr[i];
    }
    return product;
}
void swap(int &a, int &b){
    a = a + b;
    b = a - b;
    a = a - b;
}
void uniqueElement(int arr[], int size){
    for(int i = 0; i < size; i++){
        bool isUnique = true;
        for(int j = 0; j < size; j++){
            if(i != j && arr[i] == arr[j]){
                isUnique = false;
                break;
            }
        }
        if(isUnique) cout << arr[i] << " ";
    }
    cout << endl;
} 
void reverseMinAndMax(int arr[], int size){
    int largest = INT_MIN, smallest = INT_MAX, largest_index = -1, smallest_index = -1;
    for(int i = 0; i < size; i++){
        if(arr[i] > largest){
            largest = arr[i];
            largest_index = i;
        }
        if(arr[i] < smallest){
            smallest = arr[i];
            smallest_index = i;
        }
    }
    swap(arr[largest_index], arr[smallest_index]);
    for(int i = 0; i < size; i++){
        cout << arr[i] << " ";
    }
    cout << endl;
}
void intersection(int arr1[], int size1, int arr2[], int size2){
    for(int i = 0; i < size1; i++){
        bool repeated = false;
        for(int j = 0; j < size1; j++){
            if(i != j && arr1[i] == arr1[j]){
               repeated = true;
               break;
            }
        }
        if(repeated) arr1[i] = INT_MAX;
        for(int j = 0; j < size2; j++){
            if(arr1[i] == arr2[j]){
               cout << arr1[i] << " ";
               break;
            }
        }

    }
    cout << endl;
}
int main(){
    int arr1[] = {1, 2, 4, 6, 4, 6, 2, 5, 9};
    int size1 = sizeof(arr1) / sizeof(int);
    int arr2[] = {2, 4, 3, 5, 8, 6, 3};
    int size2 = sizeof(arr2) / sizeof(int);
    cout << "Sum of elements : " << sum(arr1, size1) << endl;
    cout << "Product of elements : " << product(arr1, size1) << endl;
    cout << "The elements of the first array after the maximum element and minimum element are reversed : ";
    reverseMinAndMax(arr1, size1);
    cout << "The unique elements in the first array : ";
    uniqueElement(arr1, size1);
    cout << "The intersecting elements between the first and second array : ";
    intersection(arr1, size1, arr2, size2);
    return 0;
}
// Author : Khadiza Sultana 
#include<iostream>
 using namespace std;
  int binTodec(int binNum){
    int ans = 0, pow = 1;
    while(binNum > 0){
        int rem = binNum % 10; // accessing the last digit
        ans += rem * pow;
        binNum /= 10; // removing the last digit
        pow *= 2;
    }
    return ans;
  }

  int main(){
    int binNum;
    cin >> binNum;
    cout << binTodec(binNum) << endl;
    return 0;
  }
// Author : Khadiza Sultana
#include<iostream>
using namespace std;

int decimalToBinary(int decNum){
    int ans = 0, pow = 1;
    while(decNum > 0){
        int rem = decNum % 2; // documenting the remainder for example for 3 % 2 = 1
        decNum /= 2; // determining the divisor 3 / 2 = 1
        ans += (rem * pow); // determining the position for the remainder as it goes from down to up
        pow *= 10; // updating the position of the digits
    }
    return ans;
}

int main(){
    int decNum = 50;  
    cout << decimalToBinary(decNum) << endl;
    return 0;
}
// Khadiza Sultana
#include<iostream>
using namespace std;
int primecheck(int n){
    bool isprime = true;
    for(int i = 2; i * i <= n; i++){
        if(n % i == 0){
            isprime = false;
            return false;
        }
    }
    if(isprime)
       return true;
}
void printprime(int num){
    for(int i = 2; i <= num; i++){
        if(primecheck(i))
           cout << i << " ";
    }
}
int primecount(int num){
    int count = 0;
    for(int i = 2; i <= num; i++){
        if(primecheck(i))
           count++;
    }
    return count;
}
int main(){
    int num;
    cin >> num;
    printprime(num);
    cout << endl;
    cout << primecount(num) << endl;
    return 0;
}
#include <Wire.h>
#include <LiquidCrystal_I2C.h>
LiquidCrystal_I2C lcd(0x27, 16, 2);

//Initialize the pins
int moisture = A0;
int manual = A2;
int relay = 8;

//Setup
void setup() {
  pinMode(relay, OUTPUT);
  lcd.init();
  lcd.backlight();
  lcd.setCursor(2, 0);
  lcd.print("Initializing");
  lcd.setCursor(0, 1);
  lcd.print("STYRERIUM MODULE");
  Serial.begin(9600);
  delay(10000);

}
void loop() {
  lcd.clear();
  //Convert to percentage
  int moistureValue = analogRead(moisture);
  int moisturePercent = map(moistureValue, 0, 1023, 100, 0);
  int manualValue = analogRead(manual);
  int manualPercent = map(manualValue, 0, 1023, 0, 100);
  //Relay control
  if (moisturePercent < 13 || moisturePercent < manualPercent) {
    digitalWrite(relay, HIGH);
  } else {  //Turn off relay
    digitalWrite(relay, LOW);
  }
  //Displaying the stats
  lcd.setCursor(0, 0);
  lcd.print("Moisture: ");
  lcd.setCursor(12, 0);
  lcd.print(moisturePercent);
  lcd.print("%");
  //Manual watering display
  lcd.setCursor(0, 1);
  lcd.print("Manual: ");
  lcd.setCursor(12, 1);
  lcd.print(manualPercent);
  lcd.print("%");
  delay(100);
}
#include <Wire.h>
#include "DHT.h"
#include <LiquidCrystal_I2C.h>
//Define DHT pin and type
#define DHTPIN 9
#define DHTTYPE DHT11
//Initialize the sensor and LCD
LiquidCrystal_I2C lcd(0x27, 16, 2);
DHT dht(DHTPIN, DHTTYPE);

const int pumpPin = 8;
const int soilMoisturePin = A0;
const int potentiometerPin = A2;
unsigned long pumpStartTime = 0;  // unsigned: only >=0
bool pumpRunning = false;

void setup() {
  lcd.init();
  lcd.backlight();
  dht.begin();

  pinMode(pumpPin, OUTPUT);
  pinMode(soilMoisturePin, INPUT);
  pinMode(potentiometerPin, INPUT);
  lcd.setCursor(2, 0);
  lcd.print("Initializing");
  lcd.setCursor(0, 1);
  delay(2000);
  lcd.clear();
}

void loop() {
  int moistureValue = analogRead(soilMoisturePin);        // Read current soil moisture level
  int potentiometerValue = analogRead(potentiometerPin);  // Read potentiometer value
  int targetMoisturePercent;
  // Map values to percentage
  int moisturePercent = map(moistureValue, 1023, 0, 0, 100);
  int potentiometerPercent = map(potentiometerValue, 0, 1023, 0, 100);
  if (potentiometerPercent >= 40) {
  targetMoisturePercent = potentiometerPercent;
  } else {
    targetMoisturePercent = 40;
  }
  // Check if pump should be running
  if (pumpRunning) {
    unsigned long elapsedTime = millis() - pumpStartTime;

    // If pump has been running for 20 seconds and soil moisture hasn't increased
    if (elapsedTime >= 20000 && moisturePercent <= 30) {
      lcd.clear();
      lcd.setCursor(0, 0);
      lcd.print("Low water! Pump");
      lcd.setCursor(0, 1);
      lcd.print("stopped.");

      // Stop the pump
      digitalWrite(pumpPin, LOW);
      pumpRunning = false;
      delay(20000);
      lcd.clear();
    }
    // Stop the pump if desired soil moisture level is reached
    else if (moisturePercent >= targetMoisturePercent) {
      digitalWrite(pumpPin, LOW);  // Stop the pump
      pumpRunning = false;

      lcd.clear();
      lcd.setCursor(0, 0);
      lcd.print("Plants watered!");
      lcd.setCursor(7, 1);
      lcd.print(":)");
      delay(2000);  // Display message for 2 seconds
      lcd.clear();
    } else {
      lcd.setCursor(0, 0);
      lcd.print("Pump running...");
      lcd.setCursor(0, 1);
      lcd.print("Soil: ");
      lcd.print(moisturePercent);
      lcd.print("% Man: ");
      lcd.print(potentiometerPercent);
      lcd.print("%");
    }
  } else {
    float h = dht.readHumidity();
    // Read temperature as Celsius (the default)
    float t = dht.readTemperature();
    if (isnan(h) || isnan(t)) {
      Serial.println(F("Failed to read from DHT sensor!"));
    }
    // If pump has stopped, continuously display moisture and potentiometer levels
    lcd.setCursor(0, 0);
    lcd.print("Mst:");
    lcd.print(moisturePercent);
    lcd.print("%  ");

    lcd.setCursor(8, 0);
    lcd.print("Tmp:");

    if (!isnan(t)) {
      lcd.print(t);
      lcd.print("oC ");
    }
    lcd.setCursor(8, 1);
    lcd.print("Hum:");
    if (!isnan(h)) {
      lcd.print(h);
      lcd.print("% ");
    }

    lcd.setCursor(0, 1);
    lcd.print("Man:");
    lcd.print(potentiometerPercent);
    lcd.print("% ");


    // Start the pump if potentiometerPercent is above 50% and soil is below target
    if (moisturePercent < targetMoisturePercent) {
      digitalWrite(pumpPin, HIGH);
      pumpStartTime = millis();
      pumpRunning = true;

      lcd.clear();
      lcd.setCursor(0, 0);
      lcd.print("Pump running...");
    }
  }

  delay(2000);  // Adjust delay as needed to update readings
}
//
//#include <iostream> 
//using namespace std;
//
//int main() {
//    int n;
//    setlocale(LC_ALL, "");
//    cout << "Введите количество чисел: ";
//    cin >> n;
//    int* arr = new int[n];
//
//    // Ввод чисел в массив 
//    cout << "Введите " << n << " чисел:" << endl;
//    for (int i = 0; i < n; ++i) {
//        cin >> *(arr+i);
//    }
//
//    // Поиск наибольшего числа
//    int max_value = *(arr);
//
//    for (int i = 1; i < n; ++i) {
//        if (arr[i] > max_value) {
//            max_value = *(arr+i);
//        }
//    }
//
//    // Вывод результата 
//    cout << "Наибольшее число: " << max_value << endl;
//    delete[] arr;
//    return 0;
//
//}

//#include<iostream>
//#include<vector>
//#include<windows.h>
//using namespace std;
//
//int main()
//{
//    SetConsoleCP(1251);
//    SetConsoleOutputCP(1251);
//    int n; // Количествострок
//    cout << "Введите количество строк: ";
//    cin >> n;
//
//    vector<string>lines; // Вектор для хранения строк
//
//    // Ввод строк
//    cout << "Введите " << n << " строк:" << endl;
//    for (int i = 0; i < n; ++i)
//    {
//        string line;
//        cin >> line; // Считываем строку без пробелов
//
//        // Вставляем строку в отсортированное место
//        vector<string>::iterator it = lines.begin();
//        while (it != lines.end() && *it < line)
//        {
//            ++it; // Находим место для вставки
//        }
//        lines.insert(it, line); // Вставляемстроку
//    }
//
//    // Вывод результата
//    cout << "Строки в алфавитном порядке:" << endl;
//    for (vector<string>::size_type i = 0; i < lines.size(); ++i)
//    {
//        cout << lines[i] << endl;
//    }
//
//    return 0;
//}
//

#include <iostream>
#include <windows.h>
using namespace std;

void print_array_using_pointers(int r, int c, int* ptr)
{
	int i, j;
	for (i = 0; i < r; i++)
	{
		cout << "[";
		for (j = 0; j < c; j++)
		{
			cout << " " << *ptr;
			ptr = ptr + 1;
		}
		cout << " ]" << endl;
	}
	return;
}

double determinant(int m, int* p)
{
	double ans = 0, inner_sol, inner_determinant;
	int a, b, c, d;

	if ((m == 1) || (m == 2))
	{
		if (m == 1)
			ans = *p;
		else
		{
			a = *p;
			b = *(p + 1);
			c = *(p + 2);
			d = *(p + 3);
			ans = (a * d) - (b * c);
		}
	}
	else
	{
		int i, j, k, l, n, sign, basic, element;
		n = 0;
		sign = +1;
		int* q;
		q = new int[(m - 1) * (m - 1)];

		for (i = 0; i < m; i++)
		{
			l = 0;
			n = 0;
			basic = *(p + i);

			for (j = 0; j < m; j++)
			{
				for (k = 0; k < m; k++)
				{
					element = *(p + l);
					cout << element << " ";
					if ((j == 0) || (i == k));
					else
					{
						*(q + n) = element;
						n = n + 1;
					}
					l = l + 1;
				}
			}
			cout << endl << basic << " x " << endl;
			print_array_using_pointers((m - 1), (m - 1), q);

			inner_determinant = determinant(m - 1, q);
			inner_sol = sign * basic * inner_determinant;

			cout << "Знак:" << sign << "x Базис: " << basic << "x Определитель" << inner_determinant << " = " << inner_sol << endl;
			ans = ans + inner_sol;
			sign = sign * -1;
		}
		delete[] q;
	}
	return ans;
}

void initialize_array(int r, int c, int* ptr)
{
	int i, j, k;
	cout << "Вводите числа в матрицу" << endl;
	cout << "После каждого числа нажимайте Enter" << endl;

	for (i = 0; i < r; i++)
	{
		for (j = 0; j < c; j++)
		{
			cin >> k;
			*(ptr + i * c + j) = k;

		}
	}
}

int main()
{
	SetConsoleCP(1251);
	SetConsoleOutputCP(1251);


	int r, * p;
	cout << "Количество рядов: ";
	cin >> r;

	p = new int[r * r];

	initialize_array(r, r, p);
	print_array_using_pointers(r, r, p);
	double ans = determinant(r, p);

	cout << "Определитель: " << ans << endl;
	delete[] p;

	return 0;

}
#include <iostream>
#include <windows.h>
using namespace std;

void print_array_using_pointers(int r, int c, int* ptr)
{
	int i, j;
	for (i = 0; i < r; i++)
	{
		cout << "[";
		for (j = 0; j < c; j++)
		{
			cout << " " << *ptr;
			ptr = ptr + 1;
		}
		cout << " ]" << endl;
	}
	return;
}

double determinant(int m, int* p)
{
	double ans = 0, inner_sol, inner_determinant;
	int a, b, c, d;

	if ((m == 1) || (m == 2))
	{
		if (m == 1)
			ans = *p;
		else
		{
			a = *p;
			b = *(p + 1);
			c = *(p + 2);
			d = *(p + 3);
			ans = (a * d) - (b * c);
		}
	}
	else
	{
		int i, j, k, l, n, sign, basic, element;
		n = 0;
		sign = +1;
		int* q;
		q = new int[(m - 1) * (m - 1)];

		for (i = 0; i < m; i++)
		{
			l = 0;
			n = 0;
			basic = *(p + i);

			for (j = 0; j < m; j++)
			{
				for (k = 0; k < m; k++)
				{
					element = *(p + l);
					cout << element << " ";
					if ((j == 0) || (i == k));
					else
					{
						*(q + n) = element;
						n = n + 1;
					}
					l = l + 1;
				}
			}
			cout << endl << basic << " x " << endl;
			print_array_using_pointers((m - 1), (m - 1), q);

			inner_determinant = determinant(m - 1, q);
			inner_sol = sign * basic * inner_determinant;

			cout << "Знак:" << sign << "x Базис: " << basic << "x Определитель" << inner_determinant << " = " << inner_sol << endl;
			ans = ans + inner_sol;
			sign = sign * -1;
		}
		delete[] q;
	}
	return ans;
}

void initialize_array(int r, int c, int* ptr)
{
	int i, j, k;
	cout << "Вводите числа в матрицу" << endl;
	cout << "После каждого числа нажимайте Enter" << endl;

	for (i = 0; i < r; i++)
	{
		for (j = 0; j < c; j++)
		{
			cin >> k;
			*(ptr + i * c + j) = k;

		}
	}
}

int main()
{
	SetConsoleCP(1251);
	SetConsoleOutputCP(1251);


	int r, * p;
	cout << "Количество рядов: ";
	cin >> r;

	p = new int[r * r];

	initialize_array(r, r, p);
	print_array_using_pointers(r, r, p);
	double ans = determinant(r, p);

	cout << "Определитель: " << ans << endl;
	delete[] p;

	return 0;

}
#include <iostream>
#include <vector>
using namespace std; 
 
int main() {
    vector<int> arr = { 64, 34, 25, 12, 22, 11, 90 };
    int n = arr.size();
    bool swapped;
  
    for (int i = 0; i < n - 1; i++) {
        swapped = false;
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
            }
        }
      
        // If no two elements were swapped, then break
        if (!swapped)
            break;
    }
    
    for (int num : arr)
        cout << " " << num;
}
#include <iostream>
#include <vector>
using namespace std; 
 
int main() { 
    int n; 
    setlocale(LC_ALL, ""); 
    cout <<"Введите количество чисел: ";
    cin >> n;
	std::vector <int> arr(n);
 
    // Ввод чисел в массив 
    cout << "Введите " << n << " чисел:" << endl; 
    for (int i = 0; i < n; ++i) { 
        cin >> arr[i]; 
    } 
 
    // Поиск наибольшего числа  
    int max_value = arr[0];              
 
    for (int i = 1; i < n; ++i) { 
        if (arr[i] > max_value) { 
            max_value = arr[i]; 
        } 
    } 
 
    // Вывод результата 
    cout << "Наибольшее число: " << max_value<< endl; 
 
    return 0;
    
}
#include <iostream> 
using namespace std; 
 
int main() { 
    int n; 
    setlocale(LC_ALL, ""); 
    cout <<"Введите количество чисел: ";
    cin >> n;
    int *arr = new int[n];
 
    // Ввод чисел в массив 
    cout << "Введите " << n << " чисел:" << endl; 
    for (int i = 0; i < n; ++i) { 
        cin >> arr[i]; 
    } 
 
    // Поиск наибольшего числа
    int max_value = arr[0];              
 
    for (int i = 1; i < n; ++i) { 
        if (arr[i] > max_value) { 
            max_value = arr[i]; 
        } 
    } 
 
    // Вывод результата 
    cout << "Наибольшее число: " << max_value<< endl; 
 	delete[] arr;
    return 0;
    
}
class DisjointSet {
    vector<int> rank, parent, size;
    
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 findUPar(int node) {
        if (node == parent[node])
            return node;
        return parent[node] = findUPar(parent[node]); // Path compression
    }

    void unionByRank(int u, int v) {
        int pu = findUPar(u);
        int pv = findUPar(v);
        if (pu == pv) return;

        if (rank[pu] < rank[pv]) {
            parent[pu] = pv;
        } else if (rank[pv] < rank[pu]) {
            parent[pv] = pu;
        } else {
            parent[pv] = pu;
            rank[pu]++;
        }
    }

    void unionBySize(int u, int v) {
        int pu = findUPar(u);
        int pv = findUPar(v);
        if (pu == pv) return;

        if (size[pu] < size[pv]) {
            parent[pu] = pv;
            size[pv] += size[pu];
        } else {
            parent[pv] = pu;
            size[pu] += size[pv];
        }
    }
};

class Solution {
public:
    vector<int> sp(int n) {
        vector<int> spf(n + 1);
        for (int i = 0; i <= n; ++i) spf[i] = i;
        for (int i = 2; i * i <= n; ++i) {
            if (spf[i] == i) {
                for (int j = i * i; j <= n; j += i) {
                    if (spf[j] == j) spf[j] = i;
                }
            }
        }
        return spf;
    }

    vector<int> fac(int x, vector<int>& spf) {
        vector<int> f;
        while (x > 1) {
            int p = spf[x];
            f.push_back(p);
            while (x % p == 0) x /= p;
        }
        return f;
    }

    int largestComponentSize(vector<int>& nums) {
        int n = nums.size();
        int maxNum = *max_element(nums.begin(), nums.end());

        vector<int> spf = sp(maxNum);
        DisjointSet ds(maxNum + 1);

        for (int num : nums) {
            vector<int> primes = fac(num, spf);
            for (int prime : primes) {
                ds.unionBySize(num, prime); // Union by size
            }
        }

        unordered_map<int, int> cnt;
        int maxSize = 0;
        for (int num : nums) {
            int root = ds.findUPar(num);
            cnt[root]++;
            maxSize = max(maxSize, cnt[root]);
        }

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

int mod = 1e9 + 7;
const int MAX = 1e5 + 1;

#define ll long long
#define ull unsigned long long
#define int64 long long int
#define vi vector<int>
#define pii pair<int, int>
#define ppi pair<pii>
#define all(v) v.begin(), v.end()
#define ff first
#define ss second
#define eb emplace_back
#define sz(x) (int(x.size()))
#define mset(dp, x) memset(dp, x, sizeof(dp))

int dir[5] = {0, 1, 0, -1, 0};
int dirI[8] = {1, 1, 0, -1, -1, -1, 0, 1}, dirJ[8] = {0, -1, -1, -1, 0, 1, 1, 1};

ll fact[MAX] = {1};

ll add(ll a, ll b)
{
    return (a % mod + b % mod) % mod;
}

ll sub(ll a, ll b)
{
    return (a % mod - b % mod + mod) % mod;
}

ll mul(ll a, ll b)
{
    return ((a % mod) * (b % mod)) % mod;
}

ll exp(ll a, ll b)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
            ans = (ans * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans;
}

ll inv(ll b)
{
    return exp(b, mod - 2) % mod;
}

ll division(ll a, ll b)
{
    return ((a % mod) * (inv(b) % mod)) % mod;
}

ll nCr(ll n, ll r)
{
    if (r > n)
        return 0;
    return division(fact[n], mul(fact[r], fact[n - r]));
}

ll nPr(ll n, ll r)
{
    if (r > n)
        return 0;
    return division(fact[n], fact[n - r]);
}

ll gcd(ll a, ll b)
{
    if (a == 0)
        return b;
    return gcd(b % a, a);
}

ll lcm(ll a, ll b)
{
    return (a * b) / gcd(a, b);
}

void pre(int _mod = mod)
{
    mod = _mod;
    fact[0] = 1;
    for (int i = 1; i < MAX; i++)
    {
        fact[i] = mul(fact[i - 1], i);
    }
}

void solve() {
    cout << "write code here" << "\n";
}

int main() {
	#ifndef ONLINE_JUDGE
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif

	int tt = 1;
	cin >> tt;
	while (tt--) {
		solve();
	}
	return 0;
}
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

ll gcd(ll a, ll b) {
  if(!a) return b;
  return gcd(b % a, a);
}

ll lcm(ll a, ll b) {
    return a * b / gcd(a, b);
}

int main() {
  cout << gcd(12, 18) << endl;
  cout << gcd(0, 18) << endl;
  cout << lcm(12, 18) << endl;
  return 0;
}
#include <iostream>
#include <vector>
using namespace std;

// Function to calculate the smallest prime factors (SPF)
vector<int> calculate_spf(int n) {
    vector<int> SPF(n + 1, 0); // SPF array initialized to 0

    for (int i = 2; i <= n; i++) {
        if (SPF[i] == 0) { // i is a prime number
            for (int j = i; j <= n; j += i) {
                if (SPF[j] == 0) { // Mark only if not marked
                    SPF[j] = i; // Assign smallest prime factor
                }
            }
        }
    }
    return SPF;
}

// Function to get the prime factors of a number using the SPF array
vector<int> get_prime_factors(int n, const vector<int>& SPF) {
    vector<int> prime_factors;
    while (n != 1) {
        prime_factors.push_back(SPF[n]);
        n /= SPF[n]; // Divide n by its smallest prime factor
    }
    return prime_factors;
}

int main() {
    int N = 100; // Precompute SPF array for numbers up to N
    vector<int> SPF = calculate_spf(N);

    // Example: Factorizing multiple numbers
    vector<int> numbers_to_factor = {30, 45, 84, 97};

    for (int num : numbers_to_factor) {
        cout << "Prime factors of " << num << ": ";
        vector<int> factors = get_prime_factors(num, SPF);
        for (int f : factors) {
            cout << f << " ";
        }
        cout << endl;
    }

    return 0;
}
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

// Function to perform the simple sieve of Eratosthenes up to sqrt(b)
vector<int> simple_sieve(int limit) {
    vector<bool> is_prime(limit + 1, true);
    vector<int> primes;
    is_prime[0] = is_prime[1] = false;

    for (int i = 2; i <= limit; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
            for (int j = i * i; j <= limit; j += i) {
                is_prime[j] = false;
            }
        }
    }
    return primes;
}

// Function to find all primes in the range [a, b] using the segmented sieve
void segmented_sieve(int a, int b) {
    int limit = sqrt(b);
    vector<int> primes = simple_sieve(limit);

    // Create a boolean array for the range [a, b]
    vector<bool> is_prime_segment(b - a + 1, true);

    // Mark multiples of each prime in the range [a, b]
    for (int prime : primes) {
        int start = max(prime * prime, a + (prime - a % prime) % prime);

        for (int j = start; j <= b; j += prime) {
            is_prime_segment[j - a] = false;
        }
    }

    // If a is 1, then it's not a prime number
    if (a == 1) {
        is_prime_segment[0] = false;
    }

    // Output all primes in the range [a, b]
    cout << "Prime numbers in the range [" << a << ", " << b << "] are:" << endl;
    for (int i = 0; i <= b - a; i++) {
        if (is_prime_segment[i]) {
            cout << (a + i) << " ";
        }
    }
    cout << endl;
}

int main() {
    int a = 10, b = 50;
    segmented_sieve(a, b);
    return 0;
}
#include <iostream>
#include <vector>
using namespace std;
void sieve_of_eratosthenes(int n) {
    vector<bool> is_prime(n + 1, true); // Initialize all entries as true
    is_prime[0] = is_prime[1] = false;  // 0 and 1 are not prime numbers
    for (int i = 2; i * i <= n; i++) {
        if (is_prime[i]) {
            // Mark all multiples of i as false
            for (int j = i * i; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }

    // Output all prime numbers
    cout << "Prime numbers up to " << n << " are:" << endl;
    for (int i = 2; i <= n; i++) {
        if (is_prime[i]) {
            cout << i << " ";
        }
    }
    cout << endl;
}

int main() {
    int n = 50;
    sieve_of_eratosthenes(n);
    return 0;
}
#include <iostream>
using namespace std;

int main(void){

}
struct node {
    node* arr[26] = {nullptr};
    bool flag = false;
    vector<string> below;
    bool contains(char ch) {
        if (arr[ch - 'a']) return true;
        else return false;
    }
    void add(char ch, node* sub) {
        arr[ch - 'a'] = sub;
    }
    node* next(char ch) {
        return arr[ch - 'a'];
    }
    void end() {
        flag = true;
    }
    bool isend() {
        return flag;
    }
    void ins(string bel) {
        below.push_back(bel);
    }
    void put(vector<string>& res) {
        int count = 0;
        for (auto it : below) {
            res.push_back(it);
            if (++count == 3) break;
        }
    }
};

class Trie {
private:
    node* root = new node();
public:
    void insert(string word) {
        node* nod = root;
        for (int i = 0; i < word.length(); ++i) {
            if (!nod->contains(word[i])) {
                nod->add(word[i], new node()); 
            }
            nod = nod->next(word[i]);
            nod->ins(word);
        }
        nod->end();
    }

    vector<vector<string>> search(string word) {
        vector<vector<string>> res;
        node* nod = root;
        for (int i = 0; i < word.length(); ++i) {
            vector<string> ans;
            if (!nod->contains(word[i])) {
                break;
            }
            nod = nod->next(word[i]);
            nod->put(ans);
            res.push_back(ans);
        }
        while (res.size() < word.size()) {
            res.push_back({});
        }
        return res;
    }
};

class Solution {
public:
    vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
        sort(products.begin(), products.end());
        Trie a;
        for (auto it : products) {
            a.insert(it);
        }
        return a.search(searchWord);
    }
};
// Challenge Solution - Part #4
  // Add Challenge Color - Soft-White Triangle
  0x888888,   // soft white triangle
// Challenge Solution - Part #3
  // Add Challenge Element Name
  piece_Tri, 
 
// Challenge Solution - Part #2
// Challenge Element "Triangle"
const char piece_Tri[] = {
  // Rotation 1
  1, 1, 1, 0,
  1, 1, 0, 0,
  1, 0, 0, 0, 
  0, 0, 0, 0,

  // Rotation 2
  1, 1, 1, 0,
  1, 1, 0, 0,
  1, 0, 0, 0, 
  0, 0, 0, 0,

  // Rotation 3
  1, 1, 1, 0,
  1, 1, 0, 0,
  1, 0, 0, 0, 
  0, 0, 0, 0,

  // Rotation 4
  1, 1, 1, 0,
  1, 1, 0, 0,
  1, 0, 0, 0, 
  0, 0, 0, 0,
}; // End Challenge Element
 
#define NUM_ELEMENT_TYPES       8 // Challenge Solution - Part #1 - Add 1 for Number of Element Types
 
// 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);
}
c