Problem Statement

You have been charged with writing the 'type checking' module for a new language called TC--. When coding in TC--, the coder is allowed to omit the types of local variables and parameters, and the return types of functions, only when the compiler is able to deduce those types from their usage. Each valid program has one and only one possible "type set".

Sometimes a variable is used before its type is "known" when reading the program from top to bottom, but that should not deter the type checking module you're writing. Once the type of a variable is known, it is retroactively effective to the start of the function, and proactively effective to the end of the function. This applies to local variables, formal parameters, and function return types.

Informally the grammar can be defined as:

• - A program is one or more function definitions.
• - A function definition always includes the name of the function, zero or more parameters with optional type definitions, and an optional return type. Every function will return a value, even if it is not explicitly declared. After the function definition, zero or more local variables will be defined, then zero or more program statements, then exactly one return statement. Example:

  	function a(b:string)
  

• - Local variable definitions. Variable definitions are optional, but when present, must specify the variable name and type:

  	a:int
  	b:string
  

• - Function call. There can be zero or more actual arguments, which always match the type and number of formal parameters. All arguments are variables only and never integer or string constants, nor expressions.

  	a=b()
  	c=d(e,f,g)
  

• - Assignment.

  	a=12345
  	s="this is 'a' string constant!"
  	b=c
  

• - Expressions: (note, you cannot mix ints and strings, and cannot use constants in expressions)

  	a=b+c
  	a=b-c
  	a=b/c
  	a=b*c
  

• - Return statement: (you can return a variable, or an int or string constant)

  	return x
  

Function calls, assignments and expressions are all instances of "program statements" and can occur in any order within the function. A return statement will always be the last statement in a function.

Note that there are only two data types in TC--: int and string. You cannot mix ints and strings in an assignment or an expression. Only the + and - operators are valid on strings, whereas all four operators are valid on ints. Both arguments to a binary operator must be variables or parameters of the same type (no constants in expressions).

For example (line numbers and whitespace added for clarity):

	 1  function f(a,b,c)
	 2     e:int
	 3     g=h(a)
	 4     e=b+c
	 5     return c
	 6  
	 7  function h(p:string):string
	 8     return p

The TC-- compiler will deduce the following types:

• - The type of parameter a is string from the call on line 3 to function h - whose argument must be a string.
• - The type of parameters b and c is int, since e is declared as an int on line 2 and you can only add ints together, on line 4.
• - Since c is an int, and function f returns it on line 5, we know that the return type of f is int.
• - Therefore the complete signature of function f is:

  	function f(a:string,b:int,c:int):int
  

• - The type of local variable g must be string because on line 3 it calls function h, which returns a string, defined on line 7. (Note: the fact that p is declared as a string on line 7, and returned on line 8, is another way to determine that the return type of h is string.)

Write a method, deduceTypes, which is given a valid TC-- program which follows the grammar defined above, and determines each function's complete signature and the types of all local variables in each function. The program provided will be syntactically valid, and will be guaranteed to have only one unique type assignment. Your method should return a String[] which contains two types of entries:

1. 1. function signatures, in the order they were defined in program, in the following format:

   	function name(param:type,...):type
   

   The only whitespace should be a single space between the word "function" (quotes added for clarity) and the name of the function. As listed in the constraints section, all function and parameter names are single letters, lower case.
   
   
   
   
2. 2. local variable declarations, in alphabetical order within each function, in the following format:

   	var:type
   

   There should be no whitespace. type should be either "string" or "int" (quotes added for clarity). As listed in the constraints section, all variable names are single letters, lower case.

Therefore, for the above example, your output should be:

	function f(a:string,b:int,c:int):int
	e:int
	g:string
	function h(p:string):string

Definition

Notes

Constraints

!@#$%^*()_+`~-={}|;:,.?

Examples