liverpool.cpp

//
// Created by wangzhiheng on 26/09/2025.
//
#include "liverpool.h"

#include "templates.h"
#include <algorithm>
#include <climits>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <ostream>
#include <queue>
#include <ranges>
#include <sstream>
#include <stack>
#include <vector>

using namespace std;

namespace liverpool {
	namespace stable_matching {
		vector<int> Solution::match(vector<vector<int>> s2c, vector<vector<int>> c2s) {
			int N     = s2c.size();
			students  = vector<Student *>();
			companies = vector<Company *>();
			for(int i = 0; i < N; i++) {
				Student *stu    = new Student(i);
				stu->c_priority = unordered_map<Company *, int>();
				stu->priority_c = unordered_map<int, Company *>();
				students.emplace_back(stu);
				Company *com  = new Company(i);
				com->priority = unordered_map<Student *, int>();
				companies.emplace_back(com);
			}
			for(int i = 0; i < N; i++) {
				for(int j = 0; j < N; j++) {
					students[i]->c_priority[companies[j]] = s2c[i][j];
					students[i]->priority_c[s2c[i][j]]    = companies[j];
					companies[i]->priority[students[j]]   = c2s[i][j];
				}
			}
			bool flag = true;
			while(flag) {
				flag = false;
				for(int i = 0; i < N; i++) {
					auto stu = students[i];
					if(stu->matched_company == nullptr) {
						flag = true;
						stu->priority_c[stu->current_priority++]->proposed_students.insert(stu);
					}
				}

				for(int i = 0; i < N; i++) {
					auto com                         = companies[i];
					Student *current_matched_student = com->matched_student;
					if(com->proposed_students.size() > 0) {
						int min_priority       = com->matched_student ? com->priority[com->matched_student] : INT_MAX;
						Student *max_p_student = com->matched_student;
						for(auto stu: com->proposed_students) {
							if(com->priority[stu] < min_priority) {
								min_priority  = com->priority[stu];
								max_p_student = stu;
								flag          = true;
							}
						}
						if(flag) {
							if(current_matched_student != nullptr) {
								current_matched_student->matched_company = nullptr;
							}
							com->matched_student           = max_p_student;
							max_p_student->matched_company = com;
						}
						com->proposed_students.clear();
					}
				}
			}
			vector<int> ans = vector<int>(N, -1);
			for(int i = 0; i < N; i++) {
				ans[i] = students[i]->matched_company->id;
			}
			return ans;
		}
	}// namespace stable_matching

	namespace oddecho {
		int main(istream &cin, ostream &cout) {
			string str;
			int cnt = 0;
			while(cin >> str) {
				if(cnt % 2 == 1) {
					cout << str << endl;
				}
				cnt++;
			}
			return 0;
		}
	}// namespace oddecho

	namespace recount {
		int main(istream &cin, ostream &cout) {
			unordered_map<string, unsigned long> m = unordered_map<string, unsigned long>();
			string line;
			while(std::getline(cin, line)) {
				if(line == "***") {
					break;
				}
				m[line]++;
			}

			string ans             = "***";
			unsigned long max_vote = 0;
			for(const auto &[k, v]: m) {
				max_vote = max(max_vote, v);
			}
			for(const auto &[k, v]: m) {
				if(v == max_vote) {
					if(ans != "***") {
						cout << "Runoff!";
						return 0;
					}
					ans = k;
				}
			}
			cout << ans;

			return 0;
		}
	}// namespace recount

	namespace set {
		vector<vector<int>> ans = {};
		cardset::cardset(card *c) {
			this->cards.insert(c);
			this->cnt = 1;
		}

		unsigned short calc_mask(card *c1, card *c2) {
			unsigned short mask = 0;
			for(int i = 0; i < 4; i++) {
				mask <<= 1;
				mask |= c1->f[i] == c2->f[i];
			}
			return mask;
		}
		card::card(int id, string s) {
			this->id = id;
			istringstream iss(s);
			iss >> this->f[0] >> this->f[1] >> this->f[2] >> this->f[3];
		}

		void cardset::insert(card *c) {
			if(this->mask == (unsigned short) (-1)) {
				this->mask = calc_mask(c, *this->cards.begin());
			}
			this->cards.insert(c);
			this->cnt++;
			if(this->cnt == 3) {
				vector<int> vec = {};
				for(auto &c: this->cards) {
					vec.emplace_back(c->id);
				}
				std::sort(vec.begin(), vec.end());
				ans.emplace_back(vec);
			}
		}

		bool fit(card *c, const cardset *s) {
			if(s->mask == (unsigned short) (-1)) {
				return true;
			}
			for(auto &sc: s->cards) {
				if(calc_mask(sc, c) != s->mask) {
					return false;
				}
			}
			return true;
		}

		int main(istream &cin, ostream &cout) {
			cardset sets[1 << 10] = {};
			int sets_cnt          = 0;
			string input;
			for(int i = 1; i <= 12; i++) {
				cin >> input;
				card *newcard = new card(i, input);
				for(int j = 0; j < sets_cnt; j++) {
					if(fit(newcard, &sets[j])) {
						cardset newset = sets[j];
						newset.insert(newcard);
						sets[sets_cnt++] = (newset);
					}
				}
				cardset newset   = cardset(newcard);
				sets[sets_cnt++] = (newset);
			}
			if(ans.size() == 0) {
				cout << "no sets";
				return 0;
			}
			std::sort(ans.begin(), ans.end(), [](const vector<int> &a, const vector<int> &b) {
				if(a[0] != b[0]) {
					return a[0] < b[0];
				} else if(a[1] != b[1]) {
					return a[1] < b[1];
				} else {
					return a[2] < b[2];
				}
			});
			for(const auto &s: ans) {
				cout << s[0] << ' ' << s[1] << ' ' << s[2] << endl;
			}
			return 0;
		}
	}// namespace set

