unsigned short int i=(unsigned short int)(-1234);
printf("%hu\n",i);

int minMutation(string startGene, string endGene, vector<string>& bank) {

    if (bank.size() == 0) return -1;

    int total_diff = 0;
    vector<bool> visit(bank.size(), false);

    queue<string> genes;
    genes.push(startGene);

    while (genes.size()) {

        total_diff ++;
        for (int n = genes.size(); n > 0; n --) {

            string gene = genes.front();
            genes.pop();
            for (int i = 0; i < bank.size(); i ++) {

                if (visit[i]) continue;
                int count_diff = 0;
                for (int j = 0; j < gene.size(); j ++) {
                    if (gene[j] != bank[i][j]) count_diff ++;
                }
                if (count_diff == 1) {
                    if (bank[i] == endGene) return total_diff;
                    genes.push(bank[i]);
                    visit[i] = true;
                }
            }
        }
    }

    return -1;
}

int electricCarPlan(vector<vector<int>>& paths, int cnt, int start, int end, vector<int>& charge) {

    int n = charge.size();

    // 记录每条相邻边，以及边的距离
    vector<vector<pair<int, int>>> edges(n);
    for (auto p : paths) {
        edges[p[0]].emplace_back(p[1], p[2]);
        edges[p[1]].emplace_back(p[0], p[2]);
    }

    // 计算以不同油量到达各个端点的最短单位时间
    vector<vector<int>> cost(n, vector<int>(cnt + 1, INT_MAX));
    cost[start][0] = 0;

    // 优先队列按照单位时间排序 (消耗时间, 节点, 油量)
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> q;
    q.emplace(0, start, 0);

    while (q.size()) {

        // 获取当前消耗时间最短的下一条路径
        auto [cost1, n1, o1] = q.top(); q.pop();

        // 若现有消耗时间比已有记录还大，跳过判断
        if (cost1 > cost[n1][o1]) continue;

        // 若已到达终点，则跳出循环
        if (n1 == end) return cost1;

        // 考虑不同的充电状态
        if (o1 < cnt) {
            int new_cost = cost1 + charge[n1];
            if (new_cost < cost[n1][o1 + 1]) {
                cost[n1][o1 + 1]  = new_cost;
                // 为节点新增不同的油量状态
                q.emplace(new_cost, n1, o1 + 1);
            }
        }

        // 遍历当前节点的相邻边
        for (auto [n2, cost2] : edges[n1]) {
            // 若油量不足往下走，则跳过
            if (o1 < cost2) continue;
            int new_cost = cost1 + cost2;
            int new_o = o1 - cost2;
            // 若从当前节点走到n2且油量为new_o，比已有起点到n2且油量
            // 为new_o的时间短，则更新
            if (new_cost < cost[n2][new_o]) {
                cost[n2][new_o] = new_cost;
                // 新增到达n2的时间，并减去消耗的油量
                q.emplace(new_cost, n2, new_o);
            }
        }

    }

    return -1;

}

int numBusesToDestination(vector<vector<int>>& routes, int source, int target) {
    // 若起点和重点一致则无需坐公交
    if (source == target) return 0;
    int n = routes.size();
    unordered_map<int, set<int>> stationRoute; // 记录站点对应的线路
    queue<int> iterRoutes; // 遍历各条路线
    vector<int> dis(n, 10e7); // 记录到达该线路的最短经过线路数
    for (int i = 0; i < n; i ++) {
        auto route = routes[i];
        bool find = false;
        for (auto station : route) {
            // 记录车站对应的线路
            stationRoute[station].insert(i);
            if (station == source) {
                find = true;
            }
        }
        if (find) {
            // 记录起始点所在线路并初始化经过线路数
            iterRoutes.emplace(i);
            dis[i] = 1;
        }
    }
    vector<int> visited(n, false);
    while (iterRoutes.size()) {
        // 取当前的最近线路
        int curRoute = iterRoutes.front(); iterRoutes.pop();
        // 判断是否已计算过该线路
        if (visited[curRoute]) continue;
        visited[curRoute] = true;
        // 遍历线路中的各个站点，寻找可能的下一条线路
        for (auto station : routes[curRoute]) {
            // 若重点就在本线路，则返回线路数
            if (station == target) return dis[curRoute];
            // 遍历站点对应的多条线路
            for (auto route : stationRoute[station]) {
                if (visited[route]) continue;
                // 更新经过线路的最短距离
                if (dis[curRoute] + 1 < dis[route]) {
                    dis[route] = dis[curRoute] + 1;
                    iterRoutes.emplace(route);
                }
            }
        }
    }
    return -1;
}

vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
    vector<double> result;
    map<string, int> nodes;
    for (auto eq : equations) {
        string a = eq[0], b = eq[1];
        if (! nodes.count(a)) {
            nodes[a] = nodes.size();
        }
        if (! nodes.count(b)) {
            nodes[b] = nodes.size();
        }
    }
    int nodeNum = nodes.size();
    vector<vector<double>> connect(nodeNum, vector<double>(nodeNum, -1.0));
    // 构建自身算式连接
    for (int i = 0; i < nodeNum; i ++) {
        connect[i][i] = 1.0;
    }
    // 构建已有算式连接
    for (int i = 0, len = equations.size(); i < len; i ++) {
        auto eq = equations[i];
        double val = values[i];
        string a = eq[0], b = eq[1];
        int ia = nodes[a], ib = nodes[b];
        connect[ia][ib] = val;
        connect[ib][ia] = 1.0 / val;
    }
    // 构建可达连接
    for (int k = 0; k < nodeNum; k ++) {
        for (int i = 0; i < nodeNum; i ++) {
            for (int j = 0; j < nodeNum; j ++) {
                // 已有连接不重复赋值（在此题背景下不同路径结果相同）
                if (connect[i][j] == -1 && connect[i][k] != -1 && connect[k][j] != -1) {
                    connect[i][j] = connect[i][k] * connect[k][j];
                }
            }
        }
    }
    // 值查询
    for (auto query : queries) {
        string a = query[0], b = query[1];
        int ia = nodes.find(a) != nodes.end() ? nodes[a] : -1;
        int ib = nodes.find(b) != nodes.end() ? nodes[b] : -1;
        if (ia != -1 && ib != -1) {
            result.push_back(connect[ia][ib]);
        }
        else {
            result.push_back(-1);
        }
    }
    return result;
}

bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    vector<vector<int>> edges(numCourses);
    vector<int> father(numCourses, 0);
    // 通过二维向量构建有向图
    for (int i = 0, len = prerequisites.size(); i < len; i ++) {
        int a = prerequisites[i][0];
        int b = prerequisites[i][1];
        edges[a].push_back(b);
        father[b] ++;
    }
    // 初始化BFS队列
    queue<int> learn;
    for (int i = 0; i < numCourses; i ++) {
        if (! father[i]) learn.push(i);
    }
    // 计算遍历图的节点访问次数
    int count = 0;
    while (learn.size()) {
        count ++;
        int node = learn.front(); learn.pop();
        for (auto edge : edges[node]) {
            // 保证被访问节点只访问一次
            if (-- father[edge] == 0) {
                learn.push(edge);
            }
        }
    }
    // 判断节点访问次数与节点数是否相同
    return count == numCourses;
}

int lengthOfLIS(vector<int>& nums) {
    auto end = nums.begin();
    for (int x : nums) {
        auto it = lower_bound(nums.begin(), end, x);
        *it = x;
        if (it == end) {
            end ++;
        }
    }
    return end - nums.begin();
}

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

int main()
{
    priority_queue<int,vector<int>,less<int>> p1;     //默认大根堆
    p1.push(2); p1.push(1); p1.push(3);               //输出 3 2 1
    while(p1.empty()== false){
        cout<<p1.top()<<" ";
        p1.pop();
    }

    priority_queue<int,vector<int>,greater<int>> p2;  //小根堆
    p2.push(2); p2.push(1); p2.push(3);               //输出 1 2 3
    while(p2.empty()== false){
        cout<<p2.top()<<" ";
        p2.pop();
    }

    // 基本数据类型-pair-pair类型默认先比较第一个元素，第一个相等比较第二个
    priority_queue<pair<int, int> > a;
    a.push(pair<int,int>{1,2});
    a.push(pair<int,int>{1,3});
    a.push(pair<int,int>{2,5});
    while (a.empty()== false){
        cout<<a.top().first<<" "<< a.top().second<<endl;
        a.pop();
    }
    //输出:
    //2 5
    //1 3
    //1 2

    return 0;
}

