{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eThe \u003cb\u003elambda calculus\u003c/b\u003e is a simple language that is often used to study the theory of programming languages. This language only consists of variable references, functions that take a single argument, and applications of functions.\u003cbr\u003eThe lambda calculus consists of a language of \u003cb\u003elambda terms\u003c/b\u003e. The syntax of the lambda calculus defines that all valid lambda terms can be built by applying the following three rules:\u003cbr\u003e1. a \u003cb\u003evariable\u003c/b\u003e x, which is a nonempty string other than lambda, is itself a lambda term;\u003cbr\u003e2. if t is a valid lambda term, and x is a variable, then (lambda (x) t) is a lambda term (called a \u003cb\u003elambda abstraction\u003c/b\u003e), here x has at least one occurrence in t;\u003cbr\u003e3. if t and s are lambda terms, then (t s) is a lambda term (called an \u003cb\u003eapplication\u003c/b\u003e).\u003cbr\u003eNothing else is a lambda term. Thus a lambda term is valid if and only if it can be obtained by repeated application of these three rules. Note that the parentheses in the second and the third rule can NOT be omitted.\u003cbr\u003eA \u003cb\u003elambda abstraction\u003c/b\u003e (lambda (x) t) is a definition of an anonymous function that is capable of taking a single input x and substituting it into the term t. The abstraction \u003cb\u003ebinds\u003c/b\u003e the variable x in term t, so we call it a \u003cb\u003elambda binding\u003c/b\u003e of variable x.\u003cbr\u003eAn \u003cb\u003eapplication\u003c/b\u003e (t s) represents the application of a function t to an input s, that is, it represents the act of calling\u003cbr\u003efunction t on input s to produce t(s).\u003cbr\u003eTo see how this works, consider the lambda calculus extended with arithmetic operators. In that language, a lambda abstraction (lambda (x) x + 5), in which x is bound, defines a function f(x) \u003d x + 5. And an application ((lambda (x) x + 5) 3) applies function f(x) \u003d x + 5 to input 3 and produces f(3) \u003d 3 + 5 \u003d 8.\u003cbr\u003eWe say that a variable \u003cb\u003eoccurs free\u003c/b\u003e in an lambda term t if it has some occurrence in t that is not inside some lambda binding of the same variable. For example,\u003cbr\u003e $\\bullet$ x occurs free in x;\u003cbr\u003e $\\bullet$ x does not occur free in y;\u003cbr\u003e $\\bullet$ x does not occur free in (lambda (x) (x y));\u003cbr\u003e $\\bullet$ x occurs free in (lambda (y) (x y));\u003cbr\u003e $\\bullet$ x occurs free in ((lambda (x) x) (x y)), which is an application that produces (x y) in which x occurs free;\u003cbr\u003e $\\bullet$ x occurs free in (lambda (y) (lambda (z) (x (y z)))).\u003cbr\u003eNow you are given a lambda term t, you need to find all distinct variables that occur free in t.\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line of the input contains a positive integer T denoting the number of test cases. Then T lines follow, each line contains a nonempty string denoting a lambda term.\u003cbr\u003eEach variable in the the lambda terms contains only latin letters and the hyphen, and is no longer than 20 characters.\u003cbr\u003eIt is guaranteed that all lambda terms in the input are valid, and the total length of all lambda terms will not exceed 107 .\u003cbr\u003eThere might be some extra spaces in the input as long as they do not cause any misunderstanding."}},{"title":"Output","value":{"format":"HTML","content":"For each test case, output first the case number and then all distinct variables that occur free in the lambda term in a single line. These variables should be printed in lexicographic order, and there should be a single space between\u003cbr\u003eeach two adjacent variables. There should be a space after the colon in each test case.\u003cbr\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e6\r\nx\r\ny\r\n(lambda (x) (x y))\r\n(lambda (y) (x y))\r\n( (lambda (x) x) (x y) )\r\n( lambda (y) ( lambda (z) (x (y z)) ) )\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1: x\r\nCase #2: y\r\nCase #3: y\r\nCase #4: x\r\nCase #5: x y\r\nCase #6: x\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cbr\u003eThe free variables of a term are those variables not bound by a lambda abstraction. The set of free variables of\u003cbr\u003ean expression is defined inductively:\u003cbr\u003e1. The free variables of x are just x;\u003cbr\u003e2. The set of free variables of (lambda (x) t) is the set of free variables of t, but with x removed;\u003cbr\u003e3. The set of free variables of (t s) is the union\u003cbr\u003eWe can define it with the context-free grammar:\u003cbr\u003e LcExp ::\u003d Variable\u003cbr\u003e ::\u003d (lambda (Variable) LcExp)\u003cbr\u003e ::\u003d (LcExp LcExp)\u003cbr\u003ewhere a variable is any string other than lambda.\u003cbr\u003e"}}]}