	namespace plantingtrees {
		int main(istream &cin, ostream &cout) {
			int n;
			cin >> n;
			vector<int> vec(n);
			for(int i = 0; i < n; i++) {
				cin >> vec[i];
			}
			sort(vec.rbegin(), vec.rend());
			int ans = 0;
			for(int i = 0; i < n; i++) {
				ans = max(ans, i + vec[i] + 2);
			}
			cout << ans;

			return 0;
		}
	}// namespace plantingtrees

	namespace snowflakes {
		int main(istream &cin, ostream &cout) {
			int testCases;
			cin >> testCases;
			while(testCases--) {
				int n;
				cin >> n;
				if(n == 0) {
					cout << 0 << endl;
					break;
				}
				vector<int> snowflakes(n);
				for(int i = 0; i < n; ++i) {
					cin >> snowflakes[i];
				}
				unordered_map<int, int> lastSeen;
				int left      = 0;
				int maxLength = 0;
				for(int right = 0; right < n; ++right) {
					int currentSnowflake = snowflakes[right];
					if(lastSeen.count(currentSnowflake)) {
						left = max(left, lastSeen[currentSnowflake] + 1);
					}
					lastSeen[currentSnowflake] = right;
					maxLength                  = max(maxLength, right - left + 1);
				}
				cout << maxLength;
			}

			return 0;
		}
	}// namespace snowflakes

	namespace amalgram {
		int main(istream &cin, ostream &cout) {
			string a, b;
			cin >> a >> b;
			vector<int> cnt1 = vector<int>(26, 0);
			vector<int> cnt2 = vector<int>(26, 0);
			for(char c: a) {
				cnt1[c - 'a']++;
			}
			for(char c: b) {
				cnt2[c - 'a']++;
			}
			for(int i = 0; i < 26; i++) {
				for(int j = 0; j < max(cnt1[i], cnt2[i]); j++) {
					cout << (char) ('a' + i);
				}
			}
			return 0;
		}
	}// namespace amalgram

	namespace wheresmyinternet {
		int main(istream &cin, ostream &cout) {
			int N, M;
			int a, b;
			cin >> N >> M;
			UnionFind uf = UnionFind(N + 1);
			while(M--) {
				cin >> a >> b;
				uf.unite(a, b);
			}
			bool flag = false;
			for(int i = 2; i <= N; i++) {
				if(!uf.same(i, 1)) {
					cout << i << endl;
					flag = true;
				}
			}
			if(!flag) {
				cout << "Connected";
			}
			return 0;
		}
	}// namespace wheresmyinternet

	namespace oddities {
		int main(istream &cin, ostream &cout) {
			int n;
			cin >> n;
			while(n--) {
				int x;
				cin >> x;
				cout << x << " is " << ((abs(x) % 2 == 1) ? "odd" : "even") << endl;
			}
			return 0;
		}
	}// namespace oddities

	namespace countingchocolate {
		bool solve(const vector<int> &a, int john, int sam, int sp, int target) {
			if(sp == a.size()) {
				return false;
			}
			if(john == target || sam == target) {
				return true;
			}
			if(john > target || sam > target) {
				return false;
			}
			return solve(a, john + a[sp], sam, sp + 1, target) || solve(a, john, sam + a[sp], sp + 1, target);
		}

		int main(istream &cin, ostream &cout) {
			int n;
			cin >> n;
			vector<int> a = vector<int>(n);
			int sum       = 0;
			for(int i = 0; i < n; i++) {
				cin >> a[i];
				sum += a[i];
			}
			if(sum % 2 == 1) {
				cout << "NO";
				return 0;
			}
			if(solve(a, 0, 0, 0, sum / 2)) {
				cout << "YES";
			} else {
				cout << "NO";
			}
			return 0;
		}
	}// namespace countingchocolate

	namespace grid {

		int n, m;
		struct pair_hash {
			size_t operator()(const pair<int, int> &p) const {
				return hash<int>()(p.first) ^ (hash<int>()(p.second) << 1);
			}
		};
		struct pair_equal {
			bool operator()(const pair<int, int> &a, const pair<int, int> &b) const {
				return a.first == b.first && a.second == b.second;
			}
		};
		int main(istream &cin, ostream &cout) {
			cin >> n >> m;
			vector<vector<int>> grid(n, vector<int>(m));
			for(int i = 0; i < n; i++) {
				string line;
				cin >> line;
				istringstream iss(line);
				for(int j = 0; j < m; j++) {
					char c;
					iss >> c;
					grid[i][j] = c - '0';
				}
			}
			unordered_set<pair<int, int>, pair_hash, pair_equal> visited{};
			auto comp = [](const state &a, const state &b) {
				if(a.step != b.step) {
					return a.step > b.step;
				}
				int dist_a = (n - a.x - 1) + (m - a.y - 1);
				int dist_b = (n - b.x - 1) + (m - b.y - 1);
				return dist_a > dist_b;
			};
			priority_queue<state, vector<state>, decltype(comp)> pq{};
			pq.push(state{0, 0, 0});
			while(!pq.empty()) {
				auto top = pq.top();
				pq.pop();
				int x = top.x;
				int y = top.y;
				if(visited.count({x, y})) {
					continue;
				}
				visited.insert(make_pair(x, y));
				if(x == n - 1 && y == m - 1) {
					cout << top.step;
					return 0;
				}
				int step               = grid[x][y];
				pair<int, int> next[4] = {
				        make_pair(x + step, y),
				        make_pair(x - step, y),
				        make_pair(x, y + step),
				        make_pair(x, y - step)};
				for(auto [next_x, next_y]: next) {
					if(next_x == n - 1 && next_y == m - 1) {
						cout << top.step + 1;
						return 0;
					}
					if(next_x >= 0 && next_x < n && next_y >= 0 && next_y < m && grid[next_x][next_y] != 0) {
						pq.push(state{next_x, next_y, top.step + 1});
					}
				}
			}
			cout << -1;
			return 0;
		}
	}// namespace grid

	namespace allpairspath {

