Problem Statement

You are given a positive integer N.

Find the number of triples of positive integers (A, B, C) such that A\leq B\leq C and ABC\leq N.

The Constraints guarantee that the answer is less than 2^{63}.

Constraints

• 1 \leq N \leq 10^{11}
• N is an integer.

Sample Input 1

4

Sample Output 1

5

There are five such triples: (1,1,1),(1,1,2),(1,1,3),(1,1,4),(1,2,2).

Sample Input 2

100

Sample Output 2

323

Sample Input 3

100000000000

Sample Output 3

5745290566750

Problem Statement

Consider a two-dimensional coordinate plane, where the x-axis is oriented to the right, and the y-axis is oriented upward.

In this plane, there is a quadrilateral without self-intersection.
The coordinates of the four vertices are (A_x,A_y), (B_x,B_y), (C_x,C_y), and (D_x,D_y), in counter-clockwise order.

Determine whether this quadrilateral is convex.

Here, a quadrilateral is convex if and only if all four interior angles are less than 180 degrees.

Constraints

• -100 \leq A_x,A_y,B_x,B_y,C_x,C_y,D_x,D_y \leq 100
• All values in input are integers.
• The given four points are the four vertices of a quadrilateral in counter-clockwise order.
• The quadrilateral formed by the given four points has no self-intersection and is non-degenerate. That is,
  • no two vertices are at the same coordinates;
  • no three vertices are colinear; and
  • no two edges that are not adjacent have a common point.

Sample Input 1

0 0
1 0
1 1
0 1

Sample Output 1

Yes

The given quadrilateral is a square, whose four interior angles are all 90 degrees. Thus, this quadrilateral is convex.

Sample Input 2

0 0
1 1
-1 0
1 -1

Sample Output 2

No

The angle A is 270 degrees. Thus, this quadrilateral is not convex.

Problem Statement

You are given a string S of length N consisting of digits.

Find the number of square numbers that can be obtained by interpreting a permutation of S as a decimal integer.

More formally, solve the following.

Let s _ i be the number corresponding to the i-th digit (1\leq i\leq N) from the beginning of S.

Find the number of square numbers that can be represented as \displaystyle \sum _ {i=1} ^ N s _ {p _ i}10 ^ {N-i} with a permutation P=(p _ 1,p _ 2,\ldots,p _ N) of (1, \dots, N).

Constraints

• 1\leq N\leq 13
• S is a string of length N consisting of digits.
• N is an integer.

Sample Input 1

4
4320

Sample Output 1

2

For P=(4,2,3,1), we have s _ 4\times10 ^ 3+s _ 2\times10 ^ 2+s _ 3\times10 ^ 1+s _ 1=324=18 ^ 2.
For P=(3,2,4,1), we have s _ 3\times10 ^ 3+s _ 2\times10 ^ 2+s _ 4\times10 ^ 1+s _ 1=2304=48 ^ 2.

No other permutations result in square numbers, so you should print 2.

Sample Input 2

3
010

Sample Output 2

2

For P=(1,3,2) or P=(3,1,2), we have \displaystyle\sum _ {i=1} ^ Ns _ {p _ i}10 ^ {N-i}=1=1 ^ 2.
For P=(2,1,3) or P=(2,3,1), we have \displaystyle\sum _ {i=1} ^ Ns _ {p _ i}10 ^ {N-i}=100=10 ^ 2.

No other permutations result in square numbers, so you should print 2. Note that different permutations are not distinguished if they result in the same number.

Sample Input 3

13
8694027811503

Sample Output 3

840

Problem Statement

AtCoder Inc. sells merchandise on its online shop.

There are N items remaining in the company. The weight of the i-th item (1\leq i\leq N) is W_i.

Takahashi will sell these items as D lucky bags.
He wants to minimize the variance of the total weights of the items in the lucky bags.
Here, the variance is defined as V=\frac{1}{D}\displaystyle\sum_{i=1}^D (x_i-\bar{x})^2, where x_1,x_2,\ldots,x_D are the total weights of the items in the lucky bags, and \bar{x}=\frac{1}{D}(x_1+x_2+\cdots+x_D) is the average of x_1,x_2,\ldots,x_D.

Find the variance of the total weights of the items in the lucky bags when the items are divided to minimize this value.
It is acceptable to have empty lucky bags (in which case the total weight of the items in that bag is defined as 0),
but each item must be in exactly one of the D lucky bags.

Constraints

• 2 \leq D\leq N\leq 15
• 1 \leq W_i\leq 10^8
• All input values are integers.

Sample Input 1

5 3
3 5 3 6 3

Sample Output 1

0.888888888888889

If you put the first and third items in the first lucky bag, the second and fifth items in the second lucky bag, and the fourth item in the third lucky bag, the total weight of the items in the bags are 6, 8, and 6, respectively.

Then, the average weight is \frac{1}{3}(6+8+6)=\frac{20}{3},
and the variance is \frac{1}{3}\left\{\left(6-\frac{20}{3}\right)^2+\left(8-\frac{20}{3}\right)^2+\left(6-\frac{20}{3}\right)^2 \right\}=\frac{8}{9}=0.888888\ldots, which is the minimum.

Note that multiple items may have the same weight, and that each item must be in one of the lucky bags.

Problem Statement

You are given a sequence A = (A_1, A_2, \ldots, A_N) of length N.

Process Q queries in the order they are given. Each query is of one of the following two types:

• Type 1: Given in the form 1 p x. Change the value of A_p to x.
• Type 2: Given in the form 2 l r. print the number of occurrences of the second largest value in (A_l, A_{l+1}, \ldots, A_r). More precisely, print the number of integers i satisfying l \leq i \leq r such that there is exactly one distinct value greater than A_i among A_l, A_{l+1}, \ldots, A_r.

Constraints

• 1 \leq N, Q \leq 2 \times 10^5
• 1 \leq A_i \leq 10^9
• For type-1 queries, 1 \leq p \leq N.
• For type-1 queries, 1 \leq x \leq 10^9.
• For type-2 queries, 1 \leq l \leq r \leq N.
• There is at least one type-2 query.
• All input values are integers.

Sample Input 1

5 4
3 3 1 4 5
2 1 3
2 5 5
1 3 3
2 2 4

Sample Output 1

1
0
2

Initially, A = (3, 3, 1, 4, 5).

For the first query, the second largest value in (3, 3, 1) is 1, which appears once in 3, 3, 1, so print 1.

For the second query, there is no second largest value in (5), so print 0.

The third query makes A = (3, 3, 3, 4, 5).

For the fourth query, the second largest value in (3, 3, 4), is 3, which appears twice in 3, 3, 4, so print 2.

Sample Input 2

1 1
1000000000
2 1 1

Sample Output 2

0

Sample Input 3

8 9
2 4 4 3 9 1 1 2
1 5 4
2 7 7
2 2 6
1 4 4
2 2 5
2 2 7
1 1 1
1 8 1
2 1 8

Sample Output 3

0
1
0
2
4