Valid Palindrome

Easy

Given a string, print whether it is a palindrome after converting uppercase letters to lowercase and ignoring non-alphanumeric characters. Input format: - One line: s Print `true` or `false`.

Constraints

0 <= s.length <= 2 * 10^5

Sample tests

Sample 1

Input

A man, a plan, a canal: Panama

Output

true

Sample 2

Input

race a car

Output

false