		int main(istream &cin, ostream &cout) {
			int n, m, q;
			while(cin >> n >> m >> q) {
				if(n == 0 && m == 0 && q == 0) {
					return 0;
				}

				vector<vector<int>> dist = vector(n, vector<int>(n, INT_MAX / 2));
				vector<edge> edges       = vector<edge>(m);
				for(int i = 0; i < n; i++) {
					dist[i][i] = 0;
				}
				unordered_set<int> calced{};

				for(int i = 0; i < m; i++) {
					int u, v, w;
					cin >> u >> v >> w;
					edges[i] = edge{u, v, w};
				}

				while(q--) {
					int u, v;
					cin >> u >> v;
					if(calced.contains(u)) {
						if(dist[u][v] >= INT_MAX / 2) {
							cout << "Impossible" << endl;
						} else {
							cout << dist[u][v] << endl;
						}
						continue;
					}

					for(int i = 0; i < n; i++) {
						for(int j = 0; j < m; j++) {
							int from = edges[j].u;
							int to   = edges[j].v;
							int w    = edges[j].w;
							if(dist[u][to] > dist[u][from] + w) {
								dist[u][to] = dist[u][from] + w;
							}
						}
					}
					if(dist[u][v] >= INT_MAX / 2) {
						cout << "Impossible" << endl;
					} else {
						cout << dist[u][v] << endl;
					}

					calced.insert(u);
				}

				cout << endl;
			}
			return 0;
		}
	}// namespace allpairspath

	namespace weakvertices {
		int main(istream &cin, ostream &cout) {
			int n;
			while(cin >> n) {
				if(n == -1)
					return 0;
				vector<vector<int>> siblings = vector(n, vector<int>());
				vector<vector<bool>> graph   = vector(n, vector<bool>(n, false));
				for(int i = 0; i < n; i++) {
					for(int j = 0; j < n; j++) {
						int x;
						cin >> x;
						if(x == 1) {
							siblings[i].push_back(j);
							//siblings[j].push_back(j);
							graph[i][j] = true;
							graph[j][i] = true;
						}
					}
				}
				for(int i = 0; i < n; i++) {
					bool flag = true;
					for(int j = 0; j < siblings[i].size(); j++) {
						for(int k = j + 1; k < siblings[i].size(); k++) {
							if(graph[siblings[i][j]][siblings[i][k]]) {
								flag = false;
								break;
							}
						}
						if(!flag) {
							break;
						}
					}
					if(flag) {
						cout << i << ' ';
					}
				}
				cout << endl;
			}

			return 0;
		}
	}// namespace weakvertices

	namespace clockpictures {
		struct subarr {
			int num;
			int cnt;
		};
		int main(istream &cin, ostream &cout) {
			int n;
			cin >> n;
			vector<int> a1(n);
			vector<int> a2(n);
			vector<int> space1(n);
			vector<int> space2(n);
			for(int i = 0; i < n; i++) {
				cin >> a1[i];
			}
			for(int i = 0; i < n; i++) {
				cin >> a2[i];
			}
			sort(a1.begin(), a1.end());
			sort(a2.begin(), a2.end());
			for(int i = 0; i < n; i++) {
				space1[i] = ((i + 1 < n) ? a1[i + 1] : (a1[0] + 360000)) - a1[i];
				space2[i] = ((i + 1 < n) ? a2[i + 1] : (a2[0] + 360000)) - a2[i];
			}
			int start_1 = 0;
			for(start_1 = 1; start_1 < n && space1[start_1] == space1[0]; start_1++)
				;
			start_1 %= n;
			int start_2 = 0;
			for(start_2 = 1; start_2 < n && space2[start_2] == space2[0]; start_2++)
				;
			start_2 %= n;
			vector<subarr> subarrs_1 = {};
			vector<subarr> subarrs_2 = {};
			int prev                 = space1[start_1];
			int cnt                  = 0;
			for(int i = 0; i < n; i++) {
				if(space1[(start_1 + i) % n] != prev) {
					subarrs_1.push_back(subarr{prev, cnt});
					prev = space1[(start_1 + i) % n];
					cnt  = 1;
				} else {
					cnt++;
				}
			}
			subarrs_1.push_back(subarr{prev, cnt});


			prev = space2[start_2];
			cnt  = 0;
			for(int i = 0; i < n; i++) {
				if(space2[(start_2 + i) % n] != prev) {
					subarrs_2.push_back(subarr{prev, cnt});
					prev = space2[(start_2 + i) % n];
					cnt  = 1;
				} else {
					cnt++;
				}
			}
			subarrs_2.push_back(subarr{prev, cnt});

			ostringstream oss1;
			ostringstream oss2;
			for(int i = 0; i < subarrs_1.size(); i++) {
				oss1 << subarrs_1[i].num << '*' << subarrs_1[i].cnt << ' ';
			}
			for(int i = 0; i < subarrs_1.size(); i++) {
				oss1 << subarrs_1[i].num << '*' << subarrs_1[i].cnt << ' ';
			}
			for(int i = 0; i < subarrs_2.size(); i++) {
				oss2 << subarrs_2[i].num << '*' << subarrs_2[i].cnt << ' ';
			}
			string str1 = oss1.str();
			string str2 = oss2.str();
			if(str1.find(str2) != std::string::npos) {
				cout << "possible";
			} else {
				cout << "impossible";
			}
			return 0;
		}
	}// namespace clockpictures

	namespace ceremony {
		int main(istream &cin, ostream &cout) {
			int n;
			cin >> n;
			deque<int> floors;
			for(int i = 0; i < n; i++) {
				int h;
				cin >> h;
				floors.push_back(h);
			}
			sort(floors.begin(), floors.end());
			int ans        = 0;
			int demolished = 0;
			while(!floors.empty()) {
				ans++;
				if(floors.size() > floors.back() - demolished) {
					demolished++;
					while(!floors.empty() && floors.front() - demolished == 0) {
						floors.pop_front();
					}
				} else {
					floors.pop_back();
				}
			}
			cout << ans;
			return 0;
		}
	}// namespace ceremony

