#include<iostream>
#include<cstdio>
#include<map>
#include<algorithm>
#include<string>
#include<set>
#include<string.h>
#include<queue>
using namespace std;
struct node
{
int l, r;
char val;
};
node tree[10010];
int idx;
map<char, int> ha;
string a, b;
int build(int pl, int pr, int il, int ir)
{
int t = ++idx;
if (pl > pr)
{
tree[t].val = '0';
return 0;
}
int cur = ha[a[pl]];
int l = build(pl + 1, pl + cur - il, il, cur - 1);
int r = build(pl + cur - il + 1, pr, cur + 1, pr);

tree[t].l = l;
tree[t].r = r;
tree[t].val = a[pl];
return t;

}
void dfs(int root)
{
queue<int > q;
q.push(root);
while (q.size())
{
int top = q.front();
q.pop();
cout << tree[top].val;
if (tree[top].l)
q.push(tree[top].l);
if (tree[top].r)
q.push(tree[top].r);
}
}
int main()
{
int T;
cin >> T;
while (T--)
{
cin >> a >> b;
ha.clear();
idx = 0;
for (int i = 0; i < b.size(); i++) ha[b[i]] = i;
int root = build(0, a.size() - 1, 0, b.size() - 1);
dfs(root);
cout << endl;
}
return 0;
}



//递归建立二叉树的函数

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 1010, M = 3e4 + 10, INF = 0x3f3f3f3f;
int h[N], q[N], dist[N], ne[M], w[M], e[M], idx = 1;
int n, m, s;
bool visit[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}

int spfa()
{
memset(dist, 0x3f, sizeof(dist));
dist[0] = 0;
visit[0] = true;
int hh = 0, tt = 1;
q[0] = 0;
while(hh != tt)
{
int t = q[hh ++];
if(hh == N) hh = 0;
visit[t] = false;
for(int i = h[t]; i; i = ne[i])
{
int j = e[i];
if(dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
if(!visit[j])
{
q[tt ++] = j;
if(tt == N) tt = 0;
visit[j] = true;
}
}
}
}
if(dist[s] == INF) return -1;
else return dist[s];
}
int main()
{
while(scanf("%d%d%d", &n, &m, &s) != -1)
{
memset(h, 0, sizeof(h));
idx = 1;
while(m --)
{
int p, q, t;
scanf("%d%d%d", &p, &q, &t);
}
int w;
scanf("%d", &w);
while(w --)
{
int t;
scanf("%d", &t);
}

printf("%d\n", spfa());
}
return 0;
}




#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e6 + 10;

int tr[N][26], f[N], idx;

int ne[N], q[N];
int id[210];
char str[N];
void insert(int x)
{
int p = 0;
for(int i = 0; str[i]; i ++)
{
int t = str[i] - 'a';
if(!tr[p][t]) tr[p][t] = ++idx;
p = tr[p][t];
f[p]++;
}
id[x] = p;
}
void build()
{
int hh = 0, tt = -1;
for(int i = 0; i < 26; i ++)
if(tr[0][i])
q[++ tt] = tr[0][i];
while(hh <= tt)
{
int t = q[hh ++];
for(int i = 0; i < 26; i ++)
{
int c = tr[t][i];
if(!c) tr[t][i] = tr[ne[t]][i];
else
{
ne[c] = tr[ne[t]][i];
q[++ tt] = c;
}
}
}
}
int main()
{
int n;
cin >> n;
for(int i = 0; i < n; i ++)
{
cin >> str;
insert(i);
}

build();

for(int i = idx - 1; i >= 0; i --) f[ne[q[i]]] += f[q[i]];
for(int i = 0; i < n; i ++)
{
cout << f[id[i]] << endl;
}
return 0;
}




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

const int N = 1e4 + 10, S = 55, M = 1e6 + 10;
char str[M];
int tr[N * S][26], ne[N * S], cnt[N], q[N * S], idx;

