GOODS - good string

 

The definition of beauty quotes sequence:
Empty string is a series of beautiful quotes.
If X is a series of beautiful quotes, then [X], (X), {X} is also a beautiful array brackets.
If X, Y ranges are 2 beautiful quotation marks, the sequence XY is also beautiful.
Example: () [() ()] is a row of beautiful quotes. {[)} Is not beautiful array brackets.
Given a string S contains only the brackets. When writing out the characters from position to position i of the string S j (1 <= i <= j <= Length (S)) we obtain the sequence S (i, j). An S (i, j) is the better of the string S if S (i, j) is a series of beautiful quotes. Request the number of good properties of S.

The definition of beauty quotes sequence:

Empty string is a series of beautiful quotes.

If X is a series of beautiful quotes, then [X], (X), {X} is also a beautiful array brackets.

If X, Y ranges are 2 beautiful quotation marks, the sequence XY is also beautiful.

Example: () [() ()] is a row of beautiful quotes. {[)} Is not beautiful array brackets.

Given a string S contains only the brackets. When writing out the characters from position to position i of the string S j (1 <= i <= j <= Length (S)) we obtain the sequence S (i, j). An S (i, j) is good substring of string S if S (i, j) is a series of beautiful quotes. Request the number of good substring of S.

Input

A single line: string S.

The first 10 trials, the length of S is less than 101.

The next 10 trials, the length of S is less than 10001.

10 final test, the length of S is less than 1000001.

Output

A single integer: Number of possible substring of S.

Example

Input:
(){](({}))[]

Output:
6

Added by:Phạm Bá Thái
Date:2013-09-06
Time limit:0.200s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Mine

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.