	namespace doctorkattis {
		constexpr int N = 1000010;
		cat heap[N];
		int heap_size                        = 0;
		int time_counter                     = 0;
		unordered_map<string, int> cat_index = {};

		bool cat::operator<(const cat &c2) const {
			if(this->infection_level != c2.infection_level) {
				return this->infection_level > c2.infection_level;
			}
			return this->order < c2.order;
		}

		int bubble_up(int index) {
			while(((index - 1) / 2) >= 0 && heap[index] < heap[(index - 1) / 2]) {
				swap(heap[index], heap[(index - 1) / 2]);
				cat_index[heap[index].name] = index;
				index                       = (index - 1) / 2;
				cat_index[heap[index].name] = index;
			}
			return index;
		}

		int bubble_down(int index) {
			while(2 * index + 1 < heap_size) {
				int l        = 2 * index + 1;// Left child index
				int r        = 2 * index + 2;// Right child index
				int smallest = index;
				if(l < heap_size && heap[l] < heap[smallest]) {
					smallest = l;
				}
				if(r < heap_size && heap[r] < heap[smallest]) {
					smallest = r;
				}
				if(smallest == index) {
					break;
				}
				swap(heap[index], heap[smallest]);
				cat_index[heap[index].name]    = index;
				cat_index[heap[smallest].name] = smallest;
				index                          = smallest;
			}
			return index;
		}

		void arrive_at_clinic(string cat_name, int infection_level) {
			cat c               = cat{cat_name, time_counter++, infection_level};
			heap[heap_size]     = c;
			cat_index[cat_name] = heap_size;
			bubble_up(heap_size++);
		}

		void update_infection_level(string cat_name, int increase_infection) {
			int index                   = cat_index[cat_name];
			heap[index].infection_level = min(100, heap[index].infection_level + increase_infection);
			bubble_up(index);
		}

		void treat(string cat_name) {
			int index = cat_index[cat_name];
			int last  = heap_size - 1;
			swap(heap[index], heap[last]);
			cat_index[heap[index].name] = index;
			heap_size--;
			index = bubble_up(index);
			bubble_down(index);
		}

		string query() {
			if(heap_size > 0) {
				return heap[0].name;
			} else {
				return "The clinic is empty";
			}
		}
		int main(istream &cin, ostream &cout) {
			int n;
			cin >> n;
			while(n--) {
				int cmd;
				cin >> cmd;
				switch(cmd) {
					case 0: {
						string name;
						int infection_level;
						cin >> name >> infection_level;
						arrive_at_clinic(name, infection_level);
						break;
					}
					case 1: {
						string name;
						int increase_infection;
						cin >> name >> increase_infection;
						update_infection_level(name, increase_infection);
						break;
					}
					case 2: {
						string name;
						cin >> name;
						treat(name);
						break;
					}
					case 3: {
						cout << query() << endl;
						break;
					}
				}
			}
			return 0;
		}
	}// namespace doctorkattis


	namespace lobby {
		int main_1(istream &cin, ostream &cout) {
			string line;
			int ans = 0;
			while(cin >> line) {
				vector<int> rMax      = vector<int>(line.size(), 0);
				rMax[line.size() - 1] = line.back() - '0';
				int lineMax           = 0;
				for(int i = line.length() - 2; i >= 0; i--) {
					rMax[i] = max(line[i] - '0', rMax[i + 1]);
					lineMax = max(lineMax, 10 * (line[i] - '0') + rMax[i + 1]);
				}
				ans += lineMax;
			}
			cout << ans;
			return 0;
		}

		int main_2(istream &cin, ostream &cout) {
			string line;
			unsigned long long ans = 0;
			while(cin >> line) {
				vector<vector<unsigned long long>> rMax = vector<vector<unsigned long long>>(13, vector<unsigned long long>(line.size(), 0));
				rMax[1][line.size() - 1]                = line.back() - '0';
				unsigned long long level                = 1;
				for(int i = 1; i <= 12; i++, level *= 10) {
					for(int j = line.length() - i; j >= 0; j--) {
						rMax[i][j] = max((line[j] - '0') * level + (i - 1 > 0 ? rMax[i - 1][j + 1] : 0), j + 1 < line.length() ? rMax[i][j + 1] : 0);
					}
				}
				unsigned long long lineMax = 0;
				for(int i = 0; i < line.length(); i++) {
					lineMax = max(lineMax, rMax[12][i]);
				}
				ans += lineMax;
			}
			cout << ans;
			return 0;
		}
	}// namespace lobby

	namespace printing_department {
		int main_1(istream &cin, ostream &cout) {
			vector<string> input = {};
			string line;
			while(cin >> line) {
				input.push_back(line);
			}
			int w                   = line.length();
			int h                   = input.size();
			vector<vector<int>> cnt = vector<vector<int>>(h + 2, vector<int>(w + 2, 0));
			for(int i = 1; i <= h; i++) {
				for(int j = 1; j <= w; j++) {
					if(input[i - 1][j - 1] == '@') {
						cnt[i - 1][j]++;
						cnt[i + 1][j]++;
						cnt[i][j - 1]++;
						cnt[i][j + 1]++;
						cnt[i - 1][j - 1]++;
						cnt[i - 1][j + 1]++;
						cnt[i + 1][j + 1]++;
						cnt[i + 1][j - 1]++;
					}
				}
			}
			int ans = 0;
			for(int i = 1; i <= h; i++) {
				for(int j = 1; j <= w; j++) {
					if(cnt[i][j] < 4 && input[i - 1][j - 1] == '@') {
						ans++;
					}
				}
			}
			cout << ans;
			return 0;
		}

