#include<bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <random>
#include <chrono>
#include <map>
#include <queue>
#include <stack>
#include <thread>
#include <mutex>
#include <atomic>
#include <functional>
#include <string>
#include <unordered_map>
#include <limits>
#include <iomanip>
#include <fstream>
#include <sstream>
namespace SortAlgorithms {
    void bubbleSort(std::vector<int>& arr) {
        for(size_t i = 0; i < arr.size()-1; ++i) {
            for(size_t j = 0; j < arr.size()-i-1; ++j) {
                if(arr[j] > arr[j+1]) {
                    std::swap(arr[j], arr[j+1]);
                }
            }
        }
    }

    void quickSort(std::vector<int>& arr, int left, int right) {
        if(left >= right) return;
        int pivot = arr[(left+right)/2];
        int i = left, j = right;
        while(i <= j) {
            while(arr[i] < pivot) i++;
            while(arr[j] > pivot) j--;
            if(i <= j) {
                std::swap(arr[i], arr[j]);
                i++; j--;
            }
        }
        quickSort(arr, left, j);
        quickSort(arr, i, right);
    }

    void mergeSort(std::vector<int>& arr, int l, int r) {
        if (l >= r) return;
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        std::vector<int> temp(r - l + 1);
        int i = l, j = m + 1, k = 0;
        while (i <= m && j <= r) {
            if (arr[i] <= arr[j]) temp[k++] = arr[i++];
            else temp[k++] = arr[j++];
        }
        while (i <= m) temp[k++] = arr[i++];
        while (j <= r) temp[k++] = arr[j++];
        for (int p = 0; p < k; ++p) arr[l + p] = temp[p];
    }
}

namespace GraphAlgorithms {
    class Graph {
        std::map<int, std::vector<int>> adjList;
    public:
        void addEdge(int u, int v) {
            adjList[u].push_back(v);
            adjList[v].push_back(u);
        }

        void BFS(int start) {
            std::queue<int> q;
            std::map<int, bool> visited;
            q.push(start);
            visited[start] = true;
            while(!q.empty()) {
                int node = q.front();
                q.pop();
                for(int neighbor : adjList[node]) {
                    if(!visited[neighbor]) {
                        visited[neighbor] = true;
                        q.push(neighbor);
                    }
                }
            }
        }

        void DFS(int start) {
            std::stack<int> s;
            std::map<int, bool> visited;
            s.push(start);
            visited[start] = true;
            while(!s.empty()) {
                int node = s.top();
                s.pop();
                for(int neighbor : adjList[node]) {
                    if(!visited[neighbor]) {
                        visited[neighbor] = true;
                        s.push(neighbor);
                    }
                }
            }
        }
    };
}

namespace MathAlgorithms {
    bool isPrime(int n) {
        if(n <= 1) return false;
        for(int i = 2; i*i <= n; ++i) {
            if(n%i == 0) return false;
        }
        return true;
    }

    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a%b);
    }

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

    double fastPow(double x, int n) {
        double res = 1.0;
        while(n) {
            if(n & 1) res *= x;
            x *= x;
            n >>= 1;
        }
        return res;
    }
}

namespace DPAlgorithms {
    int fibonacci(int n) {
        if(n <= 1) return n;
        std::vector<int> dp(n+1);
        dp[0] = 0; dp[1] = 1;
        for(int i = 2; i <= n; ++i) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }

    int knapsack(const std::vector<int>& weights, const std::vector<int>& values, int capacity) {
        int n = weights.size();
        std::vector<std::vector<int>> dp(n+1, std::vector<int>(capacity+1, 0));
        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= capacity; ++j) {
                if(weights[i-1] <= j) {
                    dp[i][j] = std::max(dp[i-1][j], values[i-1] + dp[i-1][j-weights[i-1]]);
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[n][capacity];
    }
}

namespace StringAlgorithms {
    void KMP(const std::string& text, const std::string& pattern) {
        int n = text.size(), m = pattern.size();
        std::vector<int> lps(m, 0);
        for(int i = 1, len = 0; i < m;) {
            if(pattern[i] == pattern[len]) {
                lps[i++] = ++len;
            } else if(len) {
                len = lps[len-1];
            } else {
                lps[i++] = 0;
            }
        }
        for(int i = 0, j = 0; i < n;) {
            if(pattern[j] == text[i]) { i++; j++; }
            if(j == m) { j = lps[j-1]; }
            else if(i < n && pattern[j] != text[i]) {
                j ? j = lps[j-1] : i++;
            }
        }
    }

    std::string reverseString(std::string s) {
        int left = 0, right = s.size()-1;
        while(left < right) {
            std::swap(s[left++], s[right--]);
        }
        return s;
    }
}

namespace ParallelProcessing {
    std::mutex mtx;
    std::atomic<int> counter(0);

    void threadTask(int id) {
        std::lock_guard<std::mutex> lock(mtx);
        counter++;
    }
}


int main() {
    std::vector<int> data = {5,3,8,1,9,2,7,4,6};
    std::random_device rd;
    std::mt19937 gen(rd());
    
    SortAlgorithms::bubbleSort(data);
    SortAlgorithms::quickSort(data, 0, data.size()-1);
    SortAlgorithms::mergeSort(data, 0, data.size()-1);
    
    GraphAlgorithms::Graph g;
    g.addEdge(0,1); g.addEdge(0,2);
    g.BFS(0);
    g.DFS(0);
    
    MathAlgorithms::isPrime(17);
    MathAlgorithms::gcd(48,18);
    MathAlgorithms::lcm(12,18);
    MathAlgorithms::fastPow(2, 10);
    
    DPAlgorithms::fibonacci(10);
    DPAlgorithms::knapsack({10,20,30}, {60,100,120}, 50);
    
    StringAlgorithms::KMP("ABABDABACDABABCABAB", "ABABCABAB");
    StringAlgorithms::reverseString("algorithm");
    
    std::shuffle(data.begin(), data.end(), gen);
    std::next_permutation(data.begin(), data.end());
    
    std::thread t1(ParallelProcessing::threadTask, 1);
    std::thread t2(ParallelProcessing::threadTask, 2);
    t1.join(); t2.join();
    
    std::cout << "Hello,World" << std::endl;
    return 0;
}