//1.判断头尾的MT

//# include <iostream>

//# include <algorithm>

//# include <string> //字符串类

//# include <array> //静态数组

//# include <vector> //动态数组

//# include <deque> //双向动态数组

//# include <list> //双向链表

//# include <forward_list> //单向链表

//# include <utility> //pair

//# include <set> //集合容器

//# include <unordered_set> //无序set

//# include <map> //键值对容器

//# include <unordered_map> //无序map

//# include <stack> //栈

//# include <queue> //队列

//# include <cstdio>

//# include <cstdlib> //定义杂项函数和内存分配函数

//# include <cmath> //定义数学函数

//# include <cstring> //字符串处理

//# include <ctime>

////# include <windows.h>

////# include <graphics.h>

////# include <conio.h>

//

//using namespace std;

//

//typedef long long ll;

//

//int main() {

// //ios::sync_with_stdio(false);

// //freopen("in.txt", "r", stdin);

// int n; cin >> n;

// string s; cin >> s;

// int i = 0;

// while (s[i] != 'M' && i < n)i++;

// while (s[i] != 'T' && i < n)i++;

// int j = n - 1;

// while (s[j] != 'T' && j >= 0)j--;

// while (s[j] != 'M' && j >= 0)j--;

//

// string ans = s.substr(i + 1, j - i-1);

// cout << ans << endl;

//

// return 0;

//}

//2.选择业务地点

//# include <iostream>

//# include <algorithm>

//# include <string> //字符串类

//# include <array> //静态数组

//# include <vector> //动态数组

//# include <deque> //双向动态数组

//# include <list> //双向链表

//# include <forward_list> //单向链表

//# include <utility> //pair

//# include <set> //集合容器

//# include <unordered_set> //无序set

//# include <map> //键值对容器

//# include <unordered_map> //无序map

//# include <stack> //栈

//# include <queue> //队列

//# include <cstdio>

//# include <cstdlib> //定义杂项函数和内存分配函数

//# include <cmath> //定义数学函数

//# include <cstring> //字符串处理

//# include <ctime>

////# include <windows.h>

////# include <graphics.h>

////# include <conio.h>

//

//using namespace std;

//

//typedef long long ll;

//

//int main() {

// //ios::sync_with_stdio(false);

// //freopen("in.txt", "r", stdin);

// int n; cin >> n;

// int s[100010] = { 0 };

// vector<int>ans;

// for (int i = 0; i < n; i++) {

// int j = 0;

// int t;

// for (; j < n; j++) {

// cin >> t;

// if (s[t] == 0) {

// s[t] = 1;

// ans.emplace_back(t);

// break;

// }

// }

// for (j++; j < n; j++) {

// cin >> t;

// }

// }

// for (auto x : ans) {

// cout << x << ' ';

// }

// cout << endl;

//

// return 0;

//}

//3.小美追小团

//# include <iostream>

//# include <algorithm>

//# include <string> //字符串类

//# include <array> //静态数组

//# include <vector> //动态数组

//# include <deque> //双向动态数组

//# include <list> //双向链表

//# include <forward_list> //单向链表

//# include <utility> //pair

//# include <set> //集合容器

//# include <unordered_set> //无序set

//# include <map> //键值对容器

//# include <unordered_map> //无序map

//# include <stack> //栈

//# include <queue> //队列

//# include <cstdio>

//# include <cstdlib> //定义杂项函数和内存分配函数

//# include <cmath> //定义数学函数

//# include <cstring> //字符串处理

//# include <ctime>

////# include <windows.h>

////# include <graphics.h>

////# include <conio.h>

//

//using namespace std;

//

//typedef long long ll;

//

//struct node {

// int downlen = 0;

// int len = 0;

//};

//

//unordered_map<int, vector<int>> mp;

//bool vis[50010];

//node dfs(int i, int uplen, int y) {

// node ans;

// if (vis[i]) return ans;

//

// vis[i] = true;

// for (auto x : mp[i]) {

// node t = dfs(x, uplen + 1, y);

// if (t.len) {

// if (uplen > t.len) {

// if (ans.downlen < t.downlen)

// ans.downlen = t.downlen;

// }

// else {

// ans = t;

// }

// ans.len = t.len;

// }

// else {

// if (ans.downlen < t.downlen && ans.len < uplen)

// ans.downlen = t.downlen;

// }

// }

// if (i == y || ans.len) {

// ans.len++;

// }

// ans.downlen++;

// return ans;

//}

//

//

//int main() {

// //ios::sync_with_stdio(false);

// //freopen("in.txt", "r", stdin);

//

// int n, x, y; cin >> n >> x >> y;

// int u, v;

// for (int i = 0; i < n - 1; i++) {

// cin >> u >> v;

// mp[u].emplace_back(v);

// mp[v].emplace_back(u);

// }

// cout << dfs(x, 0, y).downlen - 1 << endl;

// return 0;

//}

//4.没时间做了

//5.复制粘贴

//# include <iostream>

//# include <algorithm>

//# include <string> //字符串类

//# include <array> //静态数组

//# include <vector> //动态数组

//# include <deque> //双向动态数组

//# include <list> //双向链表

//# include <forward_list> //单向链表

//# include <utility> //pair

//# include <set> //集合容器

//# include <unordered_set> //无序set

//# include <map> //键值对容器

//# include <unordered_map> //无序map

//# include <stack> //栈

//# include <queue> //队列

//# include <cstdio>

//# include <cstdlib> //定义杂项函数和内存分配函数

//# include <cmath> //定义数学函数

//# include <cstring> //字符串处理

//# include <ctime>

////# include <windows.h>

////# include <graphics.h>

////# include <conio.h>

//

//using namespace std;

//

//typedef long long ll;

//

//int main() {

// //ios::sync_with_stdio(false);

// //freopen("in.txt", "r", stdin);

// int n; cin >> n;

// vector<int>s(n);

// vector<int>ans(n, -1);

// for (int i = 0; i < n; i++) {

// cin >> s[i];

// }

// int m; cin >> m;

// while (m--) {

// int q; cin >> q;

// if (q == 1) {

// int k, x, y; cin >> k >> x >> y;

// for (int i = 0; i < k; i++) {

// ans[y - 1 + i] = s[x - 1 + i];

// }

// }

// else if (q == 2) {

// int it; cin >> it;

// cout << ans[it - 1] << endl;

// }

// }

//

// return 0;

//}