		void remove(vector<vector<int>> &cnt, const vector<string> &input, int x, int y, int w, int h, int &ans) {
			ans++;
			cnt[x][y]                    = -1;
			pair<int, int> directions[8] = {
			        {-1, 0},
			        {1, 0},
			        {0, -1},
			        {0, 1},
			        {-1, -1},
			        {-1, 1},
			        {1, 1},
			        {1, -1}};
			for(auto [dx, dy]: directions) {
				int nx = x + dx;
				int ny = y + dy;
				if(cnt[nx][ny] != -1 && nx >= 1 && nx <= h && ny >= 1 && ny <= w) {
					cnt[nx][ny]--;
					if(cnt[nx][ny] < 4 && input[nx - 1][ny - 1] == '@') {
						remove(cnt, input, nx, ny, w, h, ans);
					}
				}
			}
		}

		int main_2(istream &cin, ostream &cout) {
			vector<string> input = {};
			string line;
			while(cin >> line) {
				input.push_back(line);
			}
			int w                   = line.length();
			int h                   = input.size();
			vector<vector<int>> cnt = vector<vector<int>>(h + 2, vector<int>(w + 2, 0));
			for(int i = 1; i <= h; i++) {
				for(int j = 1; j <= w; j++) {
					if(input[i - 1][j - 1] == '@') {
						cnt[i - 1][j]++;
						cnt[i + 1][j]++;
						cnt[i][j - 1]++;
						cnt[i][j + 1]++;
						cnt[i - 1][j - 1]++;
						cnt[i - 1][j + 1]++;
						cnt[i + 1][j + 1]++;
						cnt[i + 1][j - 1]++;
					}
				}
			}

			int ans = 0;
			for(int i = 1; i <= h; i++) {
				for(int j = 1; j <= w; j++) {
					if(cnt[i][j] < 4 && cnt[i][j] != -1 && input[i - 1][j - 1] == '@') {
						remove(cnt, input, i, j, w, h, ans);
					}
				}
			}
			cout << ans;
			return 0;
		}
	}// namespace printing_department

	namespace secret_entrance {
		int main_1(istream &cin, ostream &cout) {
			int dial = 50;
			int ans  = 0;
			string cmd;
			while(cin >> cmd) {
				istringstream iss(cmd);
				char c;
				int step;
				iss >> c >> step;
				if(c == 'R') {
					dial += step;
				} else {
					dial += 100 - step;
				}
				dial %= 100;
				if(dial == 0) {
					ans++;
				}
			}
			cout << ans;
			return 0;
		}

		int main_2(istream &cin, ostream &cout) {
			int dial = 50;
			int ans  = 0;
			string cmd;
			while(cin >> cmd) {
				istringstream iss(cmd);
				char c;
				int step;
				iss >> c >> step;

				ans += step / 100;
				step %= 100;
				for(int i = 0; i < step; i++) {
					if(c == 'R') {
						dial++;
					} else {
						dial--;
					}
					dial += 100;
					dial %= 100;
					if(dial == 0) {
						ans++;
					}
				}
			}
			cout << ans;
			return 0;
		}
	}// namespace secret_entrance

	namespace cafeteria {
		struct node {
			bool start            = true;
			bool check            = false;
			unsigned long long id = 0;
		};

		int main_1(istream &cin, ostream &cout) {
			string line;
			vector<node> ranges = {};
			bool part_1         = true;
			while(cin >> line) {
				if(line.empty() || line.find('-') == string::npos) {
					part_1 = false;
				}
				istringstream iss(line);
				unsigned long long id;
				if(part_1) {
					char c;
					iss >> id >> c;
					ranges.push_back(node{true, false, id});
					iss >> id;
					ranges.push_back(node{false, false, id + 1});
				} else {
					iss >> id;
					ranges.push_back(node{false, true, id});
				}
			}

			sort(ranges.begin(), ranges.end(), [](const node &a, const node &b) {
				if(a.id != b.id) {
					return a.id < b.id;
				}
				if(a.start != b.start) {
					return a.start > b.start;
				}
				return a.check < b.check;
			});

			unsigned long long cnt = 0;
			unsigned long long ans = 0;
			for(const auto &node: ranges) {
				if(node.start) {
					cnt++;
				} else if(node.check) {
					if(cnt > 0) {
						ans++;
					}
				} else {
					cnt--;
				}
			}
			cout << ans;
			return 0;
		}

		int main_2(istream &cin, ostream &cout) {
			string line;
			vector<node> ranges = {};
			while(cin >> line) {
				istringstream iss(line);
				unsigned long long id;
				char c;
				iss >> id >> c;
				ranges.push_back(node{true, false, id});
				iss >> id;
				ranges.push_back(node{false, false, id + 1});
			}

			sort(ranges.begin(), ranges.end(), [](const node &a, const node &b) {
				if(a.id != b.id) {
					return a.id < b.id;
				}
				if(a.start != b.start) {
					return a.start > b.start;
				}
				return a.check < b.check;
			});

			unsigned long long cnt     = 0;
			unsigned long long prev_id = -1;
			unsigned long long ans     = 0;
			for(const auto &node: ranges) {
				if(node.start) {
					cnt++;
				} else {
					cnt--;
				}

				if(prev_id == -1 && cnt > 0) {
					prev_id = node.id;
				} else if(cnt == 0 && prev_id != -1) {
					ans += node.id - prev_id;
					//cerr << node.id << '\t' << prev_id << '\t' << (node.id - prev_id) << '\t' << ans << endl;
					prev_id = -1;
				}
			}
			cout << ans;
			return 0;
		}
	}// namespace cafeteria

	namespace gift_shop {
		bool test(unsigned long long num) {
			ostringstream oss = {};
			oss << num;
			string str = oss.str();
			if(str.length() % 2 == 1) {
				return false;
			}
			return str.substr(0, str.length() / 2) == str.substr(str.length() / 2);
		}

		int main_1(istream &cin, ostream &cout) {
			unsigned long long a, b;
			char c;
			unsigned long long ans = 0;
			while(cin >> a >> c >> b) {
				for(unsigned long long i = a; i <= b; i++) {
					if(test(i)) {
						ans += i;
					}
				}
				if(!(cin >> c)) {
					break;
				}
			}
			cout << ans;
			return 0;
		}