int nthUglyNumber(int n) {
    long times_num[] = {2, 3, 5};
    set<long> record;
    priority_queue<long, vector<long>, greater<long>> q;
    q.push(1);
    int index = 1;
    while (index <= n) {
        int cur_num = q.top();
        if (index == n) return cur_num;
        q.pop();
        for (long t : times_num) {
            long new_num = cur_num * t;
            if (record.contains(new_num)) continue;
            q.push(new_num);
            record.insert(new_num);
        }
        index ++;
    }
    return 0;
}

vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {

    vector<vector<int>> result;
    int l1 = nums1.size(), l2 = nums2.size();

    auto cmp = [&](const auto& a, const auto& b) {
        return nums1[a.first] + nums2[a.second] > nums1[b.first] + nums2[b.second];
    };
    priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> q(cmp);
    for (int i = 0; i < l1; i ++) {
        q.push({i, 0});
    }

    while (result.size() < k) {
        auto [ia, ib] = q.top();
        result.push_back({nums1[ia], nums2[ib]});
        q.pop();
        if (ib + 1 < l2) q.push(pair<int, int>{ia, ib + 1});
    }

    return result;
}

int lengthOfLastWord(string s) {
    stringstream ss(s);
    string word;
    while (ss >> word) ;
    return word.size();
}

int strStr(string haystack, string needle) {
    // next数组表示到该位置的字串的最大相同前后缀的长度
    vector<int> next(needle.size());
    int j = 0;
    next[0] = 0;
    for (int i = 1, len = needle.size(); i < len; i ++) {
        // 末尾不相同则查找以当前前缀的最大重复长度
        while (j && needle[i] != needle[j]) j = next[j - 1];
        // 末尾相同则记录长度
        if (needle[i] == needle[j]) j ++;
        next[i] = j;
    }
    // 通过回溯重合位置减少遍历次数
    for (int i = 0, j = 0, len = haystack.size(); i < len; i ++) {
        // 若当前位置不匹配则变换比对位置
        while (j && haystack[i] != needle[j]) j = next[j - 1];
        // 若比对成功则向后比对
        if (haystack[i] == needle[j]) j ++;
        // 判断是否已完成比对
        if (j == needle.size()) return i - needle.size() + 1;
    }
    return -1;
}

class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        vector<string> ans;
        // Lambda 函数构建字符串
        auto f = [&](int i, int j) {
            return i == j ? to_string(nums[i]) : to_string(nums[i]) + "->" + to_string(nums[j]);
        };
        // i 在迭代时为上一个区间结尾 + 1
        for (int i = 0, j, n = nums.size(); i < n; i = j + 1) {
            j = i;
            // 若差为 1，右端点移动
            while (j + 1 < n && nums[j + 1] == nums[j] + 1) {
                ++ j;
            }
            // 添加区间
            ans.emplace_back(f(i, j));
        }
        return ans;
    }
};

class Solution {
private:
    // 使用长度为26的数组存储下一个字符
    struct Node {
        vector<Node*> next;
    };
public:
    int minimumLengthEncoding(vector<string>& words) {
        int n = words.size();
        // 初始化根节点
        Node* root = new Node();
        root->next.resize(26, nullptr);
        Node* p = nullptr;
        // 按字符串长度排序
        sort(words.begin(), words.end(), [&](const string& a, const string& b) {
            return a.size() > b.size();
        });
        int count = 0;
        // 遍历各个字符串
        for (int i = 0; i < n; i ++) {
            bool include = true;
            string& w = words[i];
            p = root;
            // 从字符串尾部开始遍历
            for (int j = w.size() - 1; j >= 0; j --) {
                int charIndex = w[j] - 'a';
                // 若为非空指针则表示已有该字符序列
                if (p->next[charIndex]) {
                    p = p->next[charIndex];
                }
                // 创建新的字符
                else {
                    include = false; // 标识为新字符串
                    Node* newNode = new Node();
                    newNode->next.resize(26, nullptr);
                    p->next[charIndex] = newNode;
                    p = newNode;
                }
            }
            // 若为新字符串则加上当前字符串长度以及"#"的长度
            if (! include) count += w.size() + 1;
        }
        return count;
    }
};

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int size = nums.size();
        int left = 0;
        int right = 0;
        int sum = nums[0];
        int minLen = size + 1;
        while (left < size && right < size) {
            if (sum >= target) {
                minLen = min(minLen, right - left + 1);
                sum -= nums[left];
                left ++;
                continue;
            }
            if (right == size - 1) break;
            right ++;
            sum += nums[right];
        }
        if (minLen == size + 1) return 0;
        return minLen;
    }

};