package contest220722; import java.io.*; import java.util.*; import java.util.function.IntUnaryOperator; import java.util.function.LongUnaryOperator; public class G { InputStream is; FastWriter out; String INPUT = ""; public void solve() { int n = ni(); StringBuilder[] ss = new StringBuilder[n]; int[] fp = new int[n]; for(int i = 0;i < n;i++){ ss[i] = new StringBuilder(ns()); fp[i] = ss[i].length(); } int Q = ni(); int[][] qs = new int[Q][]; for(int i = 0;i < Q;i++){ int t = ni(); if(t == 1) { int x = ni() - 1; char c = nc(); qs[i] = new int[]{1, x, c}; ss[x].append(c); }else{ int x = ni()-1; qs[i] = new int[]{2, x}; } } TrieByList trie = new TrieByList(); for(int i = 0;i < n;i++){ trie.add(ss[i].toString().toCharArray()); } TrieByList.Node[] ns = trie.toArray(); int[][] ch = new int[trie.gen][]; for(int i = 0;i < trie.gen;i++){ ch[i] = new int[ns[i].p]; for(int j = 0;j < ns[i].p;j++){ ch[i][j] = ns[i].child[j].id; } } int[][] g = parentToG(childrenToParent(ch)); int[][] pars = parents(g, 0); int[] par = pars[0]; int[][] rights = makeRights(g, par, 0); int[] ord = rights[0], iord = rights[1], right = rights[2]; long[] ft = new long[g.length+5]; TrieByList.Node[] curs = new TrieByList.Node[n]; for(int i = 0;i < n;i++){ TrieByList.Node cur = trie.root; for(int j = 0;j < fp[i];j++){ cur = cur.search(ss[i].charAt(j)); addFenwick(ft, iord[cur.id], 1); addFenwick(ft, right[iord[cur.id]]+1, -1); } curs[i] = cur; } for(int[] q : qs){ if(q[0] == 1){ curs[q[1]] = curs[q[1]].search((char)q[2]); addFenwick(ft, iord[curs[q[1]].id], 1); addFenwick(ft, right[iord[curs[q[1]].id]]+1, -1); }else{ out.println(sumFenwick(ft, iord[curs[q[1]].id])); } } } public static long sumFenwick(long[] ft, int i) { long sum = 0; for(i++;i > 0;i -= i&-i)sum += ft[i]; return sum; } public static void addFenwick(long[] ft, int i, long v) { if(v == 0)return; int n = ft.length; for(i++;i < n;i += i&-i)ft[i] += v; } public static int[][] parents(int[][] g, int root) { int n = g.length; int[] par = new int[n]; Arrays.fill(par, -1); int[] depth = new int[n]; depth[0] = 0; int[] q = new int[n]; q[0] = root; for (int p = 0, r = 1; p < r; p++) { int cur = q[p]; for (int nex : g[cur]) { if (par[cur] != nex) { q[r++] = nex; par[nex] = cur; depth[nex] = depth[cur] + 1; } } } return new int[][]{par, q, depth}; } public static int[] sortByPreorder(int[][] g, int root){ int n = g.length; int[] stack = new int[n]; int[] ord = new int[n]; boolean[] ved = new boolean[n]; stack[0] = root; int p = 1; int r = 0; ved[root] = true; while(p > 0){ int cur = stack[p-1]; ord[r++] = cur; p--; for(int e : g[cur]){ if(!ved[e]){ ved[e] = true; stack[p++] = e; } } } return ord; } /** * ルートrootの木gに対し、行きがけ順で訪れたときの各ノードの子孫を表す範囲の終端を計算する。 * 格納はソート順で行われている。ルートが[0]に対応する。 * [ord, iord, right] * * @usage ノード番号xに対して対応する範囲は[iord[x], right[iord[x]]]. * @param g * @param par * @param root * @return */ public static int[][] makeRights(int[][] g, int[] par, int root) { int n = g.length; int[] ord = sortByPreorder(g, root); int[] iord = new int[n]; for(int i = 0;i < n;i++)iord[ord[i]] = i; int[] right = new int[n]; for(int i = n-1;i >= 1;i--){ if(right[i] == 0)right[i] = i; int p = iord[par[ord[i]]]; right[p] = Math.max(right[p], right[i]); } return new int[][]{ord, iord, right}; } public static int[] childrenToParent(int[][] children) { int n = children.length; int[] ret = new int[n]; Arrays.fill(ret, -1); for(int i = 0;i < n;i++){ for(int q : children[i]){ ret[q] = i; } } return ret; } public static int[][] parentToG(int[] par) { int n = par.length; int[] ct = new int[n]; for(int i = 0;i < n;i++){ if(par[i] >= 0){ ct[i]++; ct[par[i]]++; } } int[][] g = new int[n][]; for(int i = 0;i < n;i++){ g[i] = new int[ct[i]]; } for(int i = 0;i < n;i++){ if(par[i] >= 0){ g[par[i]][--ct[par[i]]] = i; g[i][--ct[i]] = par[i]; } } return g; } public static class TrieByList { public Node root = new Node((char) 0, 0); public int gen = 1; public List leaf; public long[] dp; public static class Node { public int id; public char c; public long ptn = 0; public int p = 0; public Node[] child = null; public int hit = 0; public Node fail; public Node(char c, int id) { this.id = id; this.c = c; } public int enc(char c) { // return c <= 'Z' ? c-'A' : c-'a'+32; return c - 'a'; } public void appendChild(Node n) { if (p == 0) { child = new Node[1]; } else if (p + 1 >= child.length) { child = Arrays.copyOf(child, child.length * 2); } int z = enc(n.c); int nind = Long.bitCount(ptn << ~z); ptn |= 1L << z; System.arraycopy(child, nind, child, nind + 1, p - nind); child[nind] = n; p++; } public Node search(char c) { if (ptn << ~enc(c) < 0) { return child[Long.bitCount(ptn << ~enc(c)) - 1]; } else { return null; } } public String toString(String indent) { StringBuilder sb = new StringBuilder(); sb.append(indent + id + ":" + c); if (hit != 0) sb.append(" H:" + hit); if (fail != null) sb.append(" F:" + fail.id); sb.append("\n"); for (int i = 0; i < p; i++) { sb.append(child[i].toString(indent + " ")); } return sb.toString(); } } public void add(char[] s) { Node cur = root; Node pre = null; for (char c : s) { pre = cur; cur = pre.search(c); if (cur == null) { cur = new Node(c, gen++); pre.appendChild(cur); } } cur.hit++; } public void buildFailure() { root.fail = null; Queue q = new ArrayDeque(); q.add(root); while (!q.isEmpty()) { Node cur = q.poll(); inner: for (int i = 0; i < cur.p; i++) { Node ch = cur.child[i]; q.add(ch); for (Node to = cur.fail; to != null; to = to.fail) { Node lch = to.search(ch.c); if (lch != null) { ch.fail = lch; ch.hit += lch.hit; // propagation of hit continue inner; } } ch.fail = root; } } } public Node next(Node cur, char c) { for (; cur != null; cur = cur.fail) { Node next = cur.search(c); if (next != null) { return next; } // dead } return root; } public int countHit(char[] q) { Node cur = root; int hit = 0; outer: for (char c : q) { for (; cur != null; cur = cur.fail) { Node next = cur.search(c); if (next != null) { hit += next.hit; cur = next; continue outer; } } cur = root; } return hit; } public Node[] toArray() { Node[] ret = new Node[gen]; ret[0] = root; for (int i = 0; i < gen; i++) { Node cur = ret[i]; for (int j = 0; j < cur.p; j++) { ret[cur.child[j].id] = cur.child[j]; } } return ret; } public String toString() { return root.toString(""); } } public static void main(String[] args) { new G().run(); } public void run() { long S = System.currentTimeMillis(); is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes()); out = new FastWriter(System.out); solve(); out.flush(); long G = System.currentTimeMillis(); tr(G-S+"ms"); // Thread t = new Thread(null, null, "~", Runtime.getRuntime().maxMemory()){ // @Override // public void run() { // long s = System.currentTimeMillis(); // solve(); // out.flush(); // if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms"); // } // }; // t.start(); // t.join(); } private boolean eof() { if(lenbuf == -1)return true; int lptr = ptrbuf; while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false; try { is.mark(1000); while(true){ int b = is.read(); if(b == -1){ is.reset(); return true; }else if(!isSpaceChar(b)){ is.reset(); return false; } } } catch (IOException e) { return true; } } private final byte[] inbuf = new byte[1024]; public int lenbuf = 0, ptrbuf = 0; private int readByte() { if(lenbuf == -1)throw new InputMismatchException(); if(ptrbuf >= lenbuf){ ptrbuf = 0; try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); } if(lenbuf <= 0)return -1; } return inbuf[ptrbuf++]; } private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); } // private boolean isSpaceChar(int c) { return !(c >= 32 && c <= 126); } private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; } private double nd() { return Double.parseDouble(ns()); } private char nc() { return (char)skip(); } private String ns() { int b = skip(); StringBuilder sb = new StringBuilder(); while(!(isSpaceChar(b))){ sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } private char[] ns(int n) { char[] buf = new char[n]; int b = skip(), p = 0; while(p < n && !(isSpaceChar(b))){ buf[p++] = (char)b; b = readByte(); } return n == p ? buf : Arrays.copyOf(buf, p); } private char[][] nm(int n, int m) { char[][] map = new char[n][]; for(int i = 0;i < n;i++)map[i] = ns(m); return map; } private int[][] nmi(int n, int m) { int[][] map = new int[n][]; for(int i = 0;i < n;i++)map[i] = na(m); return map; } private int[] na(int n) { int[] a = new int[n]; for(int i = 0;i < n;i++)a[i] = ni(); return a; } private long[] nal(int n) { long[] a = new long[n]; for(int i = 0;i < n;i++)a[i] = nl(); return a; } private int ni() { int num = 0, b; boolean minus = false; while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')); if(b == '-'){ minus = true; b = readByte(); } while(true){ if(b >= '0' && b <= '9'){ num = num * 10 + (b - '0'); }else{ return minus ? -num : num; } b = readByte(); } } private long nl() { long num = 0; int b; boolean minus = false; while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')); if(b == '-'){ minus = true; b = readByte(); } while(true){ if(b >= '0' && b <= '9'){ num = num * 10 + (b - '0'); }else{ return minus ? -num : num; } b = readByte(); } } public static class FastWriter { private static final int BUF_SIZE = 1<<13; private final byte[] buf = new byte[BUF_SIZE]; private final OutputStream out; private int ptr = 0; private FastWriter(){out = null;} public FastWriter(OutputStream os) { this.out = os; } public FastWriter(String path) { try { this.out = new FileOutputStream(path); } catch (FileNotFoundException e) { throw new RuntimeException("FastWriter"); } } public FastWriter write(byte b) { buf[ptr++] = b; if(ptr == BUF_SIZE)innerflush(); return this; } public FastWriter write(char c) { return write((byte)c); } public FastWriter write(char[] s) { for(char c : s){ buf[ptr++] = (byte)c; if(ptr == BUF_SIZE)innerflush(); } return this; } public FastWriter write(String s) { s.chars().forEach(c -> { buf[ptr++] = (byte)c; if(ptr == BUF_SIZE)innerflush(); }); return this; } private static int countDigits(int l) { if (l >= 1000000000) return 10; if (l >= 100000000) return 9; if (l >= 10000000) return 8; if (l >= 1000000) return 7; if (l >= 100000) return 6; if (l >= 10000) return 5; if (l >= 1000) return 4; if (l >= 100) return 3; if (l >= 10) return 2; return 1; } public FastWriter write(int x) { if(x == Integer.MIN_VALUE){ return write((long)x); } if(ptr + 12 >= BUF_SIZE)innerflush(); if(x < 0){ write((byte)'-'); x = -x; } int d = countDigits(x); for(int i = ptr + d - 1;i >= ptr;i--){ buf[i] = (byte)('0'+x%10); x /= 10; } ptr += d; return this; } private static int countDigits(long l) { if (l >= 1000000000000000000L) return 19; if (l >= 100000000000000000L) return 18; if (l >= 10000000000000000L) return 17; if (l >= 1000000000000000L) return 16; if (l >= 100000000000000L) return 15; if (l >= 10000000000000L) return 14; if (l >= 1000000000000L) return 13; if (l >= 100000000000L) return 12; if (l >= 10000000000L) return 11; if (l >= 1000000000L) return 10; if (l >= 100000000L) return 9; if (l >= 10000000L) return 8; if (l >= 1000000L) return 7; if (l >= 100000L) return 6; if (l >= 10000L) return 5; if (l >= 1000L) return 4; if (l >= 100L) return 3; if (l >= 10L) return 2; return 1; } public FastWriter write(long x) { if(x == Long.MIN_VALUE){ return write("" + x); } if(ptr + 21 >= BUF_SIZE)innerflush(); if(x < 0){ write((byte)'-'); x = -x; } int d = countDigits(x); for(int i = ptr + d - 1;i >= ptr;i--){ buf[i] = (byte)('0'+x%10); x /= 10; } ptr += d; return this; } public FastWriter write(double x, int precision) { if(x < 0){ write('-'); x = -x; } x += Math.pow(10, -precision)/2; // if(x < 0){ x = 0; } write((long)x).write("."); x -= (long)x; for(int i = 0;i < precision;i++){ x *= 10; write((char)('0'+(int)x)); x -= (int)x; } return this; } public FastWriter writeln(char c){ return write(c).writeln(); } public FastWriter writeln(int x){ return write(x).writeln(); } public FastWriter writeln(long x){ return write(x).writeln(); } public FastWriter writeln(double x, int precision){ return write(x, precision).writeln(); } public FastWriter write(int... xs) { boolean first = true; for(int x : xs) { if (!first) write(' '); first = false; write(x); } return this; } public FastWriter write(long... xs) { boolean first = true; for(long x : xs) { if (!first) write(' '); first = false; write(x); } return this; } public FastWriter write(IntUnaryOperator f, int... xs) { boolean first = true; for(int x : xs) { if (!first) write(' '); first = false; write(f.applyAsInt(x)); } return this; } public FastWriter write(LongUnaryOperator f, long... xs) { boolean first = true; for(long x : xs) { if (!first) write(' '); first = false; write(f.applyAsLong(x)); } return this; } public FastWriter writeln() { return write((byte)'\n'); } public FastWriter writeln(int... xs) { return write(xs).writeln(); } public FastWriter writeln(long... xs) { return write(xs).writeln(); } public FastWriter writeln(IntUnaryOperator f, int... xs) { return write(f, xs).writeln(); } public FastWriter writeln(LongUnaryOperator f, long... xs) { return write(f, xs).writeln(); } public FastWriter writeln(char[] line) { return write(line).writeln(); } public FastWriter writeln(char[]... map) { for(char[] line : map)write(line).writeln();return this; } public FastWriter writeln(String s) { return write(s).writeln(); } private void innerflush() { try { out.write(buf, 0, ptr); ptr = 0; } catch (IOException e) { throw new RuntimeException("innerflush"); } } public void flush() { innerflush(); try { out.flush(); } catch (IOException e) { throw new RuntimeException("flush"); } } public FastWriter print(byte b) { return write(b); } public FastWriter print(char c) { return write(c); } public FastWriter print(char[] s) { return write(s); } public FastWriter print(String s) { return write(s); } public FastWriter print(int x) { return write(x); } public FastWriter print(long x) { return write(x); } public FastWriter print(double x, int precision) { return write(x, precision); } public FastWriter println(char c){ return writeln(c); } public FastWriter println(int x){ return writeln(x); } public FastWriter println(long x){ return writeln(x); } public FastWriter println(double x, int precision){ return writeln(x, precision); } public FastWriter print(int... xs) { return write(xs); } public FastWriter print(long... xs) { return write(xs); } public FastWriter print(IntUnaryOperator f, int... xs) { return write(f, xs); } public FastWriter print(LongUnaryOperator f, long... xs) { return write(f, xs); } public FastWriter println(int... xs) { return writeln(xs); } public FastWriter println(long... xs) { return writeln(xs); } public FastWriter println(IntUnaryOperator f, int... xs) { return writeln(f, xs); } public FastWriter println(LongUnaryOperator f, long... xs) { return writeln(f, xs); } public FastWriter println(char[] line) { return writeln(line); } public FastWriter println(char[]... map) { return writeln(map); } public FastWriter println(String s) { return writeln(s); } public FastWriter println() { return writeln(); } } public static void trnz(int... o) { for(int i = 0;i < o.length;i++)if(o[i] != 0)System.out.print(i+":"+o[i]+" "); System.out.println(); } // print ids which are 1 public static void trt(long... o) { Queue stands = new ArrayDeque<>(); for(int i = 0;i < o.length;i++){ for(long x = o[i];x != 0;x &= x-1)stands.add(i<<6|Long.numberOfTrailingZeros(x)); } System.out.println(stands); } public static void tf(boolean... r) { for(boolean x : r)System.out.print(x?'#':'.'); System.out.println(); } public static void tf(boolean[]... b) { for(boolean[] r : b) { for(boolean x : r)System.out.print(x?'#':'.'); System.out.println(); } System.out.println(); } public void tf(long[]... b) { if(INPUT.length() != 0) { for (long[] r : b) { for (long x : r) { for (int i = 0; i < 64; i++) { System.out.print(x << ~i < 0 ? '#' : '.'); } } System.out.println(); } System.out.println(); } } public void tf(long... b) { if(INPUT.length() != 0) { for (long x : b) { for (int i = 0; i < 64; i++) { System.out.print(x << ~i < 0 ? '#' : '.'); } } System.out.println(); } } private void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); } }