		bool test2(string num, int repeat) {
			if(num.length() % repeat != 0) {
				return false;
			}
			string example = num.substr(0, num.length() / repeat);
			for(int i = 1; i < repeat; i++) {
				if(num.substr(i * (num.length() / repeat), num.length() / repeat) != example) {
					return false;
				}
			}
			return true;
		}

		int main_2(istream &cin, ostream &cout) {
			unsigned long long a, b;
			char c;
			unsigned long long ans = 0;
			while(cin >> a >> c >> b) {
				for(unsigned long long i = a; i <= b; i++) {
					string num;
					ostringstream oss = {};
					oss << i;
					num = oss.str();
					for(int j = 2; j <= 100; j++) {
						if(test2(num, j)) {
							ans += i;
							break;
						}
					}
				}
				if(!(cin >> c)) {
					break;
				}
			}
			cout << ans;
			return 0;
		}
	}// namespace gift_shop

	namespace trash_compactor {
		int main_1(istream &cin, ostream &cout, int n, int nl) {
			vector<vector<unsigned long long>> input = vector<vector<unsigned long long>>(nl, vector<unsigned long long>(n, 0));
			for(int i = 0; i < nl; i++) {
				for(int j = 0; j < n; j++) {
					cin >> input[i][j];
				}
			}
			char c;
			unsigned long long ans = 0;
			for(int i = 0; i < n; i++) {
				cin >> c;
				if(c == '+') {
					for(int j = 0; j < nl; j++) {
						ans += input[j][i];
					}
				} else {// *
					unsigned long long tmp = 1;
					for(int j = 0; j < nl; j++) {
						tmp *= input[j][i];
					}
					ans += tmp;
				}
			}
			cout << ans;
			return 0;
		}
		int main_2(istream &cin, ostream &cout) {
			vector<string> grid = vector<string>();
			string line;
			while(getline(cin, line)) {
				grid.emplace_back(line);
			}
			int h                         = grid.size();
			int w                         = grid[0].length();
			unsigned long long ans        = 0;
			stack<unsigned long long> stk = {};
			for(int i = w - 1; i >= 0; i--) {
				unsigned long long current = 0;
				bool push                  = false;
				for(int j = 0; j < h; j++) {
					char c = grid[j][i];
					if(isdigit(c)) {
						push = true;
						current *= 10;
						current += (c - '0');
					} else if(c == '+') {
						stk.push(current);
						push = false;
						while(!stk.empty()) {
							ans += stk.top();
							stk.pop();
						}
					} else if(c == '*') {
						stk.push(current);
						push                   = false;
						unsigned long long tmp = 1;
						while(!stk.empty()) {
							tmp *= stk.top();
							stk.pop();
						}
						ans += tmp;
					}
				}
				if(push)
					stk.push(current);
			}
			cout << ans;
			return 0;
		}
	}// namespace trash_compactor

	namespace movie_theater {
		int main_1(istream &cin, ostream &cout) {
			vector<pair<unsigned long long, unsigned long long>> vert = {};
			unsigned long long x, y;
			char c;
			unsigned long long ans = 0;
			while(cin >> x >> c >> y) {
				auto p = make_pair(x, y);

				for(const auto &[nx, ny]: vert) {
					unsigned long long x_min = min(nx, x);
					unsigned long long x_max = max(nx, x);
					unsigned long long y_min = min(ny, y);
					unsigned long long y_max = max(ny, y);

					ans = max(ans, (x_max + 1 - x_min) * (y_max + 1 - y_min));
				}

				vert.push_back(p);
			}
			cout << ans;
			return 0;
		}

		int main_2(istream &cin, ostream &cout) {
			vector<pair<unsigned long long, unsigned long long>> vert = {};
			unsigned long long x, y;
			char c;
			unsigned long long ans = 0;

			unordered_set<unsigned long long> xs = {};
			unordered_set<unsigned long long> ys = {};

			while(cin >> x >> c >> y) {
				xs.insert(x);
				ys.insert(y);
				auto p = make_pair(x, y);
				vert.push_back(p);
			}
			vector<unsigned long long> x_vect(xs.begin(), xs.end());
			vector<unsigned long long> y_vect(ys.begin(), ys.end());
			ranges::sort(x_vect);
			ranges::sort(y_vect);
			unordered_map<unsigned long long, unsigned long long> x_i = {};
			unordered_map<unsigned long long, unsigned long long> y_i = {};
			for(int i = 0; i < x_vect.size(); i++) {
				x_i[x_vect[i]] = i + 1;
			}
			for(int i = 0; i < y_vect.size(); i++) {
				y_i[y_vect[i]] = i + 1;
			}
			for(auto &[xx, yy]: vert) {
				xx = x_i[xx];
				yy = y_i[yy];
			}

			unsigned long long w     = x_vect.size() + 2;
			unsigned long long h     = y_vect.size() + 2;
			vector<vector<int>> grid = vector<vector<int>>(w, vector<int>(h, 2));
			for(int i = 0; i < vert.size(); i++) {
				auto p1               = vert[i];
				auto p2               = vert[(i + 1) % vert.size()];
				unsigned long long x0 = min(p1.first, p2.first);
				unsigned long long x1 = max(p1.first, p2.first);
				unsigned long long y0 = min(p1.second, p2.second);
				unsigned long long y1 = max(p1.second, p2.second);
				for(int j = x0; j <= x1; j++) {
					for(int k = y0; k <= y1; k++) {
						grid[j][k] = 1;
					}
				}
			}

			queue<pair<unsigned long long, unsigned long long>> q = {};
			q.push({0, 0});
			while(!q.empty()) {
				auto front = q.front();
				q.pop();
				pair<unsigned long long, unsigned long long> directions[4] = {
				        {1, 0},
				        {-1, 0},
				        {0, 1},
				        {0, -1}};
				for(auto [dx, dy]: directions) {
					unsigned long long nx = front.first + dx;
					unsigned long long ny = front.second + dy;
					if(nx < w && ny < h && grid[nx][ny] == 2) {
						grid[nx][ny] = 0;
						q.push({nx, ny});
					}
				}
			}

			for(int i = 0; i < vert.size(); i++) {
				for(int j = i + 1; j < vert.size(); j++) {
					unsigned long long x1 = min(vert[i].first, vert[j].first);
					unsigned long long x2 = max(vert[i].first, vert[j].first);
					unsigned long long y1 = min(vert[i].second, vert[j].second);
					unsigned long long y2 = max(vert[i].second, vert[j].second);
					bool valid            = true;
					for(int xx = x1; xx <= x2; xx++) {
						if(grid[xx][y1] == 0) {
							valid = false;
							goto END;
						}
						if(grid[xx][y2] == 0) {
							valid = false;
							goto END;
						}
					}
					for(int yy = y1; yy <= y2; yy++) {
						if(grid[x1][yy] == 0) {
							valid = false;
							goto END;
						}
						if(grid[x2][yy] == 0) {
							valid = false;
							goto END;
						}
					}
				END:
					if(valid) {
						ans = max(ans, (x_vect[x2 - 1] + 1 - x_vect[x1 - 1]) * (y_vect[y2 - 1] + 1 - y_vect[y1 - 1]));
					}
				}
			}
			cout << ans;
			return 0;
		}
	}// namespace movie_theater

