#include <bits/stdc++.h>
using namespace std;
long long MOD = 1e9 + 7;
const long long MAXN = 1e7;
bool prime[MAXN + 5];
long long tot_primes_till[MAXN + 5];
struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
};
void sieve() {
  int n = MAXN;
  fill(begin(prime), end(prime), true);
  prime[0] = prime[1] = false;
  for (long long i = 2; i <= n; i++) {
    tot_primes_till[i] = tot_primes_till[i - 1];
    if (!prime[i]) continue;
    tot_primes_till[i]++;
    for (long long j = 2 * i; j <= n; j += i) {
      prime[j] = false;
    }
  }
}
long long power(long long a, long long b, long long mod) {
  if (b == 0) {
    return 1;
  }
  long long answer = power(a, b / 2, mod);
  answer *= answer;
  answer %= mod;
  if (b % 2) {
    answer *= a;
  }
  return answer % mod;
}
long long modmul(long long a, long long b, long long mod) {
  long long res = 0;
  a %= mod;
  while (b) {
    if (b & 1) res = (res + a) % mod;
    a = (2 * a) % mod;
    b >>= 1;
  }
  return res;
}
long long gcd(long long int a, long long int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long lcm(int a, int b) { return (a / gcd(a, b)) * b; }
void solve() {
  long long q;
  cin >> q;
  map<long long, long long> m;
  vector<long long> v;
  vector<vector<long long>> s;
  while (q--) {
    long long f;
    cin >> f;
    if (f == 1) {
      long long x;
      cin >> x;
      s.push_back({x});
    } else {
      long long x, y;
      cin >> x >> y;
      s.push_back({x, y});
    }
  }
  for (long long i = s.size() - 1; i >= 0; i--) {
    if (s[i].size() == 1) {
      if (m.find(s[i][0]) == m.end()) {
        v.push_back(s[i][0]);
      } else {
        v.push_back(m[s[i][0]]);
      }
    } else {
      if (m.find(s[i][1]) == m.end()) {
        m[s[i][0]] = s[i][1];
      } else {
        m[s[i][0]] = m[s[i][1]];
      }
    }
  }
  reverse(v.begin(), v.end());
  for (long long i = 0; i < v.size(); i++) {
    cout << v[i] << " ";
  }
  cout << "\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  long long t;
  t = 1;
  while (t--) {
    solve();
  }
}

### Prompt

Create a solution in cpp for the following problem:

You have an array of integers (initially empty).

You have to perform q queries. Each query is of one of two types: 

  * "1 x" — add the element x to the end of the array; 
  * "2 x y" — replace all occurrences of x in the array with y. 



Find the resulting array after performing all the queries.

Input

The first line contains a single integer q (1 ≤ q ≤ 5 ⋅ 10^5) — the number of queries.

Next q lines contain queries (one per line). Each query is of one of two types: 

  * "1 x" (1 ≤ x ≤ 5 ⋅ 10^5); 
  * "2 x y" (1 ≤ x, y ≤ 5 ⋅ 10^5). 



It's guaranteed that there is at least one query of the first type.

Output

In a single line, print k integers — the resulting array after performing all the queries, where k is the number of queries of the first type.

Examples

Input


7
1 3
1 1
2 1 2
1 2
1 1
1 2
2 1 3


Output


3 2 2 3 2 

Input


4
1 1
1 2
1 1
2 2 2


Output


1 2 1 

Input


8
2 1 4
1 1
1 4
1 2
2 2 4
2 4 3
1 2
2 2 7


Output


1 3 3 7 

Note

In the first example, the array changes as follows:

[] → [3] → [3, 1] → [3, 2] → [3, 2, 2] → [3, 2, 2, 1] → [3, 2, 2, 1, 2] → [3, 2, 2, 3, 2].

In the second example, the array changes as follows:

[] → [1] → [1, 2] → [1, 2, 1] → [1, 2, 1].

In the third example, the array changes as follows:

[] → [] → [1] → [1, 4] → [1, 4, 2] → [1, 4, 4] → [1, 3, 3] → [1, 3, 3, 2] → [1, 3, 3, 7].

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
long long MOD = 1e9 + 7;
const long long MAXN = 1e7;
bool prime[MAXN + 5];
long long tot_primes_till[MAXN + 5];
struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
};
void sieve() {
  int n = MAXN;
  fill(begin(prime), end(prime), true);
  prime[0] = prime[1] = false;
  for (long long i = 2; i <= n; i++) {
    tot_primes_till[i] = tot_primes_till[i - 1];
    if (!prime[i]) continue;
    tot_primes_till[i]++;
    for (long long j = 2 * i; j <= n; j += i) {
      prime[j] = false;
    }
  }
}
long long power(long long a, long long b, long long mod) {
  if (b == 0) {
    return 1;
  }
  long long answer = power(a, b / 2, mod);
  answer *= answer;
  answer %= mod;
  if (b % 2) {
    answer *= a;
  }
  return answer % mod;
}
long long modmul(long long a, long long b, long long mod) {
  long long res = 0;
  a %= mod;
  while (b) {
    if (b & 1) res = (res + a) % mod;
    a = (2 * a) % mod;
    b >>= 1;
  }
  return res;
}
long long gcd(long long int a, long long int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
long long lcm(int a, int b) { return (a / gcd(a, b)) * b; }
void solve() {
  long long q;
  cin >> q;
  map<long long, long long> m;
  vector<long long> v;
  vector<vector<long long>> s;
  while (q--) {
    long long f;
    cin >> f;
    if (f == 1) {
      long long x;
      cin >> x;
      s.push_back({x});
    } else {
      long long x, y;
      cin >> x >> y;
      s.push_back({x, y});
    }
  }
  for (long long i = s.size() - 1; i >= 0; i--) {
    if (s[i].size() == 1) {
      if (m.find(s[i][0]) == m.end()) {
        v.push_back(s[i][0]);
      } else {
        v.push_back(m[s[i][0]]);
      }
    } else {
      if (m.find(s[i][1]) == m.end()) {
        m[s[i][0]] = s[i][1];
      } else {
        m[s[i][0]] = m[s[i][1]];
      }
    }
  }
  reverse(v.begin(), v.end());
  for (long long i = 0; i < v.size(); i++) {
    cout << v[i] << " ";
  }
  cout << "\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  long long t;
  t = 1;
  while (t--) {
    solve();
  }
}

```