{"problem":{"name":"Replacing","description":{"content":"You have a sequence $A$ composed of $N$ positive integers: $A_{1}, A_{2}, \\cdots, A_{N}$. You will now successively do the following $Q$ operations: *   In the $i$\\-th operation, you replace every el","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc171_d"},"statements":[{"statement_type":"Markdown","content":"You have a sequence $A$ composed of $N$ positive integers: $A_{1}, A_{2}, \\cdots, A_{N}$.\nYou will now successively do the following $Q$ operations:\n\n*   In the $i$\\-th operation, you replace every element whose value is $B_{i}$ with $C_{i}$.\n\nFor each $i$ $(1 \\leq i \\leq Q)$, find $S_{i}$: the sum of all elements in $A$ just after the $i$\\-th operation.\n\n## Constraints\n\n*   All values in input are integers.\n*   $1 \\leq N, Q, A_{i}, B_{i}, C_{i} \\leq 10^{5}$\n*   $B_{i} \\neq C_{i}$\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$A_{1}$ $A_{2}$ $\\cdots$ $A_{N}$\n$Q$\n$B_{1}$ $C_{1}$\n$B_{2}$ $C_{2}$\n$\\vdots$\n$B_{Q}$ $C_{Q}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc171_d","tags":[],"sample_group":[["4\n1 2 3 4\n3\n1 2\n3 4\n2 4","11\n12\n16\n\nInitially, the sequence $A$ is $1,2,3,4$.\nAfter each operation, it becomes the following:\n\n*   $2, 2, 3, 4$\n*   $2, 2, 4, 4$\n*   $4, 4, 4, 4$"],["4\n1 1 1 1\n3\n1 2\n2 1\n3 5","8\n4\n4\n\nNote that the sequence $A$ may not contain an element whose value is $B_{i}$."],["2\n1 2\n3\n1 100\n2 100\n100 1000","102\n200\n2000"]],"created_at":"2026-03-03 11:01:14"}}