void insert()
{
int p = 0;
for(int i = 0; str[i]; i ++)
{
int t = str[i] - 'a';
if(tr[p][t] == 0) tr[p][t] = ++idx;
p = tr[p][t];
}
cnt[p] ++;
}
void build()
{
int hh = 0, tt = -1;
for(int i = 0; i < 26; i ++)
if(tr[0][i])
q[++ tt] = tr[0][i];
while(hh <= tt)
{
int t = q[hh++];
for(int i = 0; i < 26; i ++)
{
int c = tr[t][i];
if(!c) continue;
int j = ne[t];
while(j && !tr[j][i]) j = ne[j];
if(tr[j][i]) j = tr[j][i];
ne[c] = j;
q[++ tt] = c;
}
}
}
int main()
{
int T;
cin >> T;
while(T --)
{
memset(tr, 0, sizeof tr);
memset(ne, 0, sizeof ne);
memset(str, 0, sizeof str);
int n;
cin >> n;
for(int i = 0; i < n; i ++)
{
cin >> str;
insert();
}
build();
int res = 0;
cin >> str;
for(int i = 0, j = 0; str[i]; i ++)
{
int t = str[i] - 'a';
while(j && !tr[j][t]) j = ne[j];
if(tr[j][t]) j = tr[j][t];

int p = j;
while(p)
{
res += cnt[p];
cnt[p] = 0;
p = ne[p];
}
}
cout << res << endl;
}
}




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

const int N = 6e5 + 10, INF = 1e7;
using ll = long long;
struct node
{
int l, r;
int key, val;
}tr[N];
int idx, root;
int get_node(int key)
{
tr[++ idx].key = key;
tr[idx].val = rand();
return idx;
}
void build()
{
get_node(-INF), get_node(INF);
root = 1;
tr[root].r = 2;
}
void zig(int &p)
{
int q = tr[p].l;
tr[p].l = tr[q].r, tr[q].r = p, p = q;
}
void zag(int &p)
{
int q = tr[p].r;
tr[p].r = tr[q].l, tr[q].l = p, p = q;
}
void insert(int &p, int key)
{
if(!p) p = get_node(key);
else if(tr[p].key == key) return;
else if(tr[p].key < key)
{

insert(tr[p].r, key);
if(tr[tr[p].r].val > tr[p].val) zag(p);
}
else if(tr[p].key > key)
{
insert(tr[p].l, key);
if(tr[tr[p].l].val > tr[p].val) zig(p);
}
}
int get_prev(int p, int key)
{
if(!p) return -INF;
if(tr[p].key > key) return get_prev(tr[p].l, key);
else return max(tr[p].key, get_prev(tr[p].r, key));

}
int get_next(int p, int key)
{
if(!p) return INF;
if(tr[p].key < key) return get_next(tr[p].r, key);
else return min(tr[p].key, get_next(tr[p].l, key));
}
int main()
{
int n;
cin >> n;
ll res = 0;
for(int i = 1; i <= n; i ++)
{
int x;
cin >> x;
if(i == 1) res += x;
else res += min(x - get_prev(root, x), get_next(root, x) - x);
insert(root, x);
}
cout << res << endl;
return 0;
}



#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e5 + 10, INF = 1e8;

struct node
{
int l, r;
int key, val;
int cnt, size;
}tr[N];

