import java.io.BufferedReader import java.io.InputStream import java.io.InputStreamReader import java.util.* import kotlin.math.abs import kotlin.math.max import kotlin.math.min val MOD = 1_000_000_007L /** * @param n 個数 最大値じゃないぞ。 * iの範囲は[0, n - 1] * * AがIntやLongのときは埋め込んでしまおう * type A = Int */ class RangeUpdateTree(n: Int) { private val N = if (Integer.highestOneBit(n) == n) n else Integer.highestOneBit(n) shl 1 private val dat = IntArray(2 * N) /** * [l, r) */ fun add(l: Int, r: Int, a: Int) { var left = l + N var right = r - 1 + N while(left <= right) { if ((left and 1) == 1) dat[left] = dat[left] + a if ((right and 1) == 0) dat[right] = dat[right] + a left = (left + 1) shr 1 // 右の子供なら右の親に移動 right = (right - 1) shr 1 // 左の子供なら左の親に移動 } } fun query(i: Int): Int { var ix = N + i var res: Int = 0 while(ix >= 1) { res = res + dat[ix] ix = ix shr 1 } return res } } class UnionFind0(n: Int) { private val par = IntArray(n){it} val rank = Array(n){ val a = mutableListOf() a += it a } private val visits = IntArray(n) // 訪れた場所をfind毎に用意するのがもったいないのでつかいまわす fun isRt(x: Int): Boolean { return par[x] == x } fun find(x: Int): Int { var ptr = 0 var i = x while(par[i] != i) { visits[ptr++] = i i = par[i] } for (j in 0 until ptr) { par[visits[j]] = i } return i } private fun merge(node: Int, rt: Int): Int { par[node] = rt rank[rt].addAll(rank[node]) rank[node].clear() return rt } fun unite(x: Int, y: Int): Int { val x1 = find(x) val y1 = find(y) return if (x1 == y1) x1 else { if (rank[x1].size < rank[y1].size) merge(x1, y1) else merge(y1, x1) } } } data class Seg(var l: Int, var r: Int) class UnionFind1(n: Int, P: IntArray) { private val par = IntArray(n){it} val rank = IntArray(n){1} // 集合の要素数 val seg = Array(n){Seg(P[it], P[it] + 1)} private val visits = IntArray(n) // 訪れた場所をfind毎に用意するのがもったいないのでつかいまわす fun find(x: Int): Int { var ptr = 0 var i = x while(par[i] != i) { visits[ptr++] = i i = par[i] } for (j in 0 until ptr) { par[visits[j]] = i } return i } private fun merge(node: Int, rt: Int): Int { par[node] = rt rank[rt] += rank[node] seg[rt].l = min(seg[rt].l, seg[node].l) seg[rt].r = max(seg[rt].r, seg[node].r) return rt } fun unite(x: Int, y: Int): Int { val x1 = find(x) val y1 = find(y) return if (x1 == y1) x1 else { if (rank[x1] < rank[y1]) merge(x1, y1) else merge(y1, x1) } } } data class Query(val t: Int, val a: Int, val b: Int) class Solver(stream: InputStream, private val out: java.io.PrintWriter) { fun solve() { val N = ni() val M = ni() val uf0 = UnionFind0(N) val Q = Array(M) {Query(ni(), ni(), ni())} for (q in Q) { if (q.t == 1) { uf0.unite(q.a - 1, q.b - 1) } } val P = mutableListOf() for (i in 0 until N) { if (uf0.isRt(i)) { for (j in uf0.rank[i]) P += j } } debug{ P.joinToString(" ") } val revP = IntArray(N) for (i in 0 until N) { revP[P[i]] = i } val t = RangeUpdateTree(N) val uf = UnionFind1(N, revP) for (q in Q) { if (q.t == 1) { uf.unite(q.a - 1, q.b - 1) } else if (q.t == 2) { val seg = uf.seg[uf.find(q.a - 1)] t.add(seg.l, seg.r, q.b) } else { out.println(t.query(revP[q.a - 1])) } } } private val isDebug = try { // なんか本番でエラーでる System.getenv("MY_DEBUG") != null } catch (t: Throwable) { false } private var tokenizer: StringTokenizer? = null private val reader = BufferedReader(InputStreamReader(stream), 32768) private fun next(): String { while (tokenizer == null || !tokenizer!!.hasMoreTokens()) { tokenizer = StringTokenizer(reader.readLine()) } return tokenizer!!.nextToken() } private fun ni() = next().toInt() private fun nl() = next().toLong() private fun ns() = next() private fun na(n: Int, offset: Int = 0): IntArray { return map(n) { ni() + offset } } private fun nal(n: Int, offset: Int = 0): LongArray { val res = LongArray(n) for (i in 0 until n) { res[i] = nl() + offset } return res } private fun na2(n: Int, offset: Int = 0): Array { val a = Array(2){IntArray(n)} for (i in 0 until n) { for (e in a) { e[i] = ni() + offset } } return a } private inline fun map(n: Int, f: (Int) -> Int): IntArray { val res = IntArray(n) for (i in 0 until n) { res[i] = f(i) } return res } private inline fun debug(msg: () -> String) { if (isDebug) System.err.println(msg()) } private fun debug(a: LongArray) { debug { a.joinToString(" ") } } private fun debug(a: IntArray) { debug { a.joinToString(" ") } } private fun debug(a: BooleanArray) { debug { a.map { if (it) 1 else 0 }.joinToString("") } } private fun debugDim(A: Array) { if (isDebug) { for (a in A) { debug(a) } } } /** * 勝手にimport消されるのを防ぎたい */ private fun hoge() { min(1, 2) max(1, 2) abs(-10) } } fun main() { val out = java.io.PrintWriter(System.out) Solver(System.`in`, out).solve() out.flush() }