You are given an array of field values fields, each a non-empty string. Classify every field as exactly one of four types, checked in this order:

1. int: an optional leading - followed by 1 to 18 digits (nothing else).
2. bool: the word true or false, compared case-insensitively.
3. date: exactly the shape DD/MM/YYYY (two digits, two digits, four digits separated by /) that forms a valid calendar date: month 01 to 12, and a day valid for that month. February has 29 days in leap years (years divisible by 4, except century years not divisible by 400).
4. string: anything else.

Return an array with the type label of each field, in order.

Examples

Example 1

Input: fields = ["1", "true", "12/05/2026", "sojdnvjbs", "12/14/2027"]
Output: ["int", "bool", "date", "string", "string"]
Explanation: "12/05/2026" is the 12th of May. "12/14/2027" is not a date:
14 is not a valid month, so it falls through to string.