int n, root, idx;;
void pushup(int &p)
{
tr[p].size = tr[tr[p].l].size + tr[tr[p].r].size + tr[p].cnt;
}
int get_node(int key)
{
int p = ++ idx;
tr[p] = {0, 0, key, rand(), 1, 1};
return p;
}
void build()
{
get_node(-INF), get_node(INF);
root = 1;
tr[root].r = 2;
pushup(root);
}
void zig(int &p)
{
int q = tr[p].l;
tr[p].l = tr[q].r, tr[q].r = p, p = q;
pushup(tr[p].r), pushup(p);
}
void zag(int &p)
{
int q = tr[p].r;
tr[p].r = tr[q].l, tr[q].l = p, p = q;
pushup(tr[p].l), pushup(p);
}
void insert(int &p, int key)
{
if(!p) p = get_node(key);
else if(tr[p].key == key) tr[p].cnt ++;
else if(tr[p].key > key)
{
insert(tr[p].l, key);
if(tr[tr[p].l].val > tr[p].val) zig(p);
}
else if(tr[p].key < key)
{
insert(tr[p].r, key);
if(tr[tr[p].r].val > tr[p].val) zag(p);
}
pushup(p);
}
void remove(int &p, int key)
{
if(!p) return;
if(tr[p].key == key)
{
if(tr[p].cnt > 1) tr[p].cnt --;
else if(tr[p].l || tr[p].r)
{
if(!tr[p].r || tr[tr[p].l].val > tr[tr[p].r].val)
{
zig(p);
remove(tr[p].r, key);
}
else
{
zag(p);
remove(tr[p].l, key);
}
}
else p = 0;
}
else if(tr[p].key > key) remove(tr[p].l, key);
else remove(tr[p].r, key);
pushup(p);
}
int get_rank_by_key(int p, int key)
{
if(!p) return 0;
if(tr[p].key == key) return tr[tr[p].l].size + 1;
else if(tr[p].key > key) return  get_rank_by_key(tr[p].l, key);
else return tr[tr[p].l].size + tr[p].cnt + get_rank_by_key(tr[p].r, key);
}
int get_key_by_rank(int p, int rank)
{
if(!p) return INF;
if(tr[tr[p].l].size >= rank) return get_key_by_rank(tr[p].l, rank);
else if(tr[tr[p].l].size + tr[p].cnt >= rank) return tr[p].key;
else return get_key_by_rank(tr[p].r, rank - tr[tr[p].l].size - tr[p].cnt);

}

int get_prev(int p, int key)
{
if(!p) return -INF;
if(tr[p].key >= key) return get_prev(tr[p].l, key);
else return max(tr[p].key, get_prev(tr[p].r, key));

}
int get_next(int p, int key)
{
if(!p) return INF;
if(tr[p].key <= key) return get_next(tr[p].r, key);
else return min(tr[p].key, get_next(tr[p].l, key));
}
int main()
{
cin >> n;
build();
while(n --)
{
int opt, x;
cin >> opt >> x;
if(opt == 1) insert(root, x);
else if(opt == 2) remove(root, x);
else if(opt == 3) cout << get_rank_by_key(root, x) - 1 << endl;
else if(opt == 4) cout << get_key_by_rank(root, x + 1) << endl;
else if(opt == 5) cout << get_prev(root, x) << endl;
else cout << get_next(root, x) << endl;
}
return 0;
}




#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
const int N = 1e5 + 10, M = 1e4 + 10;

int a[N];
int n, m;
vector<int> nums;
int root[N], idx;
struct node
{
int l, r, cnt;
}tr[N * 21];
int find(int x)
{
return lower_bound(nums.begin(), nums.end(), x) - nums.begin();
}
int build(int l, int r)
{
int p = ++idx;
if(l == r)
{
return p;
}
int mid = l + r >> 1;
tr[p].l = build(l, mid), tr[p].r = build(mid + 1, r);
return p;
}
int insert(int p, int l, int r, int x)
{
int q = ++ idx;
tr[q] = tr[p];
if(l == r)
{
tr[q].cnt ++;
return q;
}
int mid = l + r >> 1;
if(x <= mid) tr[q].l = insert(tr[p].l, l, mid, x);
else tr[q].r = insert(tr[p].r, mid + 1, r, x);
tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;
return q;
}
int query(int p, int q, int l, int r, int k)
{
if(l == r) return r;
int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt;
int mid = l + r >> 1;
if(cnt >= k) return query(tr[p].l, tr[q].l, l, mid, k);
else return query(tr[p].r, tr[q].r, mid + 1, r, k - cnt);
}

int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++)
{
cin >> a[i];
nums.push_back(a[i]);
}
sort(nums.begin(), nums.end());
nums.erase(unique(nums.begin(), nums.end()), nums.end());
root[0] = build(0, nums.size() - 1);

for(int i = 1; i <= n; i ++)
{
root[i] = insert(root[i - 1], 0, nums.size() - 1, find(a[i]));
}
while(m --)
{
int l, r, k;
cin >> l >> r >> k;
cout << nums[query(root[l - 1], root[r], 0, nums.size() - 1, k)] << endl;
}
return 0;
}




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

