{"raw_statement":[{"iden":"statement","content":"In the magical forest, you come upon N walls that you think is a great place to store water for your animal friends. The ith wall consists of ai blocks stacked on top of each other.\n\n\n\nYour job is to answer queries of two types:\n\n- For queries of the first type, print the amount of water that could be stored between all the walls.\n\n- For queries of the second type, increase the number of blocks on the xth wall by v.\n\nThe first line of input is T – the number of test cases.\n\nThe first line of each test case is integers N and Q (1 ≤ N, Q ≤ 105).\n\nThe second line contains N space-separated integers ai (1 ≤ ai ≤ 105).\n\nThe next Q lines contain either ‘P’ – denoting a query of the first type, or ‘U’ followed by x and v – denoting a query of the second type (1 ≤ x ≤ N) (1 ≤ v ≤ 104).\n\nFor each test case and query of the first type, output on a line the amount of water that could be stored between the walls.\n\n"},{"iden":"input","content":"The first line of input is T – the number of test cases.The first line of each test case is integers N and Q (1 ≤ N, Q ≤ 105).The second line contains N space-separated integers ai (1 ≤ ai ≤ 105).The next Q lines contain either ‘P’ – denoting a query of the first type, or ‘U’ followed by x and v – denoting a query of the second type (1 ≤ x ≤ N) (1 ≤ v ≤ 104)."},{"iden":"output","content":"For each test case and query of the first type, output on a line the amount of water that could be stored between the walls."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ N \\in \\mathbb{Z} $ be the number of walls.  \n- Let $ Q \\in \\mathbb{Z} $ be the number of queries.  \n- Let $ A = (a_1, a_2, \\dots, a_N) $ be a sequence of non-negative integers representing the height of each wall.  \n\n**Constraints**  \n1. $ 1 \\leq T \\leq \\text{unspecified} $  \n2. For each test case:  \n   - $ 1 \\leq N, Q \\leq 10^5 $  \n   - $ 1 \\leq a_i \\leq 10^5 $ for all $ i \\in \\{1, \\dots, N\\} $  \n   - For update queries: $ 1 \\leq x \\leq N $, $ 1 \\leq v \\leq 10^4 $  \n\n**Operations**  \n- **Type P (Query)**: Compute the total trapped water between walls:  \n  $$\n  W = \\sum_{i=1}^{N} \\left( \\min\\left( \\max_{j=1}^{i-1} a_j, \\max_{j=i+1}^{N} a_j \\right) - a_i \\right)^+\n  $$  \n  where $ (x)^+ = \\max(0, x) $.  \n\n- **Type U (Update)**: Update $ a_x \\leftarrow a_x + v $.  \n\n**Objective**  \nFor each query of type P, output the value of $ W $ as defined above.","simple_statement":"You are given N walls, each with a certain height (number of blocks).  \nYou need to handle two types of queries:  \n1. \"P\" — Calculate how much water can be stored between all walls (like the Trapping Rain Water problem).  \n2. \"U x v\" — Increase the height of the x-th wall by v.  \n\nFor each \"P\" query, output the total water that can be trapped.","has_page_source":false}