	namespace factory {
		int main_1(istream &cin, ostream &cout) {
			unsigned long long ans = 0;
			string line;
			while(getline(cin, line)) {
				unsigned long long destination = 0;
				vector<unsigned long long> ops = {};
				auto substrs                   = std::views::split(line, ' ');
				for(const auto &[a, b]: substrs) {
					string substr = string(a, b);
					istringstream iss;
					if(substr[0] == '[') {// destination
						substr = string(a + 1, b - 1);
						for(int i = 0; i < substr.length(); i++) {
							if(substr[i] == '#') {
								destination |= (1ULL << i);
							}
						}
					} else if(substr[0] == '(') {// operator
						unsigned long long op = 0;
						substr                = string(a + 1, b - 1);
						auto subsubstrs       = std::views::split(substr, ',');
						for(const auto &[c, d]: subsubstrs) {
							string subsubstr = string(c, d);
							iss              = istringstream(subsubstr);
							int index;
							iss >> index;
							op |= (1ULL << index);
						}
						ops.push_back(op);
					} else {// ?
						substr = string(a + 1, b - 1);
					}
				}
				unordered_set<unsigned long long> vis                 = {};
				queue<pair<unsigned long long, unsigned long long>> q = {};
				for(int i = 0; i < ops.size(); i++) {
					q.push({0 ^ ops[i], 1ULL << i});
					vis.insert(1ULL << i);
				}
				while(!q.empty()) {
					auto [current, tag] = q.front();
					q.pop();
					if(current == destination) {
						//cout << std::popcount(tag) << endl;
						ans += std::popcount(tag);
						break;
					}
					for(int i = 0; i < ops.size(); i++) {
						unsigned long long next_tag = tag | (1ULL << i);
						if(!vis.contains(next_tag)) {
							unsigned long long next_current = current ^ ops[i];
							vis.insert(next_tag);
							q.push({next_current, next_tag});
						}
					}
				}
			}
			cout << ans;
			return 0;
		}
	}// namespace factory

	namespace reactor {
		struct node {
			string name;
			vector<string> next;
			int v = 0;
		};

		int main_1(istream &cin, ostream &cout) {
			string tag;
			string in;
			unordered_map<string, node> nodes = {};
			while(cin >> tag) {
				if(tag.ends_with(':')) {
					in = tag.substr(0, tag.length() - 1);
					if(!nodes.contains(in)) {
						nodes.insert({in, node{in, {}}});
					}
				} else {
					if(!nodes.contains(tag)) {
						nodes.insert({tag, node{tag, {}}});
					}
					nodes[tag].next.push_back(in);
				}
			}
			stack<string> stk = {};
			stk.push("out");
			while(!stk.empty()) {
				string current = stk.top();
				stk.pop();
				nodes[current].v++;
				for(const auto &next: nodes[current].next) {
					if(nodes[next].v < 1 << 12)
						stk.push(next);
				}
			}
			cout << nodes["you"].v;
			return 0;
		}
	}// namespace reactor

	namespace hsbc_interview {
		string solution(string letters) {
			int lower_id[26] = {};
			int upper_id[26] = {};
			bool output[26]  = {};
			for(int i = 0; i < 26; i++) {
				lower_id[i] = -1;
				upper_id[i] = -1;
				output[i]   = false;
			}
			int cnt = 0;
			for(int i = 0; i < letters.length(); i++) {
				char c = letters[i];
				if(islower(c) && lower_id[c - 'a'] == -1) {
					lower_id[c - 'a'] = i;
				} else if(isupper(c)) {
					upper_id[c - 'A'] = i;
				}
			}
			for(int i = 0; i < 26; i++) {
				if(lower_id[i] != -1 && upper_id[i] != -1 && lower_id[i] > upper_id[i]) {
					cnt++;
					output[i] = true;
				}
			}
			ostringstream oss = {};
			oss << cnt;
			if(cnt > 0) {
				oss << " ";
				for(int i = 0; i < 26; i++) {
					if(output[i]) {
						oss << (char) (i + 'A') << ' ' << (char) (i + 'a') << ' ';
					}
				}
			}
			return oss.str();
		}
	}// namespace hsbc_interview

	namespace booking {
		int getScoreDifference(vector<int> numSeq) {
			int p1      = 0;
			int p2      = 0;
			int l       = 0;
			int r       = numSeq.size() - 1;
			int *cursor = &l;
			bool p1turn = true;
			while(l <= r) {
				int score = numSeq[*cursor];
				if(p1turn) {
					p1 += score;
				} else {
					p2 += score;
				}
				if(cursor == &l) {
					(*cursor)++;
				} else {
					(*cursor)--;
				}
				if(score % 2 == 0) {
					cursor = (cursor == &l) ? &r : &l;
				}
				p1turn = !p1turn;
			}
			return p1 - p2;
		}