const int N = 6e5 + 10, M = N * 25;
int tr[M][2], max_id[M], root[N], idx;
int s[N];
void insert(int i, int k, int p, int q)
{
if(k < 0)
{
max_id[q] = i;
return;
}
int v = s[i] >> k & 1;
if(p) tr[q][v ^ 1] = tr[p][v ^ 1];
tr[q][v] = ++ idx;
insert(i, k - 1, tr[p][v], tr[q][v]);
max_id[q] = max(max_id[tr[q][0]], max_id[tr[q][1]]);
}

int query(int root, int C, int L)
{
int p = root;
for(int i = 23; i >= 0; i --)
{
int v = C >> i & 1;
if(max_id[tr[p][v ^ 1]] >= L) p = tr[p][v ^ 1];
else p = tr[p][v];
}
return s[max_id[p]] ^ C;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
root[0] = ++ idx;
max_id[0] = -1;
insert(0, 23, 0, root[0]);

for(int i = 1; i <= n; i ++)
{
int x;
cin >> x;
s[i] = s[i - 1] ^ x;
root[i] = ++ idx;
insert(i, 23, root[i - 1], root[i]);

}
while(m --)
{
string op;
cin >> op;
if(op == "A")
{
int x; cin >> x;
n ++;
s[n] = s[n - 1] ^ x;
root[n] = ++ idx;
insert(n, 23, root[n - 1], root[n]);
}
else
{
int l, r, x;
cin >> l >> r >> x;
//cout << query(root[r - 1], s[n] ^ x, l - 1) << endl;
printf("%d\n", query(root[r - 1], s[n] ^ x, l - 1));
}
}
return 0;
}




#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;

typedef long long ll;
int a[N];    int n, m, p;
struct node
{
int l, r;
}tr[N * 4];

void pushup(int u)
{
tr[u].sum = (ll) ( tr[u << 1].sum + tr[u << 1 | 1].sum ) % p;
}
void eval(node &root, int mul, int add)
{
root.sum = ((ll) root.sum * mul + (ll) (root.r - root.l + 1) * add) % p;
root.mul = (ll) root.mul * mul  % p;
}
void pushdown(int u)
{
eval(tr[u << 1 | 1], tr[u].mul, tr[u].add);

tr[u].add = 0, tr[u].mul = 1;
}
int query(int u, int l, int r)
{
if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum % p;
else
{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
int sum = 0;
if(l <= mid) sum = query(u << 1, l, r) % p;
if(r > mid) sum = (ll) (sum + query(u << 1 | 1, l, r)) % p;
return sum;
}
}
void build(int u, int l, int r)
{
if(l == r) tr[u] = {l, r, a[l], 1, 0};
else
{
tr[u] = {l, r, 0, 1, 0};
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}

void modify(int u, int l, int r, int add, int mul)
{
if(tr[u].l >= l && tr[u].r <= r)
{
}
else
{
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(l <= mid) modify(u << 1, l, r, add, mul);
if(r > mid) modify(u << 1 | 1, l, r, add, mul);
pushup(u);
}
}

int main()
{
cin >> n >> p;
for(int i = 1; i <= n; i ++) cin >> a[i];
build(1, 1, n);
cin >> m;
while(m --)
{
int op, l, r;
cin >> op >> l >> r;
if(op == 1)
{
int e; cin >> e;
modify(1, l, r, 0, e);
}
else if(op == 2)
{
int e;
cin >> e;
modify(1, l, r, e, 1);
}
else
{
cout << query(1, l, r) << endl;
}
}
return 0;
}



// Forward declaration of compare API.
// bool compare(int a, int b);
// return bool means whether a is less than b.

class Solution {
public:
vector<int> specialSort(int N) {
vector<int> res(1, 1);
for(int i = 2; i <= N; i ++)
{
int l = 0, r = res.size() - 1;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(compare(res[mid], i)) l = mid;
else r = mid - 1;
}
res.push_back(i);
for(int j = res.size() - 2; j > r; j --) swap(res[j], res[j + 1]);
if(compare(i, res[r])) swap(res[r], res[r + 1]);
}
return res;
}
};