		int getSwapTime(string color) {
			int ans    = 0;
			int l0_cnt = 0;
			for(char c: color) {
				if(c == '0') {
					l0_cnt++;
				} else if(l0_cnt != 0) {
					ans = max(ans + 1, l0_cnt);
				}
			}
			return ans;
		}
	}// namespace booking

	namespace aboveaverage {
		int main(istream &cin, ostream &cout) {
			int C;
			cin >> C;
			while(C--) {
				int N;
				cin >> N;
				int sum = 0;
				vector<int> vec(N);
				for(int i = 0; i < N; i++) {
					cin >> vec[i];
					sum += vec[i];
				}
				int cnt = 0;
				for(int i = 0; i < N; i++) {
					if(vec[i] * N > sum) {
						cnt++;
					}
				}
				cout << setiosflags(ios::fixed) << setprecision(3) << (cnt * 100.0f) / N << '%' << endl;
			}
			return 0;
		}
	}// namespace aboveaverage

	namespace bestrelayteam {
		int main(istream &cin, ostream &cout) {
			int n;
			cin >> n;
			unordered_map<string, player *> m = {};
			vector<player *> a_list           = {};
			vector<player *> b_list           = {};
			unordered_set<player *> b_set     = {};
			while(n--) {
				string name;
				float a, b;
				cin >> name >> a >> b;
				player *pl = new player{name, a, b};
				m[name]    = pl;
				a_list.push_back(pl);
				b_list.push_back(pl);
			}
			ranges::sort(a_list, [](const player *a, const player *b) {
				if(a->a != b->a)
					return a->a < b->a;
				return a->b > b->b;
			});
			ranges::sort(b_list, [](const player *a, const player *b) {
				if(a->b != b->b) {
					return a->b < b->b;
				}
				return a->a > b->a;
			});
			b_set.insert(b_list[0]);
			b_set.insert(b_list[1]);
			b_set.insert(b_list[2]);
			float best = 999999999;
			string best_ans;
			for(int i = 0; i < a_list.size(); i++) {
				float current = a_list[i]->a;
				current += b_list[0] == a_list[i] ? 0 : b_list[0]->b;
				current += b_list[1] == a_list[i] ? 0 : b_list[1]->b;
				current += b_list[2] == a_list[i] ? 0 : b_list[2]->b;
				if(b_set.contains(a_list[i])) {
					current += b_list[3]->b;
				}
				if(current < best) {
					best              = current;
					ostringstream oss = {};
					oss << current << endl
					    << a_list[i]->name << endl;
					if(b_list[0] != a_list[i]) {
						oss << b_list[0]->name << endl;
					}
					if(b_list[1] != a_list[i]) {
						oss << b_list[1]->name << endl;
					}
					if(b_list[2] != a_list[i]) {
						oss << b_list[2]->name << endl;
					}
					if(b_set.contains(a_list[i])) {
						oss << b_list[3]->name << endl;
					}
					best_ans = oss.str();
				}
			}
			cout << best_ans;
			return 0;
		}
	}// namespace bestrelayteam

	namespace guessthedatastructure {
		int main(istream &cin, ostream &cout) {
			int n;
			while(cin >> n) {
				stack<int> stk         = {};
				queue<int> q           = {};
				priority_queue<int> pq = {};
				bool is_stk            = true;
				bool is_q              = true;
				bool is_pq             = true;
				while(n--) {
					int c, x;
					cin >> c >> x;
					if(c == 1) {
						stk.push(x);
						q.push(x);
						pq.push(x);
					} else {
						if(stk.empty()) {
							is_stk = false;
							is_q   = false;
							is_pq  = false;
							continue;
						}

						int v = stk.top();
						stk.pop();
						if(v != x) {
							is_stk = false;
						}

						v = q.front();
						q.pop();
						if(v != x) {
							is_q = false;
						}

						v = pq.top();
						pq.pop();
						if(v != x) {
							is_pq = false;
						}
					}
				}
				int cnt = (is_stk ? 1 : 0) + (is_q ? 1 : 0) + (is_pq ? 1 : 0);
				if(cnt > 1) {
					cout << "not sure" << endl;
				} else if(is_stk) {
					cout << "stack" << endl;
				} else if(is_q) {
					cout << "queue" << endl;
				} else if(is_pq) {
					cout << "priority queue" << endl;
				} else {
					cout << "impossible" << endl;
				}
			}
			return 0;
		}
	}// namespace guessthedatastructure

	namespace torn2pieces {
		bool dfs(unordered_map<string, unordered_set<string>> &m, unordered_set<string> &vis, const string &current, stack<string> &ans, const string &dst) {
			vis.insert(current);
			if(current == dst) {
				ans.push(current);
				return true;
			}
			for(string next: m[current]) {
				if(!vis.contains(next)) {
					if(dfs(m, vis, next, ans, dst)) {
						ans.push(current);
						return true;
					}
				}
			}
			return false;
		}

		int main(istream &cin, ostream &cout) {
			int N;
			cin >> N;
			unordered_map<string, unordered_set<string>> m = {};
			while(N--) {
				string line;
				getline(cin, line);
				if(line.empty()) {
					getline(cin, line);
				}
				istringstream iss(line);
				string src;
				iss >> src;
				if(!m.contains(src))
					m[src] = unordered_set<string>();
				string next;
				while(iss >> next) {
					m[src].insert(next);
					if(!m.contains(next)) {
						m[next] = unordered_set<string>();
					}
					m[next].insert(src);
				}
			}
			string src, dst;
			cin >> src >> dst;
			unordered_set<string> vis = {};
			stack<string> ans         = {};
			if(dfs(m, vis, src, ans, dst)) {
				while(!ans.empty()) {
					cout << ans.top() << ' ';
					ans.pop();
				}
			} else {
				cout << "no route found";
			}
			return 0;
		}
	}// namespace torn2pieces
